Re: [boost] [geometry] robustness approaches

Subject: Re: [boost] [geometry] robustness approaches
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2009-03-14 18:26:16

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.

Because the initial topology might be different than the topology when converted to integer coordinates, 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 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. (I know that this interpretation is a bit unfair. The authors themselves give a better justification of why they choose their approach: "The first approach is the most general and is known under the the exact geometric computation (EGC) paradigm and [...]. The EGC approach has been adopted for the software libraries LEDA and CGAL and other successful implementations.")

Regards,
Thomas