[geos-devel] Robustness of Binary Predicates

Todd Jellett todd.jellett at caris.com
Wed Mar 8 10:25:50 EST 2006 

Hi Martin,

Just got back from an extended weekend myself.

We are currently implementing our 4th generation geometries. This 
version is based on ISO 19107 while the previous generations are based 
on SFS. We wanted to use geos as a reference model to test our new code 
against since robustness is claimed (at least for the Predicates). My 
impression of the specs (both of them) was that the "package", both 
Binary Predicates and set theoretics (intersection, union, and 
differences), should be robust. To me this implies that the Binary 
Predicates and the set theoretics should agree. I acknowledge that 
neither of the specs define "robustness".

See my comments below. Since we can't use geos as a reference model (for 
the obvious reasons) you can take my comments as you wish.

Todd

Martin Davis wrote:

>I've been on holiday - lucky me.
>
>Paul's assessment is correct.  JTS predicates operate in "infinite
>precision", and are not affected by the precision model, roundoff
>errors, or robustness issues.
>
>The boolean operations, on the other hand (and all other constructive
>operations) work within the Precision Model specified, and hence can
>produce results which are affected by roundoff error.
>  
>
But the implementation of the boolean operations should be insulated 
from round-off errors by design (choice of algorithms), shouldn't they?
If you are affected by round-off errors, you have a robustness problem 
by definition don't you? (Using a computational geometry definitition of 
robustness.)

>Yes, this can lead to inconsistencies, such as the one shown.  Whether
>this is a problem or not depends on the application.  
>  
>
When I have *data* that is at a particular resolution (precision), like 
s57 or VPF data, I would expect the Binary Predicates (ie disjoint) to 
honour the precision of the *data* (because I would not get what I 
expect otherwise). Typically we would test geometries for being disjoint 
and *only* perform an intersection on the geometries that are *not* 
disjoint. Here we would get the "wrong anwer".

Can't any piece of software claim robustness as long as it is qualified 
with a "depends on the application"? You need to define your "robustness".

>Should JTS apply the Precision Model to the predicates as well?  Well,
>maybe.  One thing is for sure - this would be slower than the current
>approach.  Snap-rounding (as used in the Hobby paper) is *much* slower
>than the intersection detection algorithm currently used.
>
>  
>
Every time you snap a point, you move one end of every segment that has 
that particular point as an end point. Every time you move a segment, 
you could be creating new intersection points (and possibly removing 
others).  This can even occur in a FLOATING model where the FPU rounds 
your intersection points (and moves segments). If you don't account for 
these "extraneous intersection points" you will always have 
inconsistencies (robustness problems).

Yes I agree that it will be slower but...

We have a saying around here "Speed is important, but it doesn't matter 
how fast you get the wrong answer". :-)
Translation - In engineering applications robustness/correctness trumps 
speed of execution.  If the "intersection detection algorithm currently 
used" does not find *all* the intersection points, when it needs to find 
*all* of the intersection points to be robust, it doesn't matter how 
fast it is. This is an indication that the current algorithm needs to be 
adjusted or re-implemented using an algorithm that does find *all* the 
intersection points. Make it correct first then profile to see where it 
can be sped up.

>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: March 2, 2006 8:55 PM
>>To: GEOS Development List
>>Subject: Re: [geos-devel] Robustness of Binary Predicates
>>
>>
>>I am surprised Martin has not jumped in here with the definitive  
>>answer. It looks like the intersection is being done with a 
>>precision  
>>model and the boolean test is not... on graph paper those lines to  
>>not touch, but they do get within the precision tolerance of one  
>>another.
>>
>>P.
>>
>>On Mar 2, 2006, at 4:16 AM, Todd Jellett wrote:
>>
>>    
>>
>>>Sorry (again), I should have investigated the crash more closely.
>>>
>>>It was not occurring in the touches call but rather because I was
>>>trying to dynamic_cast a Geometry to a GeometryCollection. The  
>>>first example I sent returned a collection from the intersection  
>>>call while the second (corrected) example correctly returns the  
>>>intersection as a single point. I just wasn't checking the result  
>>>of the cast.
>>>
>>>My real problem is that using a FIXED precision model (scale = 1.0
>>>= Whole Numbers) and the LineStrings:
>>>L1 = LINESTRING (-1.0 -2.0, 9.0 5.0, 0.0 0.0, 13.0 6.0)
>>>L2 = LINESTRING (5.0 5.0, 5.0 3.0)
>>>
>>>I get:
>>>L2->touches( L1 ) = false
>>>L2->disjoint( L1 ) = true
>>>but
>>>L2->intersection( L1 ) = POINT(5.0 3.0)
>>>
>>>How can there be a non-NULL intersection (a single point) but still
>>>have the 2 geometries *being disjoint and not touching*?
>>>
>>>The intersection is correct. I am questioning the correctness of
>>>the Binary Predicates (touches and disjoint) since both 
>>>      
>>>
>>should agree.
>>    
>>
>>>Sorry for the confusion
>>>Todd
>>>
>>>
>>>strk at refractions.net wrote:
>>>
>>>      
>>>
>>>>On Wed, Mar 01, 2006 at 12:59:54PM -0400, Todd Jellett wrote:
>>>>
>>>>        
>>>>
>>>>>Sorry, the second LineString should be:
>>>>>LINESTRING (5.0 5.0, 5.0 3.0)
>>>>>
>>>>>This one crashes in L2->touches( L1 )
>>>>>
>>>>>          
>>>>>
>>>>Can you provide an xml test showing the crash ?
>>>>I tried relate(L1,L2) with 2.2.2 and HEAD with
>>>>no crashes.
>>>>
>>>>--strk;
>>>>
>>>>_______________________________________________
>>>>geos-devel mailing list
>>>>geos-devel at geos.refractions.net 
>>>>http://geos.refractions.net/mailman/listinfo/geos-devel
>>>>
>>>>        
>>>>
>>>_______________________________________________
>>>geos-devel mailing list
>>>geos-devel at geos.refractions.net 
>>>http://geos.refractions.net/mailman/listinfo/geos-devel
>>>      
>>>
>>_______________________________________________
>>geos-devel mailing list
>>geos-devel at geos.refractions.net 
>>http://geos.refractions.net/mailman/listinfo/geos-devel
>>
>>    
>>
>_______________________________________________
>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