Failing `debug_assert` in `XSegment::is_under_point`

[michaelkirk]

Failing assert: debug_assert!(self.a.x <= p.x && p.x <= self.b.x);

I'm working on integrating iOverlay into https://github.com/georust/geo. A user testing the integration hit this debug_assert.

They provided a reproduction, which can be found here https://github.com/michaelkirk/geo_fail_example

cargo run should trigger it.

[michaelkirk]

I've just now pushed up a simplified example.

My approach to simplify was to just keep deleting rings and points until the failure stopped happening — so all the remaining points are a subset of the initial input.

GeometryA WKT

MULTIPOLYGON(((2.308208703994751 -44.961544036865234,37.17605972290039 -16.19365692138672,33.88911819458008 -25.311290740966797,33.86614990234375 -25.540952682495117,40.45701217651367 -15.621655464172363,46.20624923706055 -37.305298805236816,2.308208703994751 -44.961544036865234)),((11.95650577545166 14.7280387878418,30.346940994262695 38.30845260620117,38.4443359375 40.48749923706055,41.69062423706055 18.96145248413086,33.89716720581055 20.76250076293945,11.95650577545166 14.7280387878418),(35.20156717300415 39.084500551223755,30.97531795501709 38.142252922058105,34.15063834190369 21.34823846817017,35.20156717300415 39.084500551223755),(38.073265075683594 39.88750076293945,37.69073486328125 33.43665313720703,37.88459777832031 33.34542465209961,38.073265075683594 39.88750076293945)))

GeometryB WKT

MULTIPOLYGON (((36.77085494995117 -16.330209732055664, 37.04164505004883 -15.794790267944336, 38.42919921875 -16.496543884277344, 40.78192138671875 -18.3913516998291, 40.40557861328125 -18.8586483001709, 38.10205078125 -17.003456115722656, 36.77085494995117 -16.330209732055664)))

Zoomed into the bottom polygon from GeometryA you can see the overlayed GeometryB:

Topologically, it's (maybe) interesting that the hole in the top polygon from GeometryA is vertically above GeometryB

[NailxSharipov]

Thanks a lot for the detailed bug report and for simplifying the example—it was very helpful!

It turns out that the bug was introduced in the last build when I decided that hole anchor points should be sorted, which seemed logical at the time. However, as your example shows, this is not always the case. I've added your test case, and for now, the points will be sorted automatically.

For now, the hotfix(1.7.2) sorts the points to avoid the crash. I'll look into why it's happend more deeply later.

Thanks again for your help!

[TotalKrill]

I am the one who reported the first issue, looking forward to this fix! I just tried patching the entire chain and removing the debug_assert! basically fixed my issue as well! looking forward to this hotfix!

[NailxSharipov]

@michaelkirk One more thing I'd like to mention. It looks like you're adding the first point of a path to the end, but there's no need for that since polygons are already closed when declared. By doing this, you're actually adding extra work for the algorithm, which then has to clean up the path.

If the path isn't simple, the algorithm converts it into a linked list and handles degenerate or parallel cases, which is quite performance-heavy. Most of the time, paths are already simple, but adding the first point again causes unnecessary work to remove it.

[TotalKrill]

The OGC requires polygons to be topologically closed

[michaelkirk]

One more thing I'd like to mention. It looks like you're adding the first point of a path to the end, but there's no need for that since polygons are already closed when declared

You're correct — that's particular to our representation of Polygons. So it sounds like I can just omit that last (redundant) point when I feed them into i_overlay, and they will be implicitly closed.

[michaelkirk]

Thank you for the quick fix!