Re: [Boost-users] [Boost.Polygon] support for polygons with holes

Subject: Re: [Boost-users] [Boost.Polygon] support for polygons with holes
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2011-09-08 13:26:27

Björn Piltz wrote:
>> 	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'm glad to hear it.  For some reason this email ended up misidentified as spam and went to my Junk E-mail folder, so please excuse the lateness of my response.

> 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 that.  
> 
> 1.
> 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 planned? 

You should check if their bounding boxes intersect first and then do the expensive check only if there is intersection between the bounding boxes.

> 2.
> 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 rejected   
> 
> The way it works now, the accumulated error can be great.

Yes, I see your point.  In my testing on CAM data that contained a large number of nearly colinear line segments as an artifact of meshing in addition to the sharp angles of man made geometry the operation seemed to be performing well removing the artifact vertices but retaining the ones that were desired features of the figure, however, I can imagine that for GIS data things could turn out much different since all vertices would be qualitatively similar.  The way I implemented the simplify operation the threshold is interpreted as a lower bound instead of an upper bound, which makes the result unpredictable.

> 3.
> 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.       

It is easy to imagine a polygon object that caches its area and bounding box.  You can override any free function in the library (like area()) by defining your own overload of the function that accepts your type, or partial specialization for your specific type.  Frequently the compiler fails to inline the accessor functions for simple data structres like point or rectangle resulting in less-than-zero-cost abstraction.  We address this (when benchmarking shows it is a problem) by overloading or partial specialization of the free functions that use the accessors through the traits to instead access the data type directly.  I suppose it is possible to define an extended set of traits for many of the free functions that default to the current implementation (similar to winding), but it is hard to know where to draw the line, and it wouldn't be easier for the user than just overloading, but it would be more obvious, but it would be much more work for me.  I chose to provide the winding trait because I call winding very frequently, yet it is very common for winding to be a class invariant and known actually at compile time and so have O(0) runtime complexity.  Perhaps we can add an example showing how to override free functions for performance.  

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

I'm very glad to hear it.  I made correctness with intuitive and simple to use interfaces my priority.  With feedback from the boost community I also cleaned up all the compiler warnings and fixed compatibility issues with the various compilers and versions thereof.  Getting the functionality to you was a little like getting a block of cheese through a cheese grater.  I had to limit the scope a little and work a lot.  Contributions from the community are very welcome, both patches and new features.  The simplify algorithm was actually a contributed by a user of the library who had a CAM application.  If you would like to contribute a Douglas-Peucker implementation (perhaps you were forced to write your own) I'd be very happy to integrate it, document it and get it into the next release.

Thanks,
Luke