intersects on 0-length linestring returns incorrect result
Opened this issue · 12 comments
Intersecting a 0-length linestring should either throw an exception or returns the same result as if it was a point.
test case :
line = wktreader.read("LINESTRING(10 20,10 20)");
line.intersects(line) ==> returns false !!
line.intersects(line.buffer(1)) ==> returns false !!
RelateOp is quite complex, and I did not find an easy way to fix it. I noticed that :
- when the linestring is added to the graph, the algo removes repeated points and set the single coord into the invalidPoint variable.
- while calculating the IntersectionMatrix, it still considers that input geomery has dimension 1, which may be a problem
One solution is to throw an exception, but I'd rather process the relateOp as if input geometry was a Point. I don't know if it is possible to substitute input geometry by a point somewhere in the algorithm.
Any thought about it ?
As a side note - I firstly found this strange behaviour in postgis (ST_Intersects), so geos is probably also concerned.
The short answer to this is that JTS considers 0-length linestrings to be invalid, so the result of operations on it is undefined.
I did this originally because I thought I read the OCG SFS specification ( 99-009 ) to say that Curves and thus LineStrings were not allowed to be zero-length. (See section 2.1.5). But reading it now I can't see anything that implies that. So perhaps the JTS semantics are fundamentally wrong in this respect!
What the specification does say is that a LineString is closed if the endpoints are equal, and that a closed LineString has no boundary (only an interior). So this means that LINESTRING( x y, x y) is topologically equal to POINT (x y) - as you would expect. So perhaps this means that zero-length linestrings can simple be changed into points internally. This can possibly be done in GeometryGraph.addLineString by detecting this and calling addPoint instead.
Can you try that out and see what happens?
For consistency, fixing this also requires a change in the isValid semantics as well. And associated unit tests. I can't think of anywhere else affected - but that's not a 100% guarantee.
By the way, in general JTS operations do not throw for invalid inputs, since that could require expensive validity checks.
Actually allowing zero-length lines leads to another nasty question. Topologically they are equivalent to Points, which have dimension = 0. But the spec states that "Curves are dimension-1 geometries". And in JTS LineStrings are assigned dimension 1 statically. So this might lead to some oddness in the IntersectionMatrix calculations.
Hi,
Thanks for answering. I was also convinced that 0-length linestring was invalid with respect to specification.
Maybe it depends on how we interpret the statement "Linestring is a one-dimensional geometric object". An inclusive interpretation may accept point (as it already accepts the concept of empty geometry). An more strict interpretation may exclude 0-dimensional geometry which is a kind of degeneracy case for a 1-dimension geometry. An inclusive interpretation may have different consequences and in case one accept 0-length linstring, it would be difficult to justify why we exclude 0-area polygons...
IMHO, we should not change the semantic of isValid which has been here for a long time, but all operations should always return a consistent result or an exception rather than an undefined (possibly inconsistent) result.
I'l try to addPoint instead of addLinestring in the graph in this case as you suggested.
I think it should not change the returned IntersectionMatrix but considering that input is a 0-dimension or a 1-dimension geometry may change how the IM is mapped to to the named predicates.
I agree that returning a consistent result or an exception is a worth goal, but as I mentioned, this would require expensive validity checks. So I don't think that's practical.
But it's possible to widen the scope of what results are consistent where this doesn't incur too much overhead. Handling zero-length linestrings is likely one of those cases.
Perhaps it would be possible to handle zero-area polygons in a similar way? (I.e. reducing them to a point).
Of course then the question is whether polygons which collapse to a line should be handled too. That's substantially more expensive to test, however.
On a different tack, intersects (and possibly covers) are the most useful predicates, and also ones that can have simpler implementations than the full-blown relate computation currently used in JTS. Such an algorithm would almost certainly be able handle degenerate geometries in a more graceful way. So that's another way forward to cope with this issue.
In fact, PreparedGeometry.intersects() already provides such an implementation, and it does return the correct answer for degenerate lines and polygons.
Polygon is probably more difficult to handle. Would it be possible to consider that polygons with a 0-length boundary have dimension 0 and polygons with a boundary > 0 but an area = 0 have dimension 1 ? Or length/area are not strict enough to make such conclusion ?
I did not know about PreparedGeometry.intersects ;-) Interesting. I will test it. Any reason why geometry.intersects use relate instead of PreparedGeometry.intersects in this case ?
It is probably better to avoid tying subtle relationship logic to length and area, because they are subject to precision issues. Also, that logic is getting a bit complex. Perhaps it's enough to detect polygons with only a single point and handle that in the same way as LineStrings.
PeparedGeometry uses a different algorithm which allows caching and fast evaluation of the simpler predicates (intersects and covers - which conveniently happen to be the most useful ones).
Also, that code was written some time after the original relate code. I haven't had time to work on wiring it up for the geometry predicates yet.
This will be fixed by the forthcoming RelateNG.