Very thin polygon can cause error to be thrown

[mfogel]

The following input polygon results in a crash with a SweepEvent comparison failed at [-130.73939947890625,54.91877729166476]... equal but not identical? error being thrown:

[[
   [-130.73862770644791, 54.92404227517194],
   [-130.73939947890625, 54.91877729166476],
   [-130.73939947890625, 54.918777291664775],
   [-130.73862770644791, 54.92404227517194]
]]

What's going on is that:

• the points are each being identified as different by the floating point lib (even the middle two points: [-130.73939947890625, 54.91877729166476] and [-130.73939947890625, 54.918777291664775])
• but these line segments are being identified as parallel, which causes the sweep line algorithm to barf as it tries to sort them (hence the sweep event comparison error)
  • [ -130.73939947890625, 54.91877729166476 ] -> [ -130.73939947890625, 54.918777291664775 ]
  • [ -130.73939947890625, 54.91877729166476 ] -> [ -130.73862770644791, 54.92404227517194 ]

Right now, when input points are consumed a check is being done to (silently!) drop repeated points. It should be safe to also (silently!) drop colinear points.

If a ring is shortened to two or fewer points because of the above checks, it should be dropped altogether.

[erikh2000]

Mike, I left you hanging with the bug I offered to report, but this looks like the same thing to me. Happy to see you making progress. Floating point in JS seems to be a horror show. Both JSTS and ClipperLib clipping functions fail with high-precision numbers. My project has used a workaround of converting to integers with truncation at 12 digits, performing the operation, and then converting back. But maybe floating point lib is the way to go.

[mfogel]

@erikh2000 so far I've been able to find a fix for every floating point error I've ran across, but I suspect at a significant performance hit. Not sure if you saw on the other thread but it looks like this library is currently running almost 20x slower than the one it was forked from.

I've been trying to avoid truncating/rounding as that can introduce issues of its own (ie. points that were different are now the same, or segments that were not overlapping or colinear, now they are).

Please let me know if you find any more input geometries that cause trouble!

[erikh2000]

Mike, I am in the camp of wanting a reliable set of clipping functions first, and performance second. I think most of the web world is using clipping in JS for visualization, where it's just not that horrible if clipping fails on occasion. But my project uses clipping to send automated machinery out to plant seed and fertilizer on farms. If the geometry is wrong, some poor farmer somewhere loses money due to the bug. It actually keeps me up at night sometimes.

So you say 20x slower, and I agree that's not great, but at the same time... I cannot find one clipping library in the entire JS ecosystem that is just simply reliable, e.g. handles all of the normal cases and edge cases with predictable results and no mysterious errors deep down in the bowels. Maybe yours (building on the work of Alexander, Rowan, of course) could be the first one!

Re truncating/rounding, I agree it is problematic. Just as you say, I've found I need to do extra checks on the resulting polygon to make sure it is appropriate to pass to the clipping function. I hope you continue to find your floating point issues solvable.

Re input geometries that cause trouble. At some point, I would like to hook up my test suite to mfogel/polygon-clipping and see how it does. I've got over a hundred tests for clipping operations, and so far, no clipping library I've tried has passed them all (Turf 3.x, Turf 5.x, ClipperLib, w8r/martinez with various combinations of PRs). Of course, any failures I find, I'll be happy to pass along test cases.

[munrocket]

@erikh2000 @mfogel you can use double.js for extended precision, it's extremely fast.