Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009

Subject: Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-08-28 11:44:45

Barend Gehrels wrote:
> I promised to come back on this:
> 
>> My friend Barend Gehrels [Barend.Gehrels_at_[hidden]] also has several
>> countires for the geographic database that CGAL fails on.  You might
>> be able to get them from him quite easily.  
>> 
> The counties that CGAL fails on are counties where the exterioring
> ring 
> is touching itself. CGAL reports that the polygon is not strictly
> simple, which is indeed the case. It is accepted by other libraries
> (Boost Polygon, GGL, Geos, SQL Server 2008, etc) but that does not
> mean 
> that CGAL is wrong here.
> 
> I added an image of this into our WIKI:
> http://trac.osgeo.org/ggl/wiki/CgalNotStrictlySimple
> 
> 
> Besides that, I added the performance benchmark results into our Wiki:
> http://trac.osgeo.org/ggl/wiki/Performance, including Boost Polygon,
> GGL, CGAL, Geos and other libraries.

Thanks Barend, by the way, your wiki looks very good.

This probably explains the precondition failure I was seeing in CGAL.  My algorithms outputs holes that may touch themselves the way you show in the wiki because this is the complement of the policy for shells.  The self touch degeneracy results in a high order vertex, which requires quite a bit more algorithmic work to handle correctly than if you assume order 2 vertices only.  I wouldn't say CGAL is wrong here, but I would say that it underscores the importance of providing a polygon clipping library with no preconditions on its inputs.

Thanks again,
Luke