Ich suche nach einem Packalgorithmus, der ein reguläres Polygon in Rechtecke und Rechtecke reduziert. Der Algorithmus sollte versuchen, so wenig Formen wie möglich zu verwenden, und sollte relativ leicht zu implementieren sein (angesichts der Schwierigkeit der Herausforderung).Effizienter Packungsalgorithmus für reguläre Polygone
Wenn möglich, sollte die Antwort auf diese Frage die allgemeinen Heuristiken im vorgeschlagenen Algorithmus erklären.
Ich denke, die Antwort ist ziemlich einfach für regulären Polygone.
Suchen Sie eine Symmetrieachse und zeichnen Sie eine Linie zwischen jedem Eckpunkt und seinem Spiegel. Dies teilt das Polygon in Trapeze. Jedes Trapez kann in ein Rechteck und zwei rechte Dreiecke umgewandelt werden.
Sie könnten etwas mehr Anerkennung erhalten, wenn Sie beweisen, dass dies die Mindestanzahl an Kacheln ergibt. :) – Svante
Ich glaube jetzt, das ist eigentlich optimal :-) – Mau
Nein. Es ist nicht immer optimal. Nehmen Sie zum Beispiel ein normales Sechseck mit zwei Seiten parallel zur Achse x = 0. Dann erzeugt dieser Algorithmus 2 Rechtecke und 4 rechte Dreiecke, aber 1 Rechteck und 4 Dreiecke wären ausreichend. Trotzdem ist die Lösung wahrscheinlich gut genug und einfach zu implementieren. – abc
Es sind nicht speziell Rechtecke + Rechte Dreiecke, aber ein guter Forschungspunkt für die Untersuchung von tesselierenden Polygonen ist Voronoi Diagrams and Delaunay Triangulations und here und here.
In der Tat, wenn "gerade Dreiecke" gut genug ist, sind diese garantiert, für Sie zu triangulieren, und Sie können jedes Dreieck in zwei richtige Dreiecke teilen, wenn Sie diese wirklich brauchen. Oder Sie können "Spitzen" von Dreiecken abhacken, um mehr rechte Dreiecke und einige Rechtecke aus den rechten Dreiecken zu machen.
Sie können auch versuchen, ear-clipping, entweder durch radiales Sweeping, wenn Sie wissen, dass Sie ziemlich regelmäßige Polygone haben, oder durch "Clipping der größten konvexen Chunk" aus. Dann teilen Sie jedes verbleibende Dreieck in zwei, um rechte Dreiecke zu erstellen.
polygon http://static.eruciform.com/images/polygon.png
Sie könnten versuchen, weniger Pausen durch Kehren einen Weg zu machen und dann das andere ein Trapez zu machen und teilen Sie es anders, aber Sie dann einen Scheck tun müssen, um sicherzustellen, dass Ihre Sweep-line hasn Ich habe nicht irgendwo eine andere Linie überquert. Du kannst immer mit dem Ohr schneiden, sogar mit etwas, das praktisch fraktal ist.
Dies schafft jedoch manchmal sehr schlanke Dreiecke. Sie können Heuristiken wie "Nimm den größten" ausführen, anstatt kontinuierlich entlang der Kante zu schneiden, aber das dauert länger und nähert sich O (n^2). Delaunay/Vornoi wird es in den meisten Fällen schneller machen, mit weniger schlanken Dreiecken.
Absolut müssen Rechtecke und Rechte Dreiecke sein. Ich weiß, es klingt seltsam, aber es ist eine Benutzeranforderung. – Steve
aktualisiert. Sie können jedes Dreieck recht einfach in Rechtecke und Rechtecke umwandeln. – eruciform
Delaunay-Triangulationen sind hier nicht ideal, da sie zusätzliche, unnötige Punkte in der Mitte einbringen. Jeder dieser internen Punkte kann an einen benachbarten Polygonscheitel "gezogen" werden, und Sie erhalten einen kleineren Satz von Dreiecken. –
Sie können versuchen, "Ausschneiden" the largest rectangle that can fit in the polygon, einige Reste übriglassen. Wiederholen Sie das Ausschneiden von Rechtecken auf den Resten, bis Sie mit dreieckigen Stücken enden. Dann können Sie sie bei Bedarf in zwei rechte Dreiecke aufteilen. Ich weiß nicht, ob dies immer zu Lösungen führt, die dir die wenigsten Rechtecke und Rechtecke geben.
Ich denke, das ist auch keine gute Idee: Weg essen so viel Fläche wie möglich mit dem ersten Rechteck wird nicht verlassen Sie mit der "einfachsten" Form danach. – Mau
war nicht klar, was seine Anforderungen waren. mindestens die gesamten Formen oder das meiste Gebiet in den wenigsten Formen ... – eruciform
Für regelmäßige Polygone jedoch würde es Ihnen noch "nette" Formen geben. Auch hier weiß ich nicht, ob Sie dadurch die "optimalsten" Lösungen erhalten. –
ist dies für eine Algorithmen-Klasse oder einer Klasse Computergrafik? – eruciform
Es ist nicht für eine Klasse. Ich bin nicht in der Schule. – Steve
In der Tat könnte ich bereit sein, jemandem, der die Frage gut beantworten kann, ein Stellenangebot zu geben, wenn sie für das iPhone, Mac-Desktop und .net programmieren können. ;) – Steve