Hausdorff distance wrong for LinearRing

[mwtoews]

Originally reported shapely/shapely#1934

Three geometry types with the same coordinates yield different Hausdorff distances, when the expected result should be the same (as JTS does).

Testing against main:

$ ./bin/geosop -a "POLYGON ((0 0, 0 10, 10 10, 10 0, 0 0))" -b "POLYGON ((1 1, 1 9, 9 9, 9 1, 1 1))" hausdorffDistance
1.4142135623730951
$ ./bin/geosop -a "LINESTRING (0 0, 0 10, 10 10, 10 0, 0 0)" -b "LINESTRING (1 1, 1 9, 9 9, 9 1, 1 1)" hausdorffDistance
1.4142135623730951
$ ./bin/geosop -a "LINEARRING (0 0, 0 10, 10 10, 10 0, 0 0)" -b "LINEARRING (1 1, 1 9, 9 9, 9 1, 1 1)" hausdorffDistance
12.727922061357855

Here is a viz of the expected result via JTS:

[dr-jts]

This is because the case geom.getGeometryTypeId() == GEOS_LINEARRING is not being checked in DistanceToPoint::computeDistance here.
Because of this omission the code drops through to computing the distance to only a single point of the input.

This is a common problem with checking typeIds rather than using the inheritance structure. No doubt there were good reasons for doing this. It's a simple fix here, of course. The bigger worry is whether there are other places in the code which need to check for GEOS_LINEARRING? @pramsey thoughts?

[pramsey]

Could do an audit to look for suspect patterns? The inheritance level checks had a big performance penalty, so they got scrubbed out a few releases ago.

[mwtoews]

the "assume geom is Point" part probably should throw an exception if unhandled

[dr-jts]

Could do an audit to look for suspect patterns? The inheritance level checks had a big performance penalty, so they got scrubbed out a few releases ago.

Yep, I've had a look. Actually looks pretty clea. There might be one or two other instances that need to be fixed - I will check further.

[dr-jts]

the "assume geom is Point" part probably should throw an exception if unhandled

Yes, good point. Like in PointLocator here.

[dr-jts]

LinearRings are the red-headed stepchild in JTS/GEOS - they are underrepresented in unit tests (and maybe in some algorithms).

[mwtoews]

It seems when this component was ported from JTS' DistanceToPoint.java, geom instanceof LineString was naively interpreted as geom.getGeometryTypeId() == GEOS_LINESTRING. This is another suspect pattern, since C++ doesn't have instanceof (or use this).

[dr-jts]

Actually the port originally used the C++ equivalent of instanceOf:

const LineString* ls = dynamic_cast<const LineString*>(&geom)

But this was changed in bf2958e to use the hand-rolled typeId pattern. Apparently dynamic_cast is slow - which seems unfortunate, since it's such a key part of inheritance-based programming. I really wonder whether this game is worth the candle - it's going to be a porting pitfall and fertile source of bugs.

[dr-jts]

A more geometric-based alternative would be to check if the geometry is atomic (not a collection) and has dimension = 1. Or perhaps provide a Geometry.isLine method to check if it's safe to use static_cast<const LineString*>.

There is 3 situations which can occur (and I think there's instances of all being used in different algorithms):

1. Structure-based: LineString and LinearRing processed in the same way
2. Type-based: LineString processed one way, LinearRing another
3. Topology-based: an open LineString processed one way, a closed LineString and a LinearRing in another

Instead of relying on the brittle typeId design it might be better to provide methods to distinguish these cases.