[geos-devel] Issues with relate not handling GeometryCollections?

[Martin Davis]

You're correct in your description of the problem, Chris.

In the case of overlay, the problem is deep, in that the algorithm actually experiences catastrophic failure when it encounters a topology problem caused by robustness.  There's no way to recover from this - the best you can do is throw an exception.

In the case of relate, you may be somewhat correct in that the algorithm can trap any exceptions and just return *something*, which may or may not be correct.  But is returning values which may be wrong a good thing?  Might it not be better just to say we can't handle those cases reliably (which at least indicates to the user that he'd better think of another way of modelling his data).

Good point, though, that the percentage of cases which really are incorrect will be very low.  My original question was "What is the appropriate semantics?"  If there is a strong answer of "union semantics", then it may be worth implementing this even if a few times it's going to be wrong.

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


> -----Original Message-----
> From: chodgson at refractions.net [mailto:chodgson at refractions.net]
> Sent: Thursday, December 05, 2002 10:06 AM
> To: GEOS Development List
> Subject: RE: [geos-devel] Issues with relate not handling
> GeometryCollections?
> 
> 
> Okay, I'm not much of a geometryologist so let me make sure I 
> understand why 
> this is a problem. When relating two (singleton) geometries 
> you would normally 
> be able to use the determinant, or "triangle test" to 
> determine _exactly_ 
> whether a point is to the left, right, or on a line. However, 
> in this case you 
> must first first calculate the intersection of the two lines, 
> and there may not 
> be enough precision to calculate that exactly, so that when 
> you do the 
> determinant test, you may be doing it with an incorrect 
> point, and so the 
> result may be wrong. Am I correct? 
> 
> I guess I can understand the "moral" reason for not wanting 
> to implement 
> something that could give an incorrect answer in such a case, 
> however, is it 
> actually possible for something to go wrong in the algorithm 
> as a result of 
> this? I mean, given that one point happens to get pushed just 
> to the other side 
> of line due to precision issues, could the geometries or 
> structures used in the 
> algorithm become invalid, and cause catastrophic failure? Or 
> is the worst-case 
> result of such an error occurring just an incorrect result? 
> 
> If I recall correctly, the probability of 3 random lines 
> intersecting at a 
> single point is zero, so this should rarely be an issue, 
> unless people happen 
> to pick lines with the intent of them all meeting at a point. 
> And that wouldn't
> happen with the sort of lines people work with everyday, like 
> roads and 
> streams... </sarcasm>
> 
> Chris
> 
> Quoting Martin Davis <mbdavis at VividSolutions.com>:
> 
> >  Here's an example show why a robust approach is require to 
> the issue of
> > relating GeometryCollections.  In the attach image, you 
> have to be able to
> > tell whether the red line intersects the exterior of the 
> two blue triangles. 
> > This could require more precision than supplied by double 
> precision numbers.
> > 
> > Currently the only way I can think of doing this robustly 
> is to compute the
> > arrangement of the intersections exactly, and then examine 
> the resulting line
> > segments for their location to one another.  It's basically 
> the same problem
> > as for computing overlays robustly, but at least in this 
> case you can report
> > the results precisely,  since the output is just a boolean.
> > 
> 
> 
> 
> 
> 
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net
> http://geos.refractions.net/mailman/listinfo/geos-devel
>