C++: Получить список простых полигонов из многоугольника с отверстиями

Question

Я борюсь с Boost :: Polygon - видимо, он может делать все, кроме того, что я хочу. У меня есть несколько границ, описывающих множество полигонов и их дырок (в 2d-пространстве). В общем, мы можем даже иметь отверстие в отверстии (меньший многоугольник в отверстии большего полигона) или много отверстий в одном полигоне. Если это необходимо, я могу проверить, какая граница описывает отверстие и описывает многоугольник. Иногда границы разделены (и не содержат друг друга), что означает, что у нас много полигонов. То, что я хочу, - это метод, который дает мне набор простых, не содержащих никаких многоугольников дыр, которые вместе образуют входной «дырявый» многоугольник.

Answer 1

Это возможно с помощью Boost Polygon. Вам понадобится polygon_set_data::get(), который сделает перелом отверстия для вас на случай, если вы перейдете из концепции многоугольника, поддерживающей отверстия, к той, которая этого не делает. См.: http://www.boost.org/doc/libs/1_65_0/libs/polygon/doc/gtl_polygon_set_concept.htm для более подробной информации.

Ниже приведен пример, где мы представляем многоугольник с отверстием, а затем преобразовать его в простой многоугольник только с одним кольцом:

#include <boost/polygon/polygon.hpp> 

namespace bp = boost::polygon; 

int main(void) 
{ 
    using SimplePolygon = bp::polygon_data<int>; 
    using ComplexPolygon = bp::polygon_with_holes_data<int>; 
    using Point = bp::point_data<int>; 
    using PolygonSet = bp::polygon_set_data<int>; 
    using SimplePolygons = std::vector<bp::polygon_data<int>>; 

    using namespace boost::polygon::operators; 

    std::vector<Point> points{{5, 0}, {10, 5}, {5, 10}, {0, 5}}; 

    ComplexPolygon p; 
    bp::set_points(p, points.begin(), points.end()); 

    { 
    std::vector<Point> innerPoints{{4, 4}, {6, 4}, {6, 6}, {4, 6}}; 

    std::vector<SimplePolygon> inner(1, SimplePolygon{}); 
    bp::set_points(inner.front(), innerPoints.begin(), innerPoints.end()); 
    bp::set_holes(p, inner.begin(), inner.end()); 
    } 

    PolygonSet complexPolygons; 
    complexPolygons += p; 

    SimplePolygons simplePolygons; 
    complexPolygons.get<SimplePolygons>(simplePolygons); 

    std::cout << "Fractured:\n"; 
    for (const auto& polygon : simplePolygons) 
    { 
    for (const Point& p : polygon) 
    { 
     std::cout << '\t' << std::to_string(p.x()) << ", " << std::to_string(p.y()) 
       << '\n'; 
    } 
    } 

    return 0; 
}