Come triangolare i poligoni in Boost?

Question

Qual è il modo migliore per triangolare un poligono con Boost?

Io uso Boost.polygon.

Il mio attuale algoritmo:

1. calcolare un diagramma di Voronoi dai miei vertici del poligono.

2. Crea una diretta poligono bordo per ogni cella-bordo (questo creerà due bordi poligono diretto per cellula-bordo)

3. iterare su tutti i bordi creati per creare triangoli (non banali)

Qualche soluzione migliore?

Modifica: ho appena realizzato che è probabilmente possibile attraversare le celle in un modo speciale per creare direttamente i triangoli (3 celle vicine creano un triangolo).

Answer 1

L'idea principale è quella di iterare attraverso i vertici di Voronoi e creare un triangolo dai punti di generazione di ogni incidente di cella sul vertice di Voronoi. Nel caso di vertice degenerato con grado> 3, allora dovrai generare più di un triangolo, ma questo è fatto facilmente usando una ventola triangolare.

Utilizzando Boost :: Poligono:

#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()); 
} 

Vedi anche https://computergraphics.stackexchange.com/questions/1815/how-to-triangulate-from-a-vorono%C3%AF-diagram per più di fondo sul problema.