C++ 2D-Tessellationsbibliothek?

Question

Ich habe einige konvexe Polygone (mehr oder weniger) als STL-Punktvektor gespeichert.Ich möchte mosaikieren Zerkleinern Sie sie sehr schnell, am besten in ziemlich gleichmäßig große Stücke und ohne „Späne“.

Ich werde damit einige Objekte in kleine Stücke explodieren lassen.Kennt jemand eine nette Bibliothek, um Polygone zu tesselieren (sie in ein Netz kleinerer konvexer Polygone oder Dreiecke zu unterteilen)?

Ich habe mir einige angesehen, die ich bereits online gefunden habe, aber ich schaffe es nicht einmal, sie zu kompilieren.Diese akademischen Typen legen keinen großen Wert auf Benutzerfreundlichkeit.

Answer 1

CGAL hat Pakete dieses Problem zu lösen. Am besten wäre es wahrscheinlich die 2D-Polygon-Partitionierung zu verwenden Paket. Zum Beispiel könnten Sie y-monotone Partition eines Polygons (arbeitet für nicht-konvexe Polygone, sowie) generieren und Sie würden etwas wie diese:

Die runnning Zeit ist O (n log n).

Im Hinblick auf die Benutzerfreundlichkeit ist dies ein kleines Beispiel-Code ein Zufalls Polygon zu erzeugen und Partitionieren es (basierend auf dieses Handbuch Beispiel ):

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K>                         Traits;
typedef Traits::Point_2                                     Point_2;
typedef Traits::Polygon_2                                   Polygon_2;
typedef std::list<Polygon_2>                                Polygon_list;
typedef CGAL::Creator_uniform_2<int, Point_2>               Creator;
typedef CGAL::Random_points_in_square_2<Point_2, Creator>   Point_generator;   


int main( )
{
   Polygon_2    polygon;
   Polygon_list partition_polys;

   CGAL::random_polygon_2(50, std::back_inserter(polygon),
                      Point_generator(100));

   CGAL::y_monotone_partition_2(polygon.vertices_begin(),
                                polygon.vertices_end(),
                                std::back_inserter(partition_polys));

   // at this point partition_polys contains the partition of the input polygons
   return 0;
}

cgal installieren, wenn Sie auf Fenster sind, können Sie das Installationsprogramm verwenden, um die vorkompilierte Bibliothek zu erhalten, und es gibt Einrichtungen Führungen für jede Plattform, auf diese Seite . Es ist vielleicht nicht die einfachste zu installieren, aber Sie bekommen das am häufigsten verwendete und robuste Computational Geometry Bibliothek gibt es da draußen, und die

Answer 2

poly2tri wie eine wirklich schöne leichte C sieht ++ Bibliothek für 2D Delaunay Triangulation.

Wie balint.miklos in einem Kommentar erwähnt, die Shewchuk Dreieck Paket ist ziemlich gut. Ich habe es selbst viele Male verwendet; es integriert sich gut in Projekte und es besteht die Dreieck ++ ++ C-Schnittstelle. Wenn Sie Splittern vermeiden wollen, dann lassen Dreieck (innen) Steiner Punkte hinzufügen, so dass Sie ein qualitativ hochwertiges Mesh erzeugen (in der Regel eine eingeschränkte konforme Delaunay-Triangulation).

Wenn Sie nicht die ganze GCAL in Ihre App bauen wollen -. Dies ist wahrscheinlich einfacher zu implementieren

http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

Ich habe einen Blick in das gleiche Problem gerade erst begonnen und ich überlege voronoi Tessellation. Das ursprüngliche Polygon wird eine Streuung von halb zufälligen Punkten erhalten, die die Zentren der Voronoi-Zellen sein, die gleichmäßiger verteilte sie je regelmäßiger die Zellen so bemessen sein, aber sie sollten nicht anders in einem perfekten Gitter werden die inneren Polygone werden alle gleich aussehen. Das erste, was ist in der Lage sein, jene Zelle Zentrum erzeugen Punkte- sie über den Begrenzungsrahmen des Source-Polygon zu erzeugen und einen Innen / Außen-Test sollte nicht allzu schwer sein.

