Re: [boost] [geometry] robustness approaches

Subject: Re: [boost] [geometry] robustness approaches
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-03-17 19:25:35

Thomas Klimpel wrote:
> Hi Fernando,
> 
> The clear position of Lucanus Simonson with respect to the "allowed"
> output of a line segments intersection algorithm and your reactions
> to his position makes me wonder which output you consider "allowed".  
> 
> The figures 1a), 1b), 2) and 3b) of John Hobby's publication
> http://cutebugs.net/files/curve/2-27.ps
> clearly illustrate the discussed issue.
> 
> I considered 2) as non-acceptable output and Lucanus Simonson
> considered 1b) as non-acceptable. (The output 3b) seems to be the
> most attractive one for this example.) 

Just to be clear, 3b is what my algorithm does.  I always round fractional values down with a floor() operation whereas Hobby suggests rounding to the closest whole number.  I think he also has a complicated scheme for collapsing point clusters whereas I just collapse points together if they are in the same 1x1 unit grid.  I'll be sure to cite Hobby in my boostcon submission.  I did read his paper before I devised my robustness strategy.

> Your position that geometric
> algorithms should use exactly evaluated "predicates" called
> explicitly on the input (and never ever on an intermediate result) to
> drive the topological construction doesn't seem to settle this
> question.      

I think Fernando did mention that the requirements for the output of line intersection differed from that of straight skeleton, which was his example.  Also, my implementation never stores intermetiate results as keys in the tree and never computes intersections based on intermediate results.  It works purely by storing input line segments in the tree and comparing them with exact predicates and also computes intersections based on the input line segments only, exactly as Fernando suggests.  The snapping of intersection points may introduce benign topological changes in the output, as you point out.  These changes are benign because in the case of line intersection for polygon clipping the critical topological consideration is that all closed cycles remain closed (or degenerate) after any topological change.  Since the algorithm is robust to all colinear/duplicate point type degeneracy it is also robust to such degeneracy introducted by intersection snapping.  The algorithms that consume straight skeleton have different topological requirements.  In order to understand what is allowable in the output of an algorithm you have to understand the broader context in which that algorithm is applied.  For example it is frequently the case that subsequent to polgyon clipping the polygon is fed into meshing.  That means that the output of the clipping should satisfy the input requirements of the meshing algorithms.  If it doesn't you've got a square peg and a round hole.  I don't know the context for straight skeleton, since my own uses for it are limited to centerline extraction of VLSI physical layout data.  We don't really encounter numerical issues except if the width of a wire happens to be an odd number, in which case some un-cautious implementations of integer skeleton of manhattan geometry fail spectacularly. ;)
 
I wonder if my generic scanline framework can be adapted to provide straight skeleton, the problem is ammenable to scanline if I'm not mistaken....

Regards,
Luke