Sto cercando un algoritmo di imballaggio che ridurrà un poligono regolare in rettangoli e triangoli rettangoli. L'algoritmo dovrebbe tentare di utilizzare il minor numero di forme possibili e dovrebbe essere relativamente facile da implementare (vista la difficoltà della sfida).Algoritmo di imballaggio efficiente per poligoni regolari
Se possibile, la risposta a questa domanda dovrebbe spiegare l'euristica generale utilizzata nell'algoritmo suggerito.
Penso che la risposta sia abbastanza semplice per poligoni regolari.
Trova un asse di simmetria e traccia una linea tra ciascun vertice e il suo specchio. Questo divide il poligono in trapezi. Ogni trapezio può essere trasformato in un rettangolo e due triangoli rettangoli.
Potresti ottenere un credito extra dimostrando che questo produce il numero minimo di tessere. :) – Svante
Ora credo che sia davvero ottimale :-) – Mau
No. Non è sempre ottimale. Prendiamo ad esempio un esagono regolare con due lati paralleli all'asse x = 0. Quindi questo algoritmo genera 2 rettangoli e 4 triangoli rettangoli, ma 1 rettangolo e 4 triangoli sarebbero sufficienti. Tuttavia, la soluzione è probabilmente abbastanza buona e facile da implementare. – abc
Non è specificamente rettangoli + triangoli rettangoli, ma un buon punto di ricerca per esaminare i poligoni di tesselating è Voronoi Diagrams and Delaunay Triangulations e here e here.
Infatti, se "i triangoli giusti" sono abbastanza buoni, questi sono garantiti per triangolare per te, e puoi sempre dividere qualsiasi triangolo in due triangoli rettangoli, se davvero ne hai bisogno. Oppure puoi tagliare "punte" di triangoli per rendere più triangoli rettangoli e alcuni rettangoli dai triangoli rettangoli.
Puoi anche provare ear-clipping, spazzando radialmente, se sai di avere poligoni abbastanza regolari, o "ritaglia il pezzo più grande convesso". Quindi, dividi ciascun triangolo rimanente in due per creare triangoli rettangoli.
polygon http://static.eruciform.com/images/polygon.png
Si potrebbe provare a fare meno pause da spazzare in un modo e poi l'altro per fare un trapezio e dividere in modo diverso, ma è quindi necessario fare un controllo per assicurarsi che il vostro spazzata-line hasn ho attraversato un'altra linea da qualche parte. Puoi sempre agganciare le orecchie, anche con qualcosa di praticamente frattale.
Tuttavia, questo a volte crea triangoli molto sottili. È possibile eseguire l'euristica, ad esempio "prendi il più grande", invece di tagliare continuamente lungo il bordo, ma ciò richiede più tempo, avvicinandosi a O (n^2). Delaunay/Vornoi lo farà più rapidamente nella maggior parte dei casi, con triangoli meno sottili.
Assolutamente devono essere rettangoli e triangoli rettangoli. So che sembra strano, ma è un requisito dell'utente. – Steve
aggiornato. puoi trasformare qualsiasi triangolo in triangoli e rettangoli rettangoli abbastanza facilmente. – eruciform
Le triangolazioni di Delaunay non sono ideali qui perché introducono punti aggiuntivi e non necessari nel mezzo. Ognuno di questi punti interni può essere "trascinato" su un vertice del poligono adiacente e ti rimane una serie più piccola di triangoli.Aggiornamento –
Puoi provare a "ritagliare" the largest rectangle that can fit in the polygon, lasciando dietro alcuni avanzi. Continua a ripetere il taglio dei rettangoli sugli avanzi, finché non finisci con pezzi triangolari. Quindi, se necessario, puoi dividerli in due triangoli rettangoli. Non so se questo produrrà sempre soluzioni che ti daranno la minima quantità di rettangoli e triangoli rettangoli.
Penso che neanche questa sia una buona idea: mangiare via quanta più superficie possibile con il primo rettangolo non ti lascerà più con la forma "più semplice" in seguito. – Mau
non era chiaro quali fossero le sue esigenze. almeno le forme totali o la maggior parte dell'area in meno forme ... – eruciform
Tuttavia, per i poligoni regolari, ti darebbe comunque forme "belle". Ancora una volta, non so se questo ti darà le soluzioni "più ottimali". –
è questo per una classe di algoritmi o di una classe di computer grafica? – eruciform
Non è per una classe. Non sono a scuola. – Steve
In effetti, potrei essere disposto a dare a qualcuno che può rispondere alla domanda una buona offerta di lavoro se possono programmare per iPhone, Mac desktop e .net. ;) – Steve