[geos-devel] Robustness of Binary Predicates

Martin Davis mbdavis at VividSolutions.com
Mon Mar 6 15:15:43 EST 2006


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.

Yes, this can lead to inconsistencies, such as the one shown.  Whether
this is a problem or not depends on the application.  

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.

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
> 



More information about the geos-devel mailing list