Die voronoi Kanten sind die gepunkteten Linien in diesem Bild, und sind eine Art der Ergänzung der Delaunay-Triangulation. Alle scharfen Dreieck Punkte abgestumpft:

-Boost hat einige voronoi Funktionalität: http://www.boost.org/doc/ libs / 1_55_0 / libs / Polygon / doc / voronoi_basic_tutorial.htm

Der nächste Schritt ist die Erstellung des voronoi Polygone. Voro ++ http://math.lbl.gov/voro++/ ist 3D-orientiert, aber es wird an anderer Stelle vorgeschlagen dass etwa 2d Struktur funktionieren wird, aber viel langsamer als Software auf 2D voronoi orientiert. Das andere Paket, das viel besser als ein zufälliges akademische Homepage Waise Projekt sein aussieht, ist https://github.com/ aewallin / openvoronoi .

Es sieht aus wie OpenCV Unterstützung in diese Richtung etwas zu tun pflegen, aber es veraltet ist (aber das c-api noch funktioniert?). cv :: distTransform noch aufrechterhalten wird, arbeitet aber auf Pixel und erzeugt Ausgangspixel nicht Ecken und Kanten Polygondatenstrukturen, aber für meine Bedürfnisse, wenn nicht von Ihnen ausreichend sein.

Ich werde diese einmal aktualisieren Ich habe gelernt, mehr.

Ein bisschen mehr Details zu Ihrer gewünschten Ein- und Ausgabe könnten hilfreich sein.

Wenn Sie beispielsweise nur versuchen, die Polygone in Dreiecke umzuwandeln, würde wahrscheinlich ein Dreiecksfächer funktionieren.Wenn Sie versuchen, ein Polygon in kleine Stücke zu schneiden, könnten Sie eine Art Marschquadrate implementieren.

---

Okay, ich habe eine schlechte Annahme getroffen – ich ging davon aus, dass marschierende Quadrate eher marschierenden Würfeln ähneln würden.Es stellt sich heraus, dass es ganz anders ist und überhaupt nicht das, was ich meinte.:|

Um Ihre Frage direkt zu beantworten: Ich kenne keine einfache Bibliothek, die das tut, was Sie suchen.Ich stimme der Benutzerfreundlichkeit von CGAL zu.

Der Algorithmus, den ich mir vorgestellt habe, bestand im Wesentlichen darin, Polygone durch Linien zu teilen, wobei die Linien ein Gitter darstellen, sodass man hauptsächlich Quader erhält.Wenn Sie einen Polygonlinien-Schnittpunkt hätten, wäre die Implementierung einfach.Eine andere Möglichkeit, dieses Problem zu lösen, besteht darin, das 2D-Polygon wie eine Funktion zu behandeln und ein Punktegitter zu überlagern.Dann machen Sie einfach etwas Ähnliches wie marschierende Würfel.Wenn alle 4 Punkte im Polygon liegen, erstellen Sie ein Viereck, wenn 3 Punkte im Polygon liegen, erstellen Sie ein Dreieck, 2 Punkte im Polygon, erstellen Sie ein Rechteck usw.Wahrscheinlich übertrieben.Wenn Sie leicht unregelmäßig aussehende Polygone wünschen, können Sie die Positionen der Gitterpunkte zufällig festlegen.

Andererseits könnten Sie eine Unterteilung im Catmull-Clark-Stil vornehmen, aber die Glättung weglassen.Der Algorithmus besteht im Wesentlichen darin, dass Sie einen Punkt am Schwerpunkt und in der Mitte jeder Kante hinzufügen.Dann erstellen Sie für jede Ecke des ursprünglichen Polygons ein neues kleineres Polygon, das den Kantenmittelpunkt vor der Ecke, die Ecke, den nächsten Kantenmittelpunkt und den Schwerpunkt verbindet.Dadurch wird der Raum kachelt und weist ähnliche Winkel wie Ihr Eingabepolygon auf.

