Complessità computazionale e nidificazione di forme

Question

Ho percorsi di abbozzo SVG che ho bisogno di imballare nel modo più efficiente possibile all'interno di un determinato rettangolo (con meno spreco di spazio possibile). Dopo alcune ricerche ho trovato gli algoritmi di bin packing che sembrano trattare scatole e forme curve non curve (le mie forme SVG sono piuttosto complesse e includono beziers, ecc.).

AFAIK, non esiste un algoritmo deterministico per il riempimento effettivo di forme astratte.

Desidero essere smentito qui quale sarebbe l'ideale (avendo un metodo deterministico matematico per comprimerle). Nel caso in cui io sono a destra e comunque non c'è, quale sarebbe l'approccio migliore per questo problema

Il nome del soggetto è Shape Nesting, Nesting Problem or Nesting Process.

In Nesting Forma non esiste un algoritmo singolo/uniforme o un metodo matematico per annidare le forme e ottenere il minimo spreco di spazio possibile.

• Il primo metodo è l'algoritmo di impacchettamento (crea un immaginario riquadro per ogni forma e utilizza un algoritmo 2D rettangolare per imballare le riquadri limite). Questo metodo è veloce ma il meno efficiente per quanto riguarda lo spreco di spazio .

• Il secondo metodo è una sorta di rotazione incrementale. L'algoritmo ruota la forma a passi incrementali e verifica se si adatta allo spazio . Questo è meglio del metodo di imballaggio per quanto riguarda lo spreco di spazio ma è faticosamente lento e talvolta appende anche un PC moderno (Immagina di ruotare ogni forma a incrementi di 1 grado e controllando se si adatta. Ora per 3-5 forme che sarebbe stato ok, ma quello che accade a > 20 forme?

Quali sono alcuni altri esempi aula per il raggiungimento di una soluzione a questo problema?

Answer 1

[Edit1] nuova risposta

come accennato prima bin-imballaggio è NP completo (hard) dimenticatevi quindi di soluzione algebrica approcci noti sono:

1. generare e prova

   o si prova ogni possibilità del problema e ricorda la soluzione migliore o aggiungi in modo incrementale articoli (non tutti in una volta) uno per uno con lo stesso metodo. In pratica, ciò che stai facendo ora senza un'euristica adeguata è insolitamente lento. Ma ha la migliore efficienza dello spazio (il primo è molto meglio, ma molto più lento) O(N!)

2. approfittare di ordinare gli elementi in base alle dimensioni

   qualcosa come this è molto più veloce quasi O(N.log(N)) (secondo utilizzato l'ordinamento algoritmo). L'efficienza dello spazio dipende fortemente dall'intervallo di dimensioni e dal conteggio degli articoli.Per le forme rettangolari è questo l'approccio migliore (più veloce e utilizzabile anche per N>1000). Per le forme complesse non è questo un buon modo ma guarda comunque forse si ottiene qualche idea ...

3. uso della rete neurale

   Questo è l'approccio estremamente vaga, senza alcun mandato di soluzione, ma possibile migliore efficienza spazio/rapporto runtime

4. credo ci potrebbe essere qualche approccio campo d'ingresso

   semino alcuni per la generazione di layout grafico. Tutti gli oggetti creano campi (cabina attraente e ripugnante) in modo che si spostino in stato semi-stabile.

   • In un primo momento tutti gli articoli sono in posizioni casuali
   • Quando il movimento si ferma ricordo migliore soluzione e agitare tutti gli elementi un po 'o randomize di nuovo la loro posizione.
   • Ciclo di questo paio di volte

   Questo approccio è molto più veloce Genere e prova e può fornire molto vicino soluzione ad esso, ma può appendere in locale min/max o oscillare se i campi non sono scelto in modo ottimale. Ad esempio, tutti gli oggetti possono avere una forza attrattiva costante tra loro e la forza repulsiva diventa più forte solo quando gli oggetti sono molto vicini. È necessario evitare la sovrapposizione di elementi (sia con una maggiore repulsione che con i test di collisione). Devi anche creare un momento di rotazione, ad esempio con quella forza repulsiva. Differisce su qualsiasi vertice in modo da creare un momento di rotazione (che può allineare automaticamente i lati simili più vicini tra loro). Inoltre puoi avere uno stato semi-stabile con grandi distanze tra gli oggetti e, dopo aver trovato la soluzione migliore, basta disattivare i campi di repulsione in modo che restino uniti. A volte può avere risultati migliori delle volte non ... ecco bell'esempio per il layout grafico calcolo

   • Logic to strategically place items in a container with minimum overlapping connections
   • Demo from the same QA

   E qui risolutore per l'immissione cursori in 2D:

   • How to implement a constraint solver for 2-D geometry?

---

[Edit0] risposta vecchi prima riformulare la questione

non mi è chiaro quello che si vuole raggiungere.

1. hanno immagine SVG e vuole separare le sue parti di regioni rettangolari
   • come riempito come può essere
   • minor spazio vuoto in esse
   • alcun cambiamento di forma nella foto
2. hai una immagine svg e vuoi cambiarne le forme in base ad uno scopo
   • se questo è il caso, un po 'di informazioni aggiuntive è necessaria

[soluzione per 1]

1. creare un elenco di punti per tutta SVG nello spazio SVG globale (tutti i punti sono trasformati)
   • per la linea è necessario aggiungere 2 punti
   • per i rettangoli 4 punti
   • cerchio/ellisse/Bezier/arco ellittica 8 punti
2. trovano centri locali di massa
   • uso classical approach
   • o può accelerare le cose calcolando la densità media di punti per x, asse y separatamente e dopo di ciò basta controllare tutte le combinazioni di posizioni trovate del massimo locale di densità se esse sono realmente centro di sub cluster o no.
3. tutti i sub centro del cluster è il centro della vostra regione
   • ora trovare i punti più lontani, che sono ancora parte del cluster (la sono abbastanza vicino a punti vicini)
   • creare un'area rettangolare che coprire tutti i punti dal sottogruppo.
   • è anche possibile rimuovere tutti i punti utilizzati dalla lista
4. ripetere fro tutti i sotto gruppi validi
   • fino a quando tutti i punti sono utilizzati

altro non preciso ma approccio più semplice è :

1. trova dimensioni SVG
2. crea una mappa planare di svg con una certa precisione per esempio int map [256] [256].
   • dimensione di mappa può essere costante o con lo stesso aspetto di SVG
3. mappa chiara con 0
4. per ogni punto di SVG set correlato punto della mappa 1 (o inc o altro)
5. mappa ora solo segmentate e avrete trovare oggetti
   • dopo la segmentazione si dispone di posizione e le dimensioni di tutti gli oggetti
   • così f inding di riquadri di limitazione dovrebbe essere facile

Answer 2

Si può iniziare con una variante del rettangolo algoritmo di bin-imballaggio e aggiungere la rotazione. C'è un metodo "Ghigliottina bin packer" e puoi scaricare una carta e una libreria su github.