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

Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-03-10 13:31:19

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

You are overlooking the fact that F may be passed by the scanline before we reach E, in which case we considered F with respect to CD, and can't put humpty dumpty back together again once be cross it by snapping E.  What I do is find the points such as F that may be crossed due to intersectin snapping and intersect CD with them assuming an E will will come along later.  These intersections could be made optional and performed only in the cases where it turned out to be necessary, but it is rare enough I don't bother.

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

You would be right.  Commercial tools have options to snap vertices outward and "grow" the output polygon slightly or inward and "shrink" the output polygon slightly, or just snap to the closest.  This allows for the type of reasoning you outline above.

Regards,
Luke