Boost logo

Geometry :

Subject: Re: [geometry] difference algorithm produces invalid polygon?
From: Volker Schöch (vschoech_at_[hidden])
Date: 2012-02-29 09:04:03


Hi Luke,

> I talked to Barend and he didn't object to my suggesting to you that you look the Boost.Polygon library. Polygon is integer coordinates based and robust to both numerical issues and all input geometries. Self-intersecting/self-touching polygons are not a problem, nor is open-closed or winding orientation a problem. The algorithm should never fail for any input.

Thank you very much for your input. Coming from GPC we had some debate whether we should switch to boost::polygon or boost:geometry. We decided to give geometry a shot, primarily for two admittedly weak reasons:

First, in performance comparisons that list both, boost::geometry and boost::polygon, geometry consistently seems to have some advantage (if there are sources that show opposite findings, I might have missed them and I'd be happy if you could point me there).

Second, boost::geometry seems to imply that more algorithms are supported (and that over time it may be extended to support even more) than the comparably hard but relatively specific problem of polygon clipping. For example, in our application we have some use for linestring intersection. I did not look into this yet, because our custom algorithm seems to do just fine, but when there's the next wave of changes in that department, we'd like to dump our code in favor of using some library. Next we'd like to see support for circles... Barend, would you like to comment?

I have had a look at boost::polygon and indeed it seems to be a perfect fit for the specific problem at hand. At the same time, I'd rather not mix-and-match functionality from two libraries, although I agree it would be interesting from an academic perspective. I prefer to avoid the heated discussions that are bound to occur when interaction between the two isn't smooth. It's nice to have one library to take the blame, instead of two pointing fingers at each others... ;-) Of course your wouldn't.

Preliminary bottom line: We will try to stick with geometry for the time being, but will definitely consider polygon if mission critical problems cannot get fixed before we have to release our code. Chances are that boost 1.50 becomes available before we have to release, and I have high hopes in that revision for geometry.

Your commments are very welcome!
Regards
   Volker

P.S. Is there a dedicated boost::polygon mailing list or forum? I couldn't find one.

--
Volker Schöch | vschoech_at_[hidden]
Senior Software Engineer
think-cell Software GmbH | Chausseestr. 8/E | 10115 Berlin | Germany
http://www.think-cell.com | phone +49 30 666473-10 | US phone +1 800 891 8091
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl

Geometry list run by mateusz at loskot.net