TypeError: Cannot read properties of undefined (reading 'depth')

[platypii]

I think I found a bug that results in an exception being thrown. It happens when doing a union of two polygons. The polygons in this example have a co-linear edge, although I don't know if that's relevant.

I made a test case which demonstrates the problem. Add this under test/genericTestCases/colinear.json:

{
  "features": [
    {
      "geometry": {
        "coordinates": [
          [
            [ -5, 0 ],
            [ 4.707106781186547, 0.7071067811865477 ],
            [ 3.477592250072517, 0.7836116248912244 ],
            [ 4, 1 ],
            [ -5, 0 ]
          ]
        ],
        "type": "Polygon"
      },
      "properties": {},
      "type": "Feature"
    },
    {
      "geometry": {
        "coordinates": [
          [
            [ 4.707106781186547, 0.7071067811865477 ],
            [ 4, 1 ],
            [ 0, 1 ],
            [ 4.707106781186547, 0.7071067811865477 ]
          ]
        ],
        "type": "Polygon"
      },
      "properties": {},
      "type": "Feature"
    },
    {
      "geometry": {
        "coordinates": [
          [
            [
              [ -5, 0 ],
              [ 4.707106781186547, 0.7071067811865477 ],
              [ 4, 1 ],
              [ 0, 1 ],
              [ 2.564081902288895, 0.8404535446987661 ],
              [ -5, 0 ]
            ]
          ]
        ],
        "type": "MultiPolygon"
      },
      "properties": {"operation": "union"},
      "type": "Feature"
    }
  ],
  "type": "FeatureCollection"
}

Running npm test then gives the exception:

/code/martinez/src/connect_edges.js:121
      contour.depth = contours[lowerContourId].depth;
                                               ^

TypeError: Cannot read properties of undefined (reading 'depth')
    at initializeContourFromContext (/code/martinez/src/connect_edges.js:121:48)
    at connectEdges (/code/martinez/src/connect_edges.js:150:21)
    at boolean (/code/martinez/src/index.js:76:20)
    at Object.union [as op] (/code/martinez/index.js:10:10)

The exception happens on connect_edges.js line 121 here.

Tracing the error backwards reveals that lowerContourId is set to -1.

[platypii]

Some good old fashioned println in connect_edges.js helps to understand what's happening here. I mapped vertices to letters to make it easier to follow. The operation is a union of polygons ABEC and BCD.

connectEdges sortedEvents = AB,AF,DF,DC,FA,FD,FE,FC,EB,EC,EF,EB,CE,CF,CD,CB,BA,BE,BE,BC
connectEdges resultEvents AB,AF,DF,DC,FA,FD,EC,CE,CD,CB,BA,BC
connectEdges start contour AB
initializeContourFromContext AB
connectEdges process edge AB
connectEdges process edge BC
connectEdges process edge CD
connectEdges process edge DF
connectEdges process edge FA
connectEdges output contour ABCDFA
connectEdges unprocessed edges: EC,CE
connectEdges start contour EC
initializeContourFromContext EC
Error: invalid lowerContourId -1
TypeError: Cannot read properties of undefined (reading 'depth')

The subdivision step seems okay. Inside connectEdges, the implementation finds the correct polygon ABCDF first. But then there is a leftover edge EC, and the implementation doesn't handle it properly and crashes. I am still working on understanding the algorithm, but it seems like either 1) the edge EC should have been filtered out of resultEvents as part of the orderEvents function at the beginning, or 2) it should have been pruned when EC gets processed later.

[platypii]

Even simpler example:

Which can be reproduced using:

const boolean = require('martinez-polygon-clipping')

const poly1 = [[
  [ 4.707106781186547, 0.7071067811865477 ], // B
  [ 4, 1 ], // C
  [ 3.05083120710486, 0.8101662414209719 ], // G
  [ 4.707106781186547, 0.7071067811865477 ] // B
]]
const poly2 = [[
  [ 2, 0.75 ], // A
  [ 4.707106781186547, 0.7071067811865477 ], // B
  [ 3.477592250072517, 0.7836116248912244 ], // E
  [ 4, 1 ], // C
  [ 2, 0.75 ] // A
]]

const out = boolean.union(poly1, poly2)

TypeError: Cannot read properties of undefined (reading 'depth')

There seems to be an issue with the order in which nodes are processed for splitting GB at point E. Will continue digging...

[platypii]

