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-11 15:12:31

>> The point of the slope comparison trick is that it is a way to avoid
>> loss of precision without resorting to multi-precision data types.
>> It needs only ~66 bits of precision for 32 bit integer coordinates,
>> and so long double is suitable in all cases to correctly compare the
>> slopes of integer line segments.
>
Steve M. Robbins wrote:
> OK.  But I'm assuming that I can define my own point class and use my
> favourite number type for the coordinate values.  (I admit that I
> haven't been looking closely at the current proposed library code, so
> that may be a mistaken assumption.)  If I use doubles for the
> coordinate values, then the slope comparison trick needs more
> precision.
>
> Basically, the intersection test is a degree 2 predicate so it needs
> about double the precision of the input (coordinate) data types.  So
> each predicate needs to be templated over the coordinate number type.
> Or something similar.  How is this achieved in the proposed libraries?
>
If you use your favorite number type you can supply your favorite multi-precision number type.  I use a big hammer and allow the user to specialize a meta-function that supplies the high-precision data type to use in all such cases for their given coordinate.  It defaults to long double.  I use gmp rational for my integer arithmetic when I use the library, but don't depend on gmp in the library header files because it can be customized at the application level.  While it could be more efficient to specify a different high-precision type for each predicate (long double is sufficient for my integer slope comparisions, but gmp rational is used) it is less reasonable to expect such sophisticated custimization to be applied by the user.

Each predicate could be individually overridden by specializing the function that implements it for the given coordinate type, but this would be very challenging because it would require knowledge of the internals of the library and only expert users might do it.  So far I'm the only person with such knowledge.  I could, for example, optimize integer slopes comparision to use long double instead of whatever the high-precision data type is parameterized to.  I wouldn't expect anyone else to do so.

It might be worthwhile to create a separate module of robust geometry primitives that privdes a nice interface with points of customization instead of letting them be implementation details of specific algorithms.

Regard,
Luke