Re: [boost] [geometry] area, length, centroid, behavior

Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-03-10 06:19:02

Simonson, Lucanus J wrote:
> My main concern isn't whether the scanline is maintained properly, it is whether 
> spurious intersections are introduced when snapping an intersection point to the 
> floating point coordinate grid.  Because snapping moves the edge laterally by 
> some small ammount it may cause it to cross to the other side of a vertex than 
> the original segment, leading to the invariant that all output segments are 
> non-intersecting and touch only at their end points being violated, which breaks 
> downstream code.

Let me see if I understand this correctly.  Say you have two line 
segments AB and CD that cross at E:

    A       D
     \     /
      \   /F
       \ /
        E
       / \
      /   \
     C     B

Due to the floating point approximation, C-E-D is not perfectly 
straight and there is some other vertex F which lies one one side of CD 
but the other side of ED.  This can also happen with integer 
co-ordinates, but it's easier to reason about in that case.  Right?

It seems to me that the fix must be to forget about C-D as soon as E 
has been found, and only use the new edges CE and ED from then on.  If 
this is true, what are the implications for the interfaces to the 
algorithms that do this?  Does it mean that if I have:

   polygon P;
   polygon Q;
   polygon R = intersection(P,Q);

then intersection() should be allowed to modify P and Q to add new 
points?  Otherwise, we may end up with points that are inside R but not 
inside P or Q.

Thinking about it from the application requirements point of view it 
may be acceptable to have algorithms that are guaranteed to err one way 
and not the other, e.g.

   union1(A,B) contains every point in A and B and perhaps some extra ones
   union2(A,B) contains most points from A and B and no points not in A 
or B

I would like to think that this has all been considered many timed before....

Phil.