C ++: get a list of simple polygons from a polygon with holes

Question

I am struggling with Boost :: Polygon - apparently, he can do everything except what I want. I have several borders describing many polygons and their holes (in 2d space). In general, we can even have a hole in the hole (a smaller polygon in the hole of a larger polygon) or many holes in one polygon. If necessary, I can check which boundary describes the hole and describes the polygon. Sometimes the borders are divided (and do not contain each other), which means that we have many polygons. What I want is a method that gives me a set of simple, polygon-free holes that together form an input “holey” polygon.

Answer 1

This is possible with Boost Polygon. You will need polygon_set_data::get()one that will make a fracture of the hole for you if you move from the concept of a polygon that supports holes to one that does not. See http://www.boost.org/doc/libs/1_65_0/libs/polygon/doc/gtl_polygon_set_concept.htm for details .

The following is an example when we first represent a polygon with a hole, and then convert it to a simple polygon with one ring:

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