Re: [boost] [geometry] robustness approaches

Subject: Re: [boost] [geometry] robustness approaches
From: Fernando Cacciola (fernando.cacciola_at_[hidden])
Date: 2009-03-20 19:37:35

Hi Luke,

> Fernando Cacciola wrote:
>> When I first incorporated GPC (which btw has, easily, thousands of users)
>> into a project, I spend a lot of time studying its robutness by feeding it
>> specially designed test cases. It passed them all, so it appeared to
>> evident that it was robust for all practical purposes.
>> 
>> The project evolved until one day I started to recieve, with increasing 
>> frequency, bug reports that boiled down (after many wated hours) to be 
>> robustness issues within GPC. Soon a geometric pattern popped up as the
>> culprit: a complex figure F and another figure F2 obtained by shifting F a 
>> really *really* small amount, then subtrating F2 from F.
>> 
>> That pattern totally choked GPC, even after years of succidingly producing
>>  correct results. In the end my client had to buy the CGAL clipper wich is
>>  slower, nowhere cheap, but truly 100% robust.
> 
> That's really interesting.  I didn't realize GPC was so used.  We are testing
> GPC to compare its performance to GTL.  Our impression of GPC was not very
> favorable based on its web site, API and feature set.  I figured out that its
> input polygons can be "multiple disjoint contours" but it doesn't handle
> multiple overlapping contours.  If I have thousands of polygons and they are
> not disjoint, how do I merge them together with GPC?
> 
That's actually possible.
I just found that is missing in the online docs though, but it is in the actual 
API. At least in the one I still have lurking on the code base (though unsued).

There is this function:

void gpc_polygon_overlap     (xgpc_op          overlap_operation,
                               int              depth,
                               gpc_polygon     *subject_polygon,
                               gpc_polygon     *result_polygon);

Using this operation code:
typedef enum
{
   GPC_EQUAL,                        /* Overlaps == depth value           */
   GPC_EQUAL_MORE,                   /* Overlaps >= depth value           */
   GPC_EQUAL_B,                      /* Overlaps == depth value (bridged) */
   GPC_EQUAL_MORE_B                  /* Overlaps >= depth value (bridged) */
} xgpc_op;

Best

--
Fernando Cacciola
SciSoft Consulting, Founder
http://www.scisoft-consulting.com