Es gibt also viele Optionen, und ich mag Brainstorming-Lösungen, aber ich habe immer noch keine Ahnung, wofür Sie das verwenden möchten.Sollen dadurch zerstörbare Netze geschaffen werden?Führen Sie eine Netzverarbeitung durch, die kleinere Elemente erfordert?Versuchen Sie, Gouraud-Shading-Artefakte zu vermeiden?Läuft das als Vorprozess oder in Echtzeit?Wie wichtig ist Genauigkeit?Mehr Informationen würden zu besseren Vorschlägen führen.

Wenn Sie konvexe Polygone haben, und du bist nicht zu gehangen auf Qualität, dann ist das wirklich einfach - nur tun? Ohr Clipping . Keine Sorge, es ist nicht O (n ^ 2) für konvexe Polygone. Wenn Sie dies tun naiv (das heißt, um die Ohren Clip, wie Sie sie finden), dann werden Sie ein Dreieck Fan zu bekommen, der ein bisschen ziehen, wenn Sie versuchen, Splittern zu vermeiden. Zwei triviale Heuristik, die die Triangulation verbessern kann, ist zu

1. sortieren Ohren, oder wenn das zu langsam
2. Wählen Sie ein Ohr in zufälliger Reihenfolge.

Wenn Sie eine robustere Triangulator wollen basierend auf Ohr Clipping Besuche FIST .

Answer 3

poly2tri wie eine wirklich schöne leichte C sieht ++ Bibliothek für 2D Delaunay Triangulation.

Answer 4

Wie balint.miklos in einem Kommentar erwähnt, die Shewchuk Dreieck Paket ist ziemlich gut. Ich habe es selbst viele Male verwendet; es integriert sich gut in Projekte und es besteht die Dreieck ++ ++ C-Schnittstelle. Wenn Sie Splittern vermeiden wollen, dann lassen Dreieck (innen) Steiner Punkte hinzufügen, so dass Sie ein qualitativ hochwertiges Mesh erzeugen (in der Regel eine eingeschränkte konforme Delaunay-Triangulation).

Answer 5

Wenn Sie nicht die ganze GCAL in Ihre App bauen wollen -. Dies ist wahrscheinlich einfacher zu implementieren

http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

Answer 6

Ich habe einen Blick in das gleiche Problem gerade erst begonnen und ich überlege voronoi Tessellation. Das ursprüngliche Polygon wird eine Streuung von halb zufälligen Punkten erhalten, die die Zentren der Voronoi-Zellen sein, die gleichmäßiger verteilte sie je regelmäßiger die Zellen so bemessen sein, aber sie sollten nicht anders in einem perfekten Gitter werden die inneren Polygone werden alle gleich aussehen. Das erste, was ist in der Lage sein, jene Zelle Zentrum erzeugen Punkte- sie über den Begrenzungsrahmen des Source-Polygon zu erzeugen und einen Innen / Außen-Test sollte nicht allzu schwer sein.

Die voronoi Kanten sind die gepunkteten Linien in diesem Bild, und sind eine Art der Ergänzung der Delaunay-Triangulation. Alle scharfen Dreieck Punkte abgestumpft:

-Boost hat einige voronoi Funktionalität: http://www.boost.org/doc/ libs / 1_55_0 / libs / Polygon / doc / voronoi_basic_tutorial.htm

Der nächste Schritt ist die Erstellung des voronoi Polygone. Voro ++ http://math.lbl.gov/voro++/ ist 3D-orientiert, aber es wird an anderer Stelle vorgeschlagen dass etwa 2d Struktur funktionieren wird, aber viel langsamer als Software auf 2D voronoi orientiert. Das andere Paket, das viel besser als ein zufälliges akademische Homepage Waise Projekt sein aussieht, ist https://github.com/ aewallin / openvoronoi .

Es sieht aus wie OpenCV Unterstützung in diese Richtung etwas zu tun pflegen, aber es veraltet ist (aber das c-api noch funktioniert?). cv :: distTransform noch aufrechterhalten wird, arbeitet aber auf Pixel und erzeugt Ausgangspixel nicht Ecken und Kanten Polygondatenstrukturen, aber für meine Bedürfnisse, wenn nicht von Ihnen ausreichend sein.

