Wie trianguliere Polygone in Boost?

Question

Was ist der beste Weg, ein Polygon mit Boost zu triangulieren?

Ich verwende Boost.polygon.

Mein aktueller Algorithmus:

1. Compute ein Voronoi-Diagramm von meinen Polygon-Scheitelpunkten.

2. Erstellen eines gerichteten Polygon-Kante für jede Zelle Kante (dies wird zwei pro Zelle-edge Polygonkante gerichtet erstellen)

3. Iterieren über alle bestehenden Kanten Dreiecke (nicht trivial)

erstellen

Jede bessere Lösung?

Edit: Ich habe gerade gemerkt, dass es wahrscheinlich möglich ist, durch die Zellen auf eine spezielle Weise zu gehen, um die Dreiecke direkt zu erzeugen (3 Nachbarzellen erzeugen ein Dreieck).

Answer 1

Die Hauptidee besteht darin, durch die Voronoi-Scheitelpunkte zu iterieren und aus den erzeugenden Punkten jeder Zelle, die auf den Voronoi-Scheitel trifft, ein Dreieck zu erzeugen. Im Falle eines entarteten Scheitelpunktes mit Grad> 3 müssen Sie mehr als ein Dreieck erzeugen, aber das ist leicht mit einem Dreiecksfächer möglich.

mit boost :: Polygon:

#include "boost/polygon/voronoi.hpp" 

std::vector<Point> vertices; 
// add your input vertices 

boost::polygon::voronoi_diagram<double> vd; 
boost::polygon::construct_voronoi(vertices.begin(), vertices.end(), &vd); 

for (const auto& vertex: vd.vertices()) { 
    std::vector<Point> triangle; 
    auto edge = vertex.incident_edge(); 
    do { 
     auto cell = edge->cell(); 
     assert(cell->contains_point()); 

     triangle.push_back(vertices[cell->source_index()]); 
     if (triangle.size() == 3) { 
      // process output triangles 
      std::cout << "Got triangle:" << triangle << std::endl; 
      triangle.erase(triangle.begin() + 1); 
     } 

     edge = edge->rot_next(); 
    } while (edge != vertex.incident_edge()); 
} 

Siehe auch https://computergraphics.stackexchange.com/questions/1815/how-to-triangulate-from-a-vorono%C3%AF-diagram für mehr Hintergrundinformationen über das Problem.