Opened 6 years ago

Last modified 4 months ago

#591 new defect

Port robust determinant fixes from JTS

Reported by: strk Owned by: geos-devel@…
Priority: major Milestone: 3.8.0
Component: Default Version: 3.3.5
Severity: Unassigned Keywords:
Cc:

Description (last modified by mloskot)

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

Attachments (6)

geos_3.4_GEOSPreparedGeometryTest.cpp.patch (2.8 KB) - added by mloskot 4 years ago.
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.
vis-data-from-the-test-case-in-patch.png (22.7 KB) - added by mloskot 4 years ago.
Picture showing the point on line situation from the test cases in the patch
TestIntersectsPL.xml (1.3 KB) - added by mloskot 4 years ago.
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
TestPreparedIntersectsPL.xml (1.4 KB) - added by mloskot 4 years ago.
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
LineIntersector_triangle_area_close_to_zero_is_collinear-r4037.patch (4.0 KB) - added by mloskot 4 years ago.
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
algorithm-test-point-on-segment.patch (4.3 KB) - added by mloskot 4 years ago.
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.

Download all attachments as: .zip

Change History (22)

comment:1 Changed 6 years ago by strk

Milestone: 3.3.63.3.7

comment:2 Changed 6 years ago by strk

may fix #602 (to be checked)

comment:3 Changed 6 years ago by strk

Milestone: 3.3.73.3.x

comment:4 Changed 5 years ago by robe

Milestone: 3.3.93.5.0

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

Changed 4 years ago by 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.

Changed 4 years ago by mloskot

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

comment:5 Changed 4 years ago by mloskot

Description: modified (diff)

comment:6 Changed 4 years ago by 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.

Changed 4 years ago by mloskot

Attachment: TestIntersectsPL.xml added

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

Changed 4 years ago by 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

comment:7 Changed 4 years ago by 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.

comment:8 Changed 4 years ago by 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).

comment:9 Changed 4 years ago by 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...

comment:10 in reply to:  9 Changed 4 years ago by 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.

Changed 4 years ago by 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

Changed 4 years ago by 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.

comment:11 Changed 4 years ago by 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:

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

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

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

comment:12 Changed 4 years ago by 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)

comment:13 Changed 3 years ago by robe

Milestone: 3.5.03.6.0

comment:14 Changed 2 years ago by strk

Milestone: 3.6.03.7.0

Ticket retargeted after milestone closed

comment:15 Changed 6 months ago by 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

comment:16 Changed 4 months ago by robe

Milestone: 3.7.03.8.0
Note: See TracTickets for help on using tickets.