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