Crash in polygon.contains(linestring)

[dabreegster]

To reproduce, clone https://github.com/dabreegster/georust_crash and cargo run. The input coordinates are Euclidean, relative to a 0,0 origin. I tried a few online WKT viewers, but all of them need some kind of CRS. I'll try the JTS one later and try to understand the problem.

geo-0.29.1/src/algorithm/relate/geomgraph/edge_end_bundle_star.rs:112:21:
side_location conflict with coordinate: Coord { x: 306.05652706452844, y: 848.7298084068675 }, right_location: Inside,  current_location: Outside

[urschrei]

JTS thinks The polygon's invalid:

Ring self-intersection at or near point (293.0157983578036, 694.0574518014394, NaN)

[urschrei]

If you "fix" the input Polygon (which will split it into a MultiPolygon with a little triangular outlier beneath the main geometry):

MULTIPOLYGON (((287.04945188989086 726.0816349092227, 283.9810451357949 736.7563626115539, 278.09993218862735 747.3198952339321, 277.33283050070895 748.3206509558775, 272.3892862853728 754.7699656089412, 264.63303587696504 761.2192802627951, 251.67754069098544 768.4469604778985, 267.957143194508 769.7813014404924, 273.4120885367381 771.6716178044305, 278.27039923132907 774.1179095697125, 283.3844104881557 778.4545176989327, 287.1346854106361 781.567979945512, 297.87410905239454 795.3561698944221, 287.04945188989086 726.0816349092227)), ((306.05652706452844 848.7298084068675, 307.76119748306695 859.7381213498469, 316.9664177465662 922.8969269226309, 326.4273385735124 985.277366933375, 328.3877095554978 997.953606080387, 338.3600315081266 996.5080700370502, 395.80742463576564 988.0572439393056, 401.85900462321246 987.167683297313, 465.7841453444469 977.7161014776229, 478.56917348772475 975.825785113685, 480.18861038672924 986.6117078959688, 498.5990509137277 1110.260637115559, 500.47418837496787 1122.9368762625709, 502.26409231546285 1135.8355055694883, 521.2711674888892 1262.0419216343134, 523.4872390343216 1276.9420623859119, 534.5675967590611 1275.3853312626222, 599.7712402938965 1265.8225543621893, 597.6404022704206 1251.478389012725, 588.0090144007727 1185.984486754612, 679.4645823917597 1172.5298820463504, 728.3886234230725 1165.3022018312467, 738.531412417192 1163.7454707079573, 747.8218662026476 1162.4111297453633, 812.1731745276082 1152.8483528449303, 875.7573811634393 1143.5079661059833, 885.8149366368134 1142.0624300626464, 960.0533333936577 1131.054117119667, 950.5071790459663 1065.8938001029924, 949.6548438360912 1059.8892657697397, 958.6895970581 1058.5549248071459, 989.5441316453954 1053.99592651802, 1006.5908358380477 1051.4384396719952, 1019.6315645447726 1049.5481233080573, 1025.5979110126852 1044.6555397782831, 1033.2689278991365 1043.321198814899, 1031.9904250843242 1034.425592396553, 1026.5354797433054 997.953606080387, 1073.0729821876955 990.7259258644933, 1113.8146052056632 984.3878062913824, 1120.1218857577683 983.387050569437, 1113.3032040799806 937.9082627541821, 1112.8770364750433 934.9059955875558, 1104.9503190263563 881.9771373965018, 1115.263575061966 880.4204062732122, 1126.429166308662 878.7524800699699, 1188.6496366089355 869.3008982494898, 1186.8597326696517 857.0694394238691, 1184.9845952084115 844.0596150369988, 1179.614883388138 807.365238559347, 1179.4444163454361 806.4756779181445, 1177.9102129683881 795.5785600551177, 1176.2055425486385 784.3478569514425, 1175.0122732557827 776.2306160943463, 1173.819003962927 767.668594916649, 1172.029100022432 755.3259410102853, 1169.5573279147638 738.7578740554447, 1130.1794412311422 744.5400182280016, 1114.7521739362833 746.763919832588, 1064.7200971328598 754.1027951276444, 950.3367120044758 771.1156424038763, 903.2025749124464 777.7873472176357, 893.4007200025194 778.8992980203241, 884.7069008647028 779.010493100277, 877.0358839782516 778.1209324582842, 867.4044961098148 775.897030853698, 854.8751685287727 772.1163981258217, 842.6867750307115 770.3372768418367, 836.8908956055004 769.8924965212354, 831.0950161802893 770.1148866811411, 820.1851254970405 771.7828128851734, 817.2871857844349 772.2275932057746, 757.2827870283826 781.456784865559, 727.5362882131976 786.0157831546846, 694.6361491231717 791.0195617652018, 683.7262584399227 792.6874879692343, 672.8163677566738 794.2442190925237, 662.3326446783622 795.9121452957662, 646.5644433005223 798.2472419803054, 618.2669143428515 802.4726550295727, 580.9346321619606 807.921213960691, 568.9167057066011 809.7003352446762, 558.1772820648426 811.3682614479187, 539.8520750585894 814.0369433738965, 533.3743274662053 815.0376990958418, 469.36395322422555 824.6004759962747, 456.40845803824595 826.4907923602127, 443.3677293315211 828.3811087241506, 379.61305565298835 837.610300383145, 372.794373976412 838.7222511858333, 354.2134664067118 841.6133232717167, 316.4550166208835 847.173077283578, 306.05652706452844 848.7298084068675)))

