Re: [boost] [geometry] robustness approaches

Subject: Re: [boost] [geometry] robustness approaches
From: Fernando Cacciola (fernando.cacciola_at_[hidden])
Date: 2009-03-16 12:52:56

Hi Luke,

> Thomas Klimpel wrote:
>> The mapping to the original coordinates might still be useful, but
>> I think that modifying some of the original coordinates might be OK
>> in cases where the alternative would be to introduce overlapping 
>> segments.
> 
> I realize after giving the matter more thought that there is not
> necessarily a 1:1 mapping from fixed point back to floating point
> coordinates, this makes the idea of a mapping back to floating point
> less workable.  I suppose I could use a multi-map and map back to the
> centroid of multiple points.  I was already aware that converting
> back to floating point would cause some small movement of line
> segments which could result in non-reported intersections.  These
> would not be an issue if fed back into my algorithm, but could pose
> problems for other code.  As you point out, there is no way to output
> the correct topology without ignoring intersections that are
> artifacts of approximation of the intersection points and there is no
> way to report those intersections without modifying the output top 
> ology.  In some circumstances the output topology is paramount, such
> as the straight skeleton.  In my case I think topology is secondary
> to the output being free of non-reported intersection s.  If I
> convert fixed point output to floating point coordinates I cannot
> guarentee either output topology or absence of unreported
> intersections, as you also observe.  Topologically the thing that
> must be true about the output of my algorithm is that it is closed
> polygons.  That invariant cannot be harmed by introducing vertices as
> artifacts of snapping, or even by merging vertices that are too
> close.  The other invariant that must be true about my output is that
> it contains no intersecting line segments.  My own code relies upon
> that invariant, and it is a requirement at the input to all the
> commercial software we use downstream from my code.
> 
For all that I would recommend that you simply NOT support booleans of 
floating point polygons at all, and let that one be later on added via 
an algorithm that considers whatever is appropiate for floats from the 
ground up.

Without any benchmark I would imagine that your integer based solution 
is faster than, say, CGAL's clipper, which is robust for floating points 
but uses the floating-point filtering I outlined before, which as I said 
has some overhead likely higher than yours.

Best

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