[geos-devel] QD (Quad-Double) Approach to Robustness

[Martin Davis]

This would probably be a good approach for the local problem of
computing an accurate intersection point.  It might also help solve the
problem of computing a topologically correct arrangement of noded lines,
but this might require some experimentation to see how far into the
algorithm the quad precision would have to be carried.

Any idea if there is a Java version?  8^)

Martin Davis, Senior Technical Architect
Vivid Solutions Inc.      www.vividsolutions.com
Suite #1A-2328 Government Street Victoria, B.C. V8T 5G5
Phone: (250) 385 6040 - Local 308 Fax: (250) 385 6046


> -----Original Message-----
> From: geos-devel-bounces at geos.refractions.net 
> [mailto:geos-devel-bounces at geos.refractions.net] On Behalf Of 
> Paul Ramsey
> Sent: June 12, 2006 3:11 PM
> To: GEOS Development List
> Subject: [geos-devel] QD (Quad-Double) Approach to Robustness
> 
> 
> In a conversation with Dale Lutz at GeoAlberta, he mentioned 
> they had  
> experimented with using the QD library 
> (<http://crd.lbl.gov/~dhbailey/ 
> mpdist/>) in some of their 
> topology processing and found that it was  
> exceptionally good at bypassing problems caused by reduced  
> precision.  Presumably this is because all the input data is at  
> double precision, at most, so relative to the processing precision  
> (quad) it is quite well behaved.  The approach was so good that in a  
> race between the old algorithms (double precision but with lots of  
> tests and bobbing and weaving to catch special cases) and the new  
> (quad precision, with no special cases at all, just naive 
> algorithms)  
> the qd won hands down.  So the overhead of the math library on all  
> cases was not higher than the overhead of finding and handling the  
> special cases.
> 
> Something to look at!
> 
> P
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net 
> http://geos.refractions.net/mailman/listinfo/geos-devel
>