Precision error causing polygons to not intersect

[tokheim]

A polygon containing another polygon with (almost) touching edges might in rare circumstances be viewed as disjoint. This happens when LineIntersector finds all vertices to be inside the polygon, while RayCrossingCounter finds a vertex to be outside. Example Polygons:

0103000000010000000400000001DA86DAF74BA83F2FA9595EF7FE1F408CF48F8922722440C9D18A61E80A41400000000000002440000000000000244001DA86DAF74BA83F2FA9595EF7FE1F40

010300000001000000040000000000000000002E400000000000001440FC0000505D92843FFFFF7762C29C1F40020018EA49852440000008012F1741400000000000002E400000000000001440

To avoid floating point precision errors, LineIntersector and RayCrossingCounter both need to use the same equation to determine which side of a line a point lies. See ​https://github.com/libgeos/libgeos/pull/42 for suggested patch

[strk]

Mateusz you may also be interested in running the test attached to the ticket with the DoubleDouble change in place, as the JTS version of CGAlgorithms.orientationIndex runs CGAlgorithmsDD.orientationIndex, which may help.

Tokheim: it looks like you just moved CGAlgorithms::orientationIndex implementation to RayCrossingCounter, or how did the equation change ? Is the swapping in locatePointInRing what fixes the case ?

[tokheim]

strk: In these floating point precision issues it might very well boil down to which coordinate you subtract by before you send the directional vectors to robustDeterminant. Since RayCrossingCounter and orientationIndex can't use different implementations of this normalization, it should be performed by a common function. This is why the implementation was moved to RayCrossingCounter.

[strk]

Would making RayCrossingCounter use CGAlgorithms implementation also work fine then ? It would seem a much smaller patch, only changing file would be RayCrossingCounter and only within the implementation of a function. Is that correct ?

[tokheim]

Yes, but CGAlgorithms already depend on RayCrossingCounter, so it would require cyclic dependencies or some refactoring. Besides, deciding which side of a line a point is seems to fall well under the domain of a RayCrossingCounter.

[strk]

NOTE: as of rev 926 JTS succeeds in running the testcase attached to the pull request

[strk]

As of rev 926 JTS uses CGAlgirithmsDD.orientationIndex (now I realize I already reported that). Mat, could you try your CGAlgorithmsDD port against the testcase attached to the pull request ?

[strk]

At rev 427 JTS does not use CGAlgorithmsDD and indeed it fails the testcase.

[mloskot]

Tested with x86-64 build of the CGAlgorithmsDD port

xmltester.exe bug716.xml
Files: 1
Tests: 1
Failed: 0
Succeeded: 1

[strk]

Patch by Asmund Tokheim committed as r4039 in 3.4 branch and r4040 in trunk. Thanks Asmund !

[strk]

Ticket retargeted after milestone deleted