Boostでポリゴンを三角形分割する方法は？

Question

ブーストでポリゴンを三角形分割する最良の方法は何ですか？

私はBoost.polygonを使用します。

私の現在のアルゴリズム：

1. は私のポリゴンの頂点からボロノイ図を計算します。

2. （これはセル端当たり2つの有向ポリゴンエッジを作成する）三角形を作成するために作成されたすべてのエッジ上

3. 反復（些細なことではない）

を各セル端のための1つの有向ポリゴンエッジを作成します

もっと良い解決方法はありますか？

編集：私はちょうど三角形を直接作成するために特別な方法でセルを歩くことが可能であることに気付きました（3つの隣接セルが三角形を作成します）。

Answer 1

主なアイデアは、ボロノイ頂点を反復し、ボロノイ頂点に入射する各セルの生成点から三角形を作成することです。次数> 3の縮退頂点の場合は、複数の三角形を生成する必要がありますが、三角形のファンを使用すると簡単にできます。ブースト::ポリゴン使用

：

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

は、問題の詳細な背景のためにもhttps://computergraphics.stackexchange.com/questions/1815/how-to-triangulate-from-a-vorono%C3%AF-diagram参照してください。