I have isolated the cause of this bug. The implementation of segment_intersection returns no intersections for edges EB and GB.

A minimal failing test case can be added to segment_intersection.test.js:

  const E = [3.477592250072517, 0.7836116248912244];
  const B = [4.707106781186547, 0.7071067811865477];
  const G = [3.05083120710486, 0.8101662414209719];
  t.deepEqual(intersection(E, B, G, B, true), [E, B], 'partial overlap');

This happens because the check for parallel lines is strict if (sqrKross > 0). Unfortunately computing the cross product is prone to catastrophic cancellation. Since the cross product is the difference of two large numbers, floating point errors make it unlikely that the cross product comes out to exactly zero, even if the lines are actually parallel.

I wanted to see if this was a problem specific to w8r/martinez or if it was a more general problem across implementations. The reference C++ implementation, and the other javascript implementations all handled this case correctly. Interestingly, the only implementation I found that also crashed on this example was the rust 21re/rust-geo-booleanop which is ported directly from this repo.

• w8r/martinez implementation of segment_intersection determines if segments are parallel when the cross product is 0. No epsilon check, although it has one commented out.
  

  martinez/src/segment_intersection.js

  Line 81 in 738a698

  if (sqrKross > 0/* EPS * sqrLenB * sqLenA */) {

• mfogel/polygon-clipping explicitly checks for T interections. So it doesn't depend on epsilon at all for intersection checks. Very interesting.
  https://github.com/mfogel/polygon-clipping/blob/main/src/segment.js#L246-L255

• velipso/polybooljs does a check on the cross product, but with epsilon
  https://github.com/velipso/polybooljs/blob/master/lib/epsilon.js#L74

• The martinez C++ reference implementation does an epsilon check
  https://github.com/akavel/martinez-src/blob/master/cageo141/utilities.cpp#L45

I think the answer is to un-comment the epsilon check here. However, the mfogel implementation of getIntersection is quite interesting too.

[w8r]

Thank you so much! I will try to run the tests with it

…

On Thu, 12 Jan 2023 at 07:06, Kenny ***@***.***> wrote: I have isolated the cause of this bug. The implementation of segment_intersection returns no intersections for edges EB and GB. A minimal failing test case can be added to segment_intersection.test.js: const E = [3.477592250072517, 0.7836116248912244]; const B = [4.707106781186547, 0.7071067811865477]; const G = [3.05083120710486, 0.8101662414209719]; t.deepEqual(intersection(E, B, G, B, true), [E, B], 'partial overlap'); This happens because the check for parallel lines is strict if (sqrKross > 0). Unfortunately computing the cross product is prone to catastrophic cancellation <https://en.wikipedia.org/wiki/Catastrophic_cancellation>. Since the cross product is the difference of two large numbers, floating point errors make it unlikely that the cross product comes out to exactly zero, even if the lines are actually parallel. I wanted to see if this was a problem specific to w8r/martinez or if it was a more general problem across implementations. The reference C++ implementation, and the other javascript implementations all handled this case correctly. Interestingly, the only implementation I found that also crashed on this example was the rust 21re/rust-geo-booleanop which is ported directly from this repo. - w8r/martinez implementation of segment_intersection determines if segments are parallel when the cross product is 0. No epsilon check, although it has one commented out. https://github.com/w8r/martinez/blob/738a698a49f21d7e9f631ce435a12bdbde3ebff0/src/segment_intersection.js#L81 - mfogel/polygon-clipping explicitly checks for T interections. So it doesn't depend on epsilon at all for intersection checks. Very interesting. https://github.com/mfogel/polygon-clipping/blob/main/src/segment.js#L246-L255 - velipso/polybooljs does a check on the cross product, but with epsilon https://github.com/velipso/polybooljs/blob/master/lib/epsilon.js#L74 - The martinez C++ reference implementation does an epsilon check https://github.com/akavel/martinez-src/blob/master/cageo141/utilities.cpp#L45 I think the answer is to un-comment the epsilon check here <https://github.com/w8r/martinez/blob/738a698a49f21d7e9f631ce435a12bdbde3ebff0/src/segment_intersection.js#L81>. However, the mfogel implementation of getIntersection is quite interesting too. — Reply to this email directly, view it on GitHub <#155 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAAGSBBMBAIBJ5YXIW6EYOLWR6NO3ANCNFSM6AAAAAATORIAJU> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>