[geos-devel] Robustness of Binary Predicates

Todd Jellett todd.jellett at caris.com
Thu Mar 9 09:38:58 EST 2006


Hi Martin,

See Below

Todd

Martin Davis wrote:

>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
>
>  
>
The problem I see with this approach is that the Binary Predicates can 
*never* agree with the boolean operations (which I have indicated is how 
I interpret the spec(s)).

>>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!
>
>  
>
I think I have somehow confused you. We don't use integers, we 
snap/round to a fixed precision grid (even for the FLOATING model). We 
do this for both the Binary Predicates and the boolean operations, so 
that they agree with each other. They agree in our 3rd generation 
geometries and they will in the 4th generation as well. The move to ISO 
19107 is mainly to provide a framework to tie 2D, 3D, interpolation, 
TINs, VOXELS and various types of surfaces (ie parametric surfaces) 
together. It will also allow us to create new types such as parametric 
and geodetic LineStrings.

For the FLOATING model, the FPU does the rounding but we treat it as 
FIXED with 15 significant figures. All that's needed to do this is a 
robust 3x3 (sign of) determinant which can robustly determine 
isLeftOf(), isRightOf(), and isCollinear() for 3 points *beyond* the 
precision of the computer. (We use Shewchuck's Exact Adaptive 
Orientation tests.)

For both Binary Predicates and Boolean Operations:
-Find *all* the primary and secondary intersection points up front 
(includes the extraneous intersection points).
-Snap/Round the intersection points to the precision model (This gives 
all the correct nodes and edges in your graph/TP_COMPLEX(s))
-Once you have the correct nodes and edges (based on the precision 
model), treat the graph(s)/TP_COMPLEX(s) as verbatim and "discover" what 
is there. The only computational geometry required is point-in-polygon 
(EdgeRing).

As far as mapping the universe goes, all of our clients are here on 
Earth :-) . Realistically, the 15 digits of precision gives us more 
resolution (1/10000 of a millimeter) everywhere on this planet than can 
be realistically measured (absolute measurment). When the error in a 
datum transformation is in the order of meters, this more than enough 
precision for us earthlings.

>>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).
>  
>
I see this as a restriction not an asset. Not only are the Binary 
Predicates not constructive but they cannot be used in any geometric 
constructive operation because they will cause errors due to ambiguities.

>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.
>  
>
Got to pay the mortgage (regularly) somehow. OpenSource is nice in 
theory but realistically, how many OpenSource authors are out there that 
are completely self-sustained on their OpenSource income. Yes I know 
there are some, and some of them do very well, but the majority are not 
so lucky.

>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
>
>_______________________________________________
>geos-devel mailing list
>geos-devel at geos.refractions.net
>http://geos.refractions.net/mailman/listinfo/geos-devel
>  
>




More information about the geos-devel mailing list