7

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.

Ch3shire
  • 1,095
  • 2
  • 14
  • 39
  • 1
    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? – n. m. could be an AI Dec 28 '16 at 11:33
  • My desired output is to get two polygons which together form one input polygon with hole. – Ch3shire Dec 28 '16 at 22:12
  • Oh so you want to cut the input shape into simple polygons. – n. m. could be an AI Dec 28 '16 at 22:22
  • Yup. Sorry if I didn't state myself clear :) – Ch3shire Dec 29 '16 at 10:23
  • Isn't [this](http://www.boost.org/doc/libs/1_57_0/libs/geometry/doc/html/geometry/reference/algorithms/difference.html) what you are looking for? Or mabye [this](http://www.boost.org/doc/libs/1_62_0/libs/polygon/doc/gtl_polygon_set_concept.htm)? – Steeve Jan 04 '17 at 08:34
  • I tried to use Boost::Polygon, without success so far. I'll try with this `difference` method, didn't test it yet. – Ch3shire Jan 04 '17 at 10:26
  • @Ch3shire Ok, please update us if you find a solution. – Steeve Jan 04 '17 at 16:26

1 Answers1

5

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;
}
Ton van den Heuvel
  • 10,157
  • 6
  • 43
  • 82
  • Do you know how to go the other way round, i.e. from a polygon_set to polygon_with_holes? – lakshayg Mar 03 '18 at 20:46
  • 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. – Ton van den Heuvel Mar 05 '18 at 09:06