Port robust determinant fixes from JTS

[strk]

See ​http://sourceforge.net/p/jts-topo-suite/code/626/ with log "Switched to using DD orientation predicate"

[strk]

may fix #602 (to be checked)

[robe]

this is another where there seems to be no quick hope in site. Push.

[mloskot]

A curious test case of point on segment intersection. Current test based on CGAlgorithms is failing. May be useful to check it with the planned extended precision implementation.

[mloskot]

Picture showing the point on line situation from the test cases in the patch

[mloskot]

For comparison, I've run test cases from the geos_3.4_GEOSPreparedGeometryTest.cpp.patch with PostGIS:

• object::test<7> case return false & false

-- POINT located between 3rd and 4th vertex of LINESTRING
SELECT
  ST_Intersects(
    ST_GeomFromWKB(decode('01010000009a266328061c37c0e21a172f80424940', 'hex'), 0),
    ST_GeomFromWKB(decode('0102000000070000009909bf203f1f37c05c1d66d6954249404afe386d871d37c0a7eb1124b54149409c266328061c37c056d8bff5db42494098266328061c37c0034f7b5c2a42494060065c5aa01837c08ac001de3a4449408401b189bb1637c0b04e471a4f43494014ef84a6d11537c0b20dabfb62434940', 'hex'), -1)) as point_line,
  ST_Intersects(
    ST_GeomFromWKB(decode('0102000000070000009909bf203f1f37c05c1d66d6954249404afe386d871d37c0a7eb1124b54149409c266328061c37c056d8bff5db42494098266328061c37c0034f7b5c2a42494060065c5aa01837c08ac001de3a4449408401b189bb1637c0b04e471a4f43494014ef84a6d11537c0b20dabfb62434940', 'hex'), -1),
    ST_GeomFromWKB(decode('01010000009a266328061c37c0e21a172f80424940', 'hex'), 0)) as line_point;

• object::test<8> case return true & true

-- POINT located on the 3rd vertex of LINESTRING
SELECT
  ST_Intersects(
    ST_GeomFromWKB(decode('01010000009c266328061c37c056d8bff5db424940', 'hex'), 0),
    ST_GeomFromWKB(decode('0102000000070000009909bf203f1f37c05c1d66d6954249404afe386d871d37c0a7eb1124b54149409c266328061c37c056d8bff5db42494098266328061c37c0034f7b5c2a42494060065c5aa01837c08ac001de3a4449408401b189bb1637c0b04e471a4f43494014ef84a6d11537c0b20dabfb62434940', 'hex'), -1)) as point_line,
  ST_Intersects(
    ST_GeomFromWKB(decode('0102000000070000009909bf203f1f37c05c1d66d6954249404afe386d871d37c0a7eb1124b54149409c266328061c37c056d8bff5db42494098266328061c37c0034f7b5c2a42494060065c5aa01837c08ac001de3a4449408401b189bb1637c0b04e471a4f43494014ef84a6d11537c0b20dabfb62434940', 'hex'), -1),
    ST_GeomFromWKB(decode('01010000009c266328061c37c056d8bff5db424940', 'hex'), 0)) as line_point;

The results are consistent with the results currently returned by GEOS.

[mloskot]

JTS-style XML file with the two test cases of Point on Segment and Point on Vertex of Segment. All pass with JTS 1.14

[mloskot]

JTS-style XML file with the two PreparedGeometry test cases of Point on Segment and Point on Vertex of Segment. All pass with JTS 1.14

[strk]

Not sure is related, but see also #694 for a case of "prepared" intersection involving points giving an unexpected result when fixed to really use the prepared code.

[mloskot]

I'm puzzled. I believe the two XML test files, TestIntersectsPL.xml TestPreparedIntersectsPL.xml, would be an equivalent to test<7> and test<8> from the geos_3.4_GEOSPreparedGeometryTest.cpp.patch. But, not quite.

The test<7> from GEOSPreparedGeometryTest fails indicating point on segment do not intersect, whereas the same test defined in the XML file pass

xmltester.exe TestIntersectsPL.xml TestPreparedIntersectsPL.xml
Files: 2
Tests: 4
Failed: 0
Succeeded: 4

Apart from constructing geometry object from WKB in the C++ test vs WKT in the XML test, what makes the result different?

BTW, the tests defined in XML also pass with JTS 1.14 (SVN trunk).

[strk]

XML can request fixed precision (check PrecisionModel tag). Also the WKB vs. WKT seem important to me when the test is about finding a point being on a line or not...

[mloskot]

Replying to strk:

XML can request fixed precision (check PrecisionModel tag).

I declare FLOATING first.

Also the WKB vs. WKT seem important to me

Yes, certainly. But, if JTS does not test such cases with binary-based representation of geometries, then the robust determinant computation in JTS may still be missing to capture such cases properly.

I will have to try JTS with the WKB input and see if the DoubleDouble based CGAlgorithmsDD::orientationIndex can handle those cases indeed.

[mloskot]

Small change to LineIntersector::hasIntersection performs double-check, if orientationIndex fails to determine points are collinear. This addition solves the problem in GEOSPreparedGeometryTest.cpp/test<7>. However, it makes the hasIntersection test too strict for cases like in tests/unit/algorithm/RobustLineIntersectorTest.cpp:247

[mloskot]

Patch with the infamous point-on-segment test (plus two others) for the JTS, with geometries in WKB format. RESULT: The JTS 1.14 fails the test with the same incorrect results as GEOS. So, the DoubleDouble support in JTS does not help much for the numerical robustness in this particular case.

[mloskot]

Folks,

I have gathered all my patches and findings related to this issue in two GEOS branches on GitHub, submitted as pull requests so it's easier to review the code and try it out if anyone is interested:

• Port DoubleDouble and CGAlgorithmsDD support

​https://github.com/libgeos/libgeos/pull/40

• Improve points co-linearity test in LineIntersector::hasIntersection

​https://github.com/libgeos/libgeos/pull/41

[mloskot]

The two test cases with point-on-segment and point-on-vertext have been refactoried according to Martin Davis' suggestions (see ​https://github.com/libgeos/libgeos/pull/40) and added to the tests in r4038.

This ticket remains open until complete or partial DD support is added (again, see ​https://github.com/libgeos/libgeos/pull/40)

[strk]

Ticket retargeted after milestone closed

[robe]

Are there any plans to do this or should I just push to the fundme category.

I'm also unclear if this is partly done or completely done since the

​https://github.com/libgeos/libgeos/pull/40 is closed

[Paul Ramsey <pramsey@…>]

In 842593e/git:

Add robust determinant test files
References #591

[pramsey]

Test cases pass and ttmath was added in the fall.