Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Steve M. Robbins (steve_at_[hidden])
Date: 2009-03-11 13:48:30
On Wed, Mar 11, 2009 at 09:58:31AM -0700, Simonson, Lucanus J wrote:
> Steve M. Robbins wrote:
> > Can the proposed Boost libraries support this kind of exact Predicates
> > with approximate Constructions paradigm?
> I don't see that we have a choice. Inexact Predicates leads to
> undefined prgram behavior, incorrect outputs, hangs and crashes.
> Exact Constructions implies the output coordinate data type is
> multi-precision. Most users would typically prefer the other way
> around for both.
Arguably, once in a while, someone will want to use an extended
precision number type and get exact constructions. But the common
case would be as you state.
> 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.
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?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk