Boost logo

Boost Users :

Subject: Re: [Boost-users] [Boost.Polygon] support for polygons with holes
From: Björn Piltz (bjornpiltz_at_[hidden])
Date: 2011-09-06 11:22:47

> All functionality is supported for the polygon_with_holes concept. I
> consider it to be the normal case.

Thanks, that's a relief!
I use my own containers and I missed that I had to declare polygon_traits as
well as polygon_with_holes_traits for my PolygonsWithHoles class. Now things
are working like a charm.
I'm very happing being able to map Qt's QPolygon to Boost.Polygon since this
gives me full rendering capabilities.

I do have a couple of issues and I thought I'd let you know. I'm not sure if
they are outside the scope of the library, so I'll let you be the judge of

Is there an easy(and computationally cheaper) way to check if two simple
polygons intersect?
other than: !boost::polygon::empty(a & b). If not, is such functionality

The simplify() algorithm seems to be a bit greedy. I have a hard time
thinking up a small example, but I can see it clearly on some larger
GIS-datasets. The algorithm starts chipping away at some corner, removing
unneeded vertices, but in some cases it doesn't stop until the whole polygon
is gone. It seems to me it should work a bit more like Douglas-Peucker:

Everytime a point P is removed, creating a line between A and B, all
previously removed points between A and B should be checked against the
line, and if any of the points end up to far from the line removal of P is

The way it works now, the accumulated error can be great.

Are there potentially more ways the user can help the library? Right now the
user can override polygon_traits<>::winding(), which is otherwise O(N).
Couldn't the same be done for area, bounding box and concavity. The bounding
box is of course useful for speeding up all boolean operators and knowing
concavity speeds up hit tests ( contains(point_type) ) This could be
calculated in one sweep. No boiler plate code needed if there would be
polygon_default_traits returning winding_unknown, concavity_unknown, etc.

Otherwise, like I said before, it works like a charm.


2011/9/2 Simonson, Lucanus J <lucanus.j.simonson_at_[hidden]>

> Bjorn,
> All functionality is supported for the polygon_with_holes concept. I
> consider it to be the normal case. All you need to do is create a list or
> vector of polygon_with_holes_data<int> and use that instead of
> polygon_data<int> when you get the result out of polygon_set p.
> Regards,
> Luke
> ________________________________
> From: boost-users-bounces_at_[hidden] [mailto:
> boost-users-bounces_at_[hidden]] On Behalf Of Björn Piltz
> Sent: Friday, September 02, 2011 1:39 AM
> To: boost-users_at_[hidden]
> Subject: [Boost-users] [Boost.Polygon] support for polygons with holes
> I'm playing around with Boost.Polygon and I'm wondering what functionality
> is supported for the polygon_with_holes concept. Specifically the boolean
> operators.
> For example, can I create a polygon_set with polygon_with_holes.
> I would like to punch a hole in a polygon and get a polygon with a hole as
> supposed to a key holed contour. Similarily, when combining the following
> rectangles:
> p += rectangle_data<int>(0, 0, 100, 10);
> p += rectangle_data<int>(90, 0, 100, 100);
> p += rectangle_data<int>(0, 90, 100, 100);
> p += rectangle_data<int>(0, 0, 10, 100);
> I would like to end up with
> +-----+
> | |
> | +-+ |
> | | | |
> | +-+ |
> | |
> +-----+
> as opposed to
> +-----+
> | |
> | +-+ |
> | | | |
> | +-+ |
> | | |
> +---+-+
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at