Geometry Boost List: Re: [geometry] polygons with holes

Subject: Re: [geometry] polygons with holes
From: Barend Gehrels (barend_at_[hidden])
Date: 2012-01-30 13:40:40

Hi Jeff,

On 29-1-2012 23:58, jeffpoly wrote:
>> Good question. Yes and no. Yes, because you can build with
>> Boost.Geometry primitives. No because it is not available as a standard
>> function and it is not trivial to build yourself.
>> I'll have a look, have done this at least twice before, if one of them
>> was with (a predecessor of) Boost.Geometry it might be of help.
> Thanks, could you please pointer me how could I use this functionality?
>

Hmm, yes and no, I already looked and there is a version within 
Boost.Geometry, assign_parents. But that is (besides in detail) specific 
for the results of the overlay, and is based on two input geometries. 
You will need something like that but not exactly that.

For the rest you could look at:

https://svn.boost.org/svn/boost/trunk/boost/geometry/extensions/gis/io/shapelib/shp_read_object.hpp

which is reading a shapefile (where rings are unorganized), sorts them 
on area, and assigns the parent.

This assumes that:
- clockwise rings are outer rings (area is positive)
- counterclockwise rings are inner rings (area is negative)

If you can assume that, you can use something like this. It is just on 
size, and figuring out which inner ring (negative area) is within which 
outer ring (positive area). Then you're there.

However for a large number of polygons, both positive and negative, this 
will be less performant. In that case better is to use partition, which 
is in Boost.Geometry, but that makes it more complex to implement.

In the sample (shp_read_object) it assumes one exterior ring, but it (or 
something similar) will work for a multi-polygon as well.

Regards, Barend