Boost logo

Boost :

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


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

Btw, since then I have a "classic procedure" to stress test the robustness of a
polygon clipper:

Take a typical real world GIS polygon, which has the interesting property of
having regions with very very short segments, interleaved with regions with very
very long ones. Call it polygon A.
Create a polygon B by moving A a very short amount horizontally: say 1e-5.

Then, the following:

A - ( (A-B) + (B-A) ), without any expression simplification (that is with the
intermediate binary results effectively computed) should be EXACTLY the empty set.

This is a test that can be automated, so it doesn't rely on the *impression*
that the result is correct.


Fernando Cacciola
SciSoft Consulting, Founder

Boost list run by bdawes at, gregod at, cpdaniel at, john at