C++ - 2D-tessellation-Bibliothek?

CGAL Pakete um dieses problem zu lösen. Am besten wäre wohl die Verwendung der 2D-Polygon-Partitionierung Paket. Zum Beispiel könnten Sie generieren y-monotone-partition von einem polygon (funktioniert für nicht-konvexen Polygonen), und Sie bekommen würde, so etwas wie dieses:

y-monoyone-Partitionierung http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Partition_2/Trier_opt_cvx.gif
y-monoyone-Partitionierung http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Partition_2/Idar-Oberstein_appx_cvx.gif

Den runnning Zeit O(n log n).

In Bezug auf die Benutzerfreundlichkeit dies ist ein kleiner Beispiel code-Generierung eine zufällige polygon und Partitionierung (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;
}

Installieren cgal, wenn Sie in windows Sie können den installer verwenden, um die vorkompilierte Bibliothek, und es sind Installations-Anleitungen für jede Plattform auf auf dieser Seite. Es ist vielleicht nicht die am einfachsten zu installieren, aber Sie bekommen die die meisten verwendet und robuste computational geometry-Bibliothek dort gibt, und die cgal-mailing-Liste ist sehr hilfreich um Fragen zu beantworten...

InformationsquelleAutor balint.miklos

Als balint.miklos erwähnt in einem Kommentar oben, der Shewchuk ' s Dreieck - Paket ist ziemlich gut. Ich habe es selbst viele Male; es integriert sich schön in die Projekte und es wird die Dreieck++ C++ - Schnittstelle. Wenn Sie vermeiden möchten, Splitter, ermöglichen dann die Dreieck (innen) Steiner-Punkte, so dass Sie erzeugen eine hochwertige mesh (in der Regel eine eingeschränkte konforme delaunay-triangulation).

InformationsquelleAutor Victor Liu

Ich habe gerade begonnen, einen Blick in dieses gleiche problem und ich überlege mir, voronoi-tessellation. Das original polygon erhalten eine Streuung von halb-zufälligen Punkten, die die Zentren der voronoi-Zellen, die mehr gleichmäßig verteilt werden Sie regelmäßig die Größe der Zellen, aber Sie sollte nicht in einem perfekten Gitter sonst die inneren Polygone werden alle gleich Aussehen. So die erste Sache ist, um in der Lage zu erzeugen, die Zell-Mittelpunkte - Generierung über die bounding-box des Quell-polygon und ein Interieur/Exterieur-test sollte nicht allzu schwer sein.

Die voronoi-Kanten sind die gestrichelten Linien in diesem Bild, und sind sozusagen die Ergänzung der delaunay-triangulation. Alle scharfen Dreieck stumpf:

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 der voronoi-Polygone. Voro++ http://math.lbl.gov/voro++/ ist 3D-orientiert, aber es wird vorgeschlagen, die anderswo, etwa 2d-Struktur funktionieren wird, aber viel langsamer als die software-orientiert, 2D-voronoi. Das andere Paket, das sieht um einiges besser sein als eine zufällige akademischen homepage Waisen-Projekt ist https://github.com/aewallin/openvoronoi.

Sieht es aus wie OpenCV verwendet, um den support etwas tun in diese Richtung, aber es ist veraltet (aber das c-api noch funktioniert?). cv::distTransform ist noch erhalten, aber funktioniert auf Pixel und generiert für die pixel-Ausgabe, keine Ecken und Kante, polygon-Daten-Strukturen, aber kann ausreichend sein, für meine Bedürfnisse, wenn nicht deins.

Ich werde diese zu aktualisieren, sobald ich habe mehr gelernt.

InformationsquelleAutor Lucas W

Wenn Sie konvexe Polygone, und Sie sind nicht zu aufgehängt auf Qualität, dann ist das wirklich einfach - einfach tun ear clipping. Keine Sorge, es ist nicht O(n^2) für konvexe Polygone. Wenn Sie dies tun, naiv (d.h., Sie clip die Ohren, als Sie Sie finden), dann wirst du ein Dreieck-fan, das ist ein bisschen ein ziehen, wenn Sie versuchen zu vermeiden Splittern. Zwei triviale Heuristiken, die zur Verbesserung der triangulation sind

1. Art der Ohren, oder wenn das zu langsam
2. Wählen Sie ein Ohr nach dem Zufallsprinzip.

Wenn Sie möchten, eine robustere triangulator basierend auf ear clipping, check-out FAUST.

InformationsquelleAutor IV.