[geos-devel] Issues with relate not handling GeometryCollections?
chodgson at refractions.net
chodgson at refractions.net
Thu Dec 5 13:05:32 EST 2002
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.
>
More information about the geos-devel
mailing list