Re: [boost] [geometry] robustness approaches

Subject: Re: [boost] [geometry] robustness approaches
From: Fernando Cacciola (fernando.cacciola_at_[hidden])
Date: 2009-03-15 16:55:38

Hi Thomas,

> Simonson, Lucanus J wrote:
>> Most applications need uniform precision (cartography is a good
>> example) whereas graphics is the only application I can think of
>> that needs high precision around the origin and low precision far
>> from the origin.  This scheme ought to cover most of the needs for
>> floating point geometry. Can you identify any problem with the
>> idea?
> 
> I really like the idea, but I can't help pointing out a mismatch
> between the integer and floating-point philosophies. The typical
> integer philosophy would allow to introduce new points into existing
> segments, but would "forbid" the computed result (taken literally as
> rounded to integer coordinates) to have more intersections than
> actually reported. The typical floating-point philosophy would allow
> the computed result (when represented as by floating-point numbers)
> to have more intersections than actually reported (as long as these
> additional intersections would only be artifacts of the
> floating-point representation), but would "forbid" to introduce new
> points into existing segments.
> 

It easy to see how that mismatch comes only from using intermediate 
results (which includes the snapped input) to drive the topology of the 
result.

If OTOH the algorithm used the input (*as is* without even the snapping) 
then it would matter at all what number type is used, integer or 
floating point (provided the algorithm uses the predicates correctly)

> Because the initial topology might be different than the topology
> when converted to integer coordinates,

Which is why snap rounding can be used for certain algorithms.

> the computed result might (in
> admittedly rare circumstances) have more intersections than actually
> reported, and the computation might also have introduced additional
> points into existing segments, in order to assure that the computed
> result in integer coordinates doesn't have more intersections than
> actually reported.

I would say that an implementation shouldn't do any of that all.

Based on my experience, all that hacking becomes needed when then 
algorithm *logic* is driven by its own intermediate results, so it is 
*that* what needs to be avoided to begin with.
Many many "existing" algorithms can be refactored to do that.

> I still think it's a good idea to use the described scheme. You
> already have the integer algorithms, so it's only natural to reuse
> them. When I read 'Ulrike Bartuschka, Kurt Mehlhorn, Stefan N¨aher',
> "A robust and Efficient Implementation of a Sweep Line algorithm for
> the Straight Line Segement Intersection Problem", it soon become
> clear that the LEDA rat_point/rat_segment data-types where there
> first, so that it was only natural to benefit from them. 

Indeed. As I said to Luke, intersection-based problems naturally fit 
into snap rounding. But other don't.

Best

--
Fernando Cacciola
SciSoft Consulting, Founder
http://www.scisoft-consulting.com