C++: Get list of simple polygons from polygon with holes

Question

I'm struggling with Boost::Polygon - apparently it can do everything except the thing I want. I have a few boundaries describing set of polygons and their holes (in 2d space). In general we can even have hole in a hole (smaller polygon in hole of a bigger polygon), or many holes in one polygon. If it's necessary I can check which boundary describes a hole and which describes a polygon. Sometimes boundaries are separate (and not containing each other), which means we have many polygons. What I want is a method which gives me a set of simple, not containing any holes polygons, which together form input 'holey' polygon.

Alpine

It's not clear what exactly you want. If your polygons have holes, they are not simple polygons. Suppose you have this polygon with a hole ▣, what kind of output do you want? – Shults

My desired output is to get two polygons which together form one input polygon with hole. – Alpine

Oh so you want to cut the input shape into simple polygons. – Shults

Yup. Sorry if I didn't state myself clear :) – Alpine

Isn't this what you are looking for? Or mabye this? – Goodyear

I tried to use Boost::Polygon, without success so far. I'll try with this difference method, didn't test it yet. – Alpine

@Alpine Ok, please update us if you find a solution. – Goodyear

Answer 1

This is possible with Boost Polygon. You need polygon_set_data::get(), which does the hole fracturing for you in case you convert from a polygon concept supporting 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 more details.

The following is an example, where we represent a polygon with a hole first, then convert it to a simple polygon with only 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;
}

Inexecution

Do you know how to go the other way round, i.e. from a polygon_set to polygon_with_holes? – Libratory

I am not sure whether Boost Polygon supports that natively, but it should not be too difficult to implement this yourself, by searching for the 'fracturing' edges, and remove them. – Inexecution