You'll get this result from JTS:

[dabreegster]

I added https://github.com/dabreegster/georust_crash/blob/main/polygon.geojson. I'm not surprised that it's invalid; the left corner has an infinitely thin line and a second blob:

It's produced from a tool that doesn't yet guarantee any kind of valid output.

At a glance, I don't see a public API to detect invalid polygons. If we had one, we could call it and immediately bail out from geomgraph operations, maybe? Or in any case, crashing is bad -- should contains and other APIs return results? Or detect invalid inputs and return false (but that could be confusing)?

[urschrei]

There are third-party Rust (and cpp) libraries (of varying sophistication) available. Prepair is very good but is cpp, https://github.com/mthh/geo-validity-check wraps GEOS so probably isn't what you want. The downside is that a full validity check / repair is slow, so you probably wouldn't want to run the check by default. Which brings us back to questions about catching panics and / or returning Result in those cases.

In any case the sensible approach is probably to have a look at what Prepair / ST_MAKEVALID do and emulate that in pure Rust if possible. I believe both approaches are based on constrained Delaunay triangulations which are now available to us in geo via Spade (https://docs.rs/spade/latest/spade/struct.ConstrainedDelaunayTriangulation.html).

[urschrei]

This looks kinda rudimentary but may work for most cases, and is pure Rust and MIT:

https://gitlab.com/bronsonbdevost/rust-geo-repair-polygon

[dabreegster]

Thank you! In the very short term, I'll detect/repair using something pure Rust. In the slightly longer term, make https://github.com/dabreegster/route_snapper/ produce valid polygons by construction.

The question remaining for here -- panicking on invalid inputs is quite bad. Catching panics is tricky from WASM last time I tried (though I think I saw some updated method that might work). I'd vote for returning Result, but it's a huge breaking API change.

[urschrei]

I agree re: panics, and I think I'd rather break the API with a catch-panic-and-return-Result change for boolean ops. I think it was proposed back when our bool ops were kinda shaky but don't recall why we didn't do it then. I know it's a big breaking change, but the user experience of panics is…bad.

[frewsxcv]

For anyone else who is curious, here is the line that caused the panic:

geo/geo/src/algorithm/relate/geomgraph/edge_end_bundle_star.rs

Line 112 in 2537a07

debug_assert!(right_position == current_position, "side_location conflict with coordinate: {:?}, right_location: {:?}, current_location: {:?}", edge_ends.coordinate(), right_position, current_position);

[michaelkirk]

I'm traveling for a couple weeks and probably won't be able to look deeply into this until I return.

As a rule I work to avoid crashing in release builds, but I'm pretty loose with debug_asserts. They can catch bugs while typically not endangering production usage.

Are you seeing this debug_assert! panic in your release wasm builds @dabreegster or did this occur while running a debug build?

[michaelkirk]

change for boolean ops. I think it was proposed back when our bool ops were kinda shaky but don't recall why we didn't do it then

Just in case there's confusion - this panic looks to be in the geomgraph code, not the boolops code.

[dabreegster]

Are you seeing this debug_assert! panic in your release wasm builds @dabreegster or did this occur while running a debug build?

... Ah, good catch. Actually it doesn't crash in release mode, and the results look correct to me (functionally, linestring containment in the two pieces of the polygon is OK). I hadn't noticed because I've always been compiling in debug mode when I develop.

I'm pretty loose with debug_asserts. They can catch bugs while typically not endangering production usage.

That seems reasonable for a self-contained library, but for a widely used one, it can make for a confusing developer experience! Any opinions on

1. using log::error instead
2. An opt-in feature flag to guard the use of debug_assert

[michaelkirk]

My immediate feeling is that this seems to be pretty much what debug asserts are for, and having them results in fixing bugs. I can see how it’s confusing if you aren’t familiar with them though. Maybe this one in particular needs to be re-examined?FYI  - it is possible to disable them at build time if you don’t like them.

[dabreegster]

This particular one did reveal invalid inputs, which are nice to flag. Maybe then the resolution to this issue is just a docstring update to the tune of This method may crash for invalid inputs when debug assertions are enabled. To disable this behavior, configure [debug-assertions = false](https://doc.rust-lang.org/cargo/reference/profiles.html#debug-assertions) in your Cargo.toml

[frewsxcv]

Before we go that route, we should decide if we should instead return a Result::Err if we detect an invalid state. Because if we do, then that would obviate the need for this docstring altogether since we would be returning an Err.