Làm thế nào để triangulate đa giác trong Boost?

Question

Cách tốt nhất để triangulate một đa giác với Boost là gì?

Tôi sử dụng Boost.polygon.

thuật toán hiện tại của tôi:

1. Tính một sơ đồ Voronoi từ đỉnh đa giác của tôi.

2. Tạo một đạo diễn đa giác tiến cho mỗi biên cell (điều này sẽ tạo ra hai đạo diễn cạnh đa giác mỗi biên cell)

3. lặp qua tất cả các cạnh tạo ra để tạo ra hình tam giác (không nhỏ)

Bất kỳ giải pháp nào tốt hơn?

Chỉnh sửa: Tôi vừa nhận ra rằng có thể đi qua các ô theo cách đặc biệt để tạo hình tam giác trực tiếp (3 ô lân cận tạo tam giác).

Answer 1

Ý tưởng chính là lặp qua các đỉnh Voronoi và tạo một hình tam giác từ các điểm sinh ra của mỗi sự cố tế bào trên đỉnh Voronoi. Trong trường hợp đỉnh thoái hóa với độ> 3 thì bạn sẽ cần phải tạo nhiều hơn một hình tam giác, nhưng điều đó có thể dễ dàng thực hiện bằng cách sử dụng một quạt hình tam giác.

Sử dụng 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()); 
} 

Xem thêm https://computergraphics.stackexchange.com/questions/1815/how-to-triangulate-from-a-vorono%C3%AF-diagram cho nền thêm về vấn đề này.