Re: [boost] [geometry] robustness approaches

Subject: Re: [boost] [geometry] robustness approaches
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-03-16 13:41:12

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

Luke