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.
Asked
Active
Viewed 1,928 times
7
-
1It'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 Answers
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