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-09 14:01:33

>> I don't think that fuzzy comparison is a good idea when you want to
>> make Bentley-Ottmann robust for floating point. You will have to
>> ensure that "important decisions" are only computed once, and
>> enforce that no other intermediate/computed result can contradict
>> these "decisions". 
>
Brandon Kohn wrote: 
> Perhaps you are right here, but I would have to think about it
> further. I'm not sure that there are cases where you are calculating
> the same information multiple times. The segment intersections are
> calculated once. The sorting 
> is only done when a segment is inserted into the sweepline structure
> (so one comparison between each segment inserted and those already in
> the 
> structure). I suppose the one bit of information that is calculated
> many times is the topology relation to neighboring segments when
> interpolating 
> the current intersection point with the sweep-line over a range of
> event points. When points become very close (to within an epsilon
> tolerance) the ordering on the line becomes indeterminate when simply
> using fp comparison. It may be possible to do something along the
> lines of what you suggest here. 
> 
There is a trick to perform the comparision of slopes more accurately.

If you want to know whether a/b < c/d you can either write:

if(a/b < c/d)

Or:

if(ad < cb)

Since division tends to do unfortuntate things it is better to use multiply.  If your coordinate is double you can use long double for the multiply and it will fit better.  You can extend this trick to compare two scanline intercept points.

a = y2 - y1; b = x2 - x2;
Intercept1 = y1 + (x - x1) * a/b;
Intercept2 = y2_1 + (x - x2_1) * a2/b2;
Proportional_to_intercept1 = y1 * b * b2 + (x - x1) * a * b2;
Proportional_to_intercept2 = y2_1 * b * b2 + (x - x2_1) * a2 * b;

Intercept1 < Intercept2 == Proportional_to_intercept1 < Proportional_to_intercept2

However, you run out of room in even the long double with so many multiplies, so you should investigate higher precision floating point data types to achieve robust arithmetic.

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.  This is a bad problem in floating point because the ammount 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 happer with integer coordinates.

Regards,
Luke