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

Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2009-03-09 19:18:27

Simonson, Lucanus J:
> 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.

It is an interesting question whether talking about a floating point coordinate grid is appropriate. An important difference between integer coordinates and floating point coordinates is that integer coordinates input must often be treated as exactly given, while it is often OK to modify floating point input slightly. (But this is problem dependent, and 2D geometry problems are probably more naturally associated with fixed-point/integer coordinates than with floating point coordinates. So following "floating point rules" for 2D geometry problems will probably often be inappropriate.)

> Because snapping moves the edge laterally by some small amount
> 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.

It may be OK in a floating point context to break this invariant, if enough information is given to downstream code that it can avoid breakage. If this is not an option, conversion of the initial input to fixed-point may be the more appropriate way to go. (Remember that it is often OK to modify floating point input slightly, so the inexact conversion to fixed-point is not necessarily a problem). A computed floating point coordinate would simply be allowed to have a tolerance of epsilon.

> This is a bad problem in floating point because the amount the segment moves laterally
> depends on where the intersection point was snapped in the floating point domain,
> and can become arbitrarily large.  I'm much happier with integer coordinates.

I find it a bit difficult to understand which output is considered valid in an integer coordinates context. The output in figure 2 of
http://cutebugs.net/files/curve/2-27.ps
(the reference suggested by Brandon) feels wrong to me, but it is apparently the expected output in this case. I'm not sure whether I should try to implement a Bentley-Ottmann line-intersection algorithm along the way I suggested to Brandon, but if I did, this implementation would not be allowed to report the two additional intersection points, because this would contradict the decision computed previously at the event-point (0,0) that the segment [(0,0),(9,5)] is "greater" than the segment [(0,0),(13,6)] along the sweep-line for x>0. But the implementation would still be allowed to report the intersection point (5.45,2.52) as (5,3), because it would be understood that this result has a tolerance on the order of epsilon=1.

Regards,
Thomas