Ich werde diese einmal aktualisieren Ich habe gelernt, mehr.

Answer 7

Ein bisschen mehr Details zu Ihrer gewünschten Ein- und Ausgabe könnten hilfreich sein.

Wenn Sie beispielsweise nur versuchen, die Polygone in Dreiecke umzuwandeln, würde wahrscheinlich ein Dreiecksfächer funktionieren.Wenn Sie versuchen, ein Polygon in kleine Stücke zu schneiden, könnten Sie eine Art Marschquadrate implementieren.

---

Okay, ich habe eine schlechte Annahme getroffen – ich ging davon aus, dass marschierende Quadrate eher marschierenden Würfeln ähneln würden.Es stellt sich heraus, dass es ganz anders ist und überhaupt nicht das, was ich meinte.:|

Um Ihre Frage direkt zu beantworten: Ich kenne keine einfache Bibliothek, die das tut, was Sie suchen.Ich stimme der Benutzerfreundlichkeit von CGAL zu.

Der Algorithmus, den ich mir vorgestellt habe, bestand im Wesentlichen darin, Polygone durch Linien zu teilen, wobei die Linien ein Gitter darstellen, sodass man hauptsächlich Quader erhält.Wenn Sie einen Polygonlinien-Schnittpunkt hätten, wäre die Implementierung einfach.Eine andere Möglichkeit, dieses Problem zu lösen, besteht darin, das 2D-Polygon wie eine Funktion zu behandeln und ein Punktegitter zu überlagern.Dann machen Sie einfach etwas Ähnliches wie marschierende Würfel.Wenn alle 4 Punkte im Polygon liegen, erstellen Sie ein Viereck, wenn 3 Punkte im Polygon liegen, erstellen Sie ein Dreieck, 2 Punkte im Polygon, erstellen Sie ein Rechteck usw.Wahrscheinlich übertrieben.Wenn Sie leicht unregelmäßig aussehende Polygone wünschen, können Sie die Positionen der Gitterpunkte zufällig festlegen.

Andererseits könnten Sie eine Unterteilung im Catmull-Clark-Stil vornehmen, aber die Glättung weglassen.Der Algorithmus besteht im Wesentlichen darin, dass Sie einen Punkt am Schwerpunkt und in der Mitte jeder Kante hinzufügen.Dann erstellen Sie für jede Ecke des ursprünglichen Polygons ein neues kleineres Polygon, das den Kantenmittelpunkt vor der Ecke, die Ecke, den nächsten Kantenmittelpunkt und den Schwerpunkt verbindet.Dadurch wird der Raum kachelt und weist ähnliche Winkel wie Ihr Eingabepolygon auf.

Es gibt also viele Optionen, und ich mag Brainstorming-Lösungen, aber ich habe immer noch keine Ahnung, wofür Sie das verwenden möchten.Sollen dadurch zerstörbare Netze geschaffen werden?Führen Sie eine Netzverarbeitung durch, die kleinere Elemente erfordert?Versuchen Sie, Gouraud-Shading-Artefakte zu vermeiden?Läuft das als Vorprozess oder in Echtzeit?Wie wichtig ist Genauigkeit?Mehr Informationen würden zu besseren Vorschlägen führen.

Answer 8

Wenn Sie konvexe Polygone haben, und du bist nicht zu gehangen auf Qualität, dann ist das wirklich einfach - nur tun? Ohr Clipping . Keine Sorge, es ist nicht O (n ^ 2) für konvexe Polygone. Wenn Sie dies tun naiv (das heißt, um die Ohren Clip, wie Sie sie finden), dann werden Sie ein Dreieck Fan zu bekommen, der ein bisschen ziehen, wenn Sie versuchen, Splittern zu vermeiden. Zwei triviale Heuristik, die die Triangulation verbessern kann, ist zu

1. sortieren Ohren, oder wenn das zu langsam
2. Wählen Sie ein Ohr in zufälliger Reihenfolge.

Wenn Sie eine robustere Triangulator wollen basierend auf Ohr Clipping Besuche FIST .