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

Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Steve M. Robbins (steve_at_[hidden])
Date: 2009-03-11 02:09:44

Hi,

On Mon, Mar 09, 2009 at 11:01:33AM -0700, Simonson, Lucanus J wrote:

> There is a trick to perform the comparision of slopes more accurately.
> 
> If you want to know whether a/b < c/d you can either write:
> 
> if(a/b < c/d)
> 
> Or:
> 
> if(ad < cb)

 [ ... ]

> However, you run out of room in even the long double with so many
> multiplies, so you should investigate higher precision floating
> point data types to achieve robust arithmetic.

Indeed.  A lot of work in Computational Geometry (e.g. Exact Geometric
Computation [1]) divides the numeric computation into two types.
First, we have decisions ("are three points collinear or not?") that
are based on comparing computed numbers like the slopes example above.
Second, we have newly-computed geometric entities like the point of
intersection of two line segments.

These two types of computations are sometimes called Predicates and
Constructions, respectively.

Libraries that support Exact Geometric Computing (e.g. CGAL) mandate
that Predicates are exact, but sometimes the Constructions can be
approximate, depending on the application needs.

Can the proposed Boost libraries support this kind of exact Predicates
with approximate Constructions paradigm? 

Regards,
-Steve

[1] ftp://ftp-sop.inria.fr/geometrica/pion/publis/egc_survey_jlap.pdf