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

Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Brandon Kohn (blkohn_at_[hidden])
Date: 2009-03-08 11:30:26

--------------------------------------------------
From: "Thomas Klimpel" <Thomas.Klimpel_at_[hidden]>
Sent: Sunday, March 08, 2009 5:49 AM
To: <boost_at_[hidden]>
Subject: Re: [boost] [geometry] area, length, centroid, behavior

>> Is it really just the problem of maintaining a stable sorting of the 
>> segment intersections with the sweep-line? This will surely require some 
>> care, but doesn't sound like a fundamental issue ruling out 
>> Bentley-Ottmann for floating point.

It does seem simple doesn't it. Perhaps you should give it a try to see... I 
would certainly welcome a more robust solution. I would like to point out 
that even the LEDA Bentley-Ottmann implementation has issues on FP (at least 
the version I tried a couple of years ago.)

Here's another paper describing (in sometimes painful detail ;) some of the 
issues.

ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-3270.pdf

>> What looks more nasty to me is that for nearly parallel segments, 
>> Bentley-Ottmann has to compute the intersection point of the 
>> corresponding lines, even if it is not an intersection point of the 
>> segments. But perhaps a simple modification of Bentley-Ottmann can avoid 
>> the need to depend on "false" intersection points.

I don't have anything like this in my implementation. I use segment 
intersection testing not line (though these tests do involve some of the 
same mechanisms as line intersection testing but with constraints). The 
intersection tests are only computed on segments which are adjacent to each 
other in the sweep line. I don't see how being nearly parallel makes any 
difference. If the segments (not lines) do not intersect then they do not 
report a 'false' intersection. The issues that I have encountered come from 
the computation of the intersection point of one of the segments with the 
sweep line (not between the segments.) and the subsequent comparison with 
similar intersection points from neighboring segments in close vicinity.

>>I'm just wondering whether there are more fundamental issues ruling out a 
>>Bentley-Ottmann type algorithm applied to floating point than "simple" 
>>stable sorting issues.

>>  I have a
>> faithful implementation of the algorithm from a text-book which still
>> manages to fail on occasion (even with fuzzy comparisons though not so
>> frequently as without.)
>
> 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".

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.

Perhaps this idea is similar to what is done here:

http://cutebugs.net/files/curve/2-27.ps

If you would like to give this a go, I'd be happy to collaborate. The code 
is available at:

http://sourceforge.net/svn/?group_id=240335 (project name gengeomalg).

svn checkout:

svn co https://gengeomalg.svn.sourceforge.net/svnroot/gengeomalg gengeomalg

> Assuming it is possible to make a Bentley-Ottmann type sweep-line 
> algorithm robust against floating point issues, what other issues will 
> have to be considered when deciding which algorithm to use?
>

I would say the same considerations as any other algorithm: correctness, 
run-time complexity, and memory use.

Regards,

Brandon