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

[chodgson at refractions.net]

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.
>