[geos-devel] Robustness of Binary Predicates

[Martin Davis]

Hi, Todd.

> The most important question would be why you chose to have the Binary 
> Predicates operate at "infinite precision" rather than at the 
> precision 
> of the precision model (ie in most cases at the precision of the data 
> itself). The computer itself cannot work at infinite precision.

There are a few rationales behind this decision:

- It is perfectly feasible to compute the exact topological relationship
for double-precision coordinates.  Any given double-precision coordinate
defines a finitely specified location in space.  Any two DP segments are
finitely defined, and have a well-defined topological relationship to
each other.  The relationship of all higher-order geometry can be
determined from the relationships identified for the segments comprising
them.  

- The goal was to compute topological relationships for the exact
coordinates presented by the user, not some rounded or processed
representation.  To my mind the computation of the exact relationship
given by the full-precision arrangement is the most fundamental
operation.  If a rounded representation is required, that could be
provided as a "front-end" to the relationship computation.

- To my mind the semantics of relationships using full-precision is
easier to define and comprehend than when the precision model is
incorporated.  Witness your example - visually it's obvious that the
lines do not intersect.  It's much less obvious what the correct
relationship is if the geometries are implicitly snapped to a precision
model

> Instead of  trying to make the FIXED precision model a special case of

> the FLOATING model, we have the FLOATING precision model as a special 
> case of the FIXED model. Everything falls into place better.

JTS uses floating-point for a few reasons  It's faster than integer.  It
doesn't require scale factors to represent very large or small
coordinate spaces.  It supplies 54 bits of precision (some existing
systems are limited to 32 bits, which is too small for a lot of
requirements).  

I do agree, though, that in order to provide fully robust boolean
operations (as opposed to predicates) that you probably have to round
things to a fixed-precision grid.  Another advantage of using
floating-point may be that this rounding can take place on a
case-by-case basis, rather than forcing every geometry to be rounded a
priori to the same grid.  (Looking ahead to Google Quantum Cosmos, which
displays every single atom and star in the Universe  8^)

Nice to hear that you find basing things on FIXED works better.  I'd be
interested in seeing how the API supports presenting the user with a
floating-point model.  And I hope you offer more than 32 bits of
precision!

> IMHO the Binary Predicates must honour the precision model. 
> How can the boolean operations operate at infinite precision when the
computer is 
> restricted to 15+ significant figures?

The boolean operations (overlay) can't.  The Binary Predicates can (by
virtue of the fact that they are not constructive, but simply return a
boolean value representing a computation on a finitely specified state).

Sorry to hear that all your good thinking on this topic is not going to
be readily available to the community.  There's some big issues
underneath all this, and it would be nice to be able define a standard
approach to handling this.

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