polygon-clipping
polygon-clipping copied to clipboard
mfogel
'Unable to find segment' on 0.14.3
Error: Unable to find segment #2675 [1322.452313, -830.650408] -> [1322.452315, -891.150407] in SweepLine tree. Please submit a bug report.
v0.14.3 on Chrome 83.0.4103.97 on MacOS 10.14.6.
operation.run('union', geom, moreGeoms);
throws the above exception. Case is a set of nearly (should be) rectilinear boxes, aligned to the Y axis.
geom
[
[
[
[
1325.952314,
-192.150409
],
[
1325.952323,
-584.650409
],
[
1322.452332,
-584.650409
],
[
1322.452323,
-192.150409
],
[
1325.952314,
-192.150409
]
]
]
]
moreGeoms (length = 10)
[
[
[
[
[
1325.952323,
-588.150409
],
[
1325.952327,
-745.650409
],
[
1322.452322,
-745.650409
],
[
1322.452318,
-588.150409
],
[
1325.952323,
-588.150409
]
]
]
],
[
[
[
[
1325.952327,
-749.150409
],
[
1325.952329,
-804.650409
],
[
1322.452319,
-804.650409
],
[
1322.452317,
-749.150409
],
[
1325.952327,
-749.150409
]
]
]
],
[
[
[
[
1325.952329,
-808.150409
],
[
1325.952329,
-827.150408
],
[
1322.452317,
-827.150408
],
[
1322.452317,
-808.150409
],
[
1325.952329,
-808.150409
]
]
]
],
[
[
[
[
1325.952329,
-830.650407
],
[
1325.952331,
-891.150407
],
[
1322.452315,
-891.150407
],
[
1322.452313,
-830.650407
],
[
1325.952329,
-830.650407
]
]
]
],
[
[
[
[
1325.952314,
-192.150409
],
[
1322.452323,
-192.150409
],
[
1322.452323,
-188.650418
],
[
1325.952314,
-188.650418
],
[
1325.952314,
-192.150409
]
]
]
],
[
[
[
[
1322.452318,
-584.650404
],
[
1325.952323,
-584.650404
],
[
1325.952324,
-588.150409
],
[
1322.452319,
-588.150409
],
[
1322.452318,
-584.650404
]
]
]
],
[
[
[
[
1322.452317,
-749.150409
],
[
1322.452317,
-745.650399
],
[
1325.952327,
-745.650399
],
[
1325.952327,
-749.150414
],
[
1322.452322,
-749.150414
],
[
1322.452322,
-749.150409
],
[
1322.452317,
-749.150409
]
]
]
],
[
[
[
[
1322.452317,
-808.150409
],
[
1322.452317,
-804.650397
],
[
1325.952329,
-804.650397
],
[
1325.952329,
-808.150419
],
[
1322.452319,
-808.150419
],
[
1322.452319,
-808.150409
],
[
1322.452317,
-808.150409
]
]
]
],
[
[
[
[
1322.452313,
-830.650408
],
[
1322.452313,
-827.150392
],
[
1325.952329,
-827.150392
],
[
1325.952329,
-830.650421
],
[
1322.452317,
-830.650421
],
[
1322.452317,
-830.650408
],
[
1322.452313,
-830.650408
]
]
]
],
[
[
[
[
1322.452315,
-891.150407
],
[
1325.952331,
-891.150407
],
[
1325.952331,
-894.650423
],
[
1322.452315,
-894.650423
],
[
1322.452315,
-891.150407
]
]
]
]
]
I also get this on "version": "0.14.3",
const srcArea = [
[
[
[19468643.35117507, -4992560.939474564],
[19468643.35117508, -4992866.687587708],
[19468816.852347407, -4992866.687587708],
[19468816.852347407, -4992560.939474564],
[19468643.35117507, -4992560.939474564],
],
],
] as any;
const clip = [
[
[
[19468511.104234356, -4992713.813531134],
[19468511.104234356, -4992560.939474564],
[19468663.978290927, -4992560.939474564],
[19468663.978290927, -4992713.813531134],
[19468511.104234356, -4992713.813531134],
],
],
] as any;
intersection(srcArea, clip);
Unable to find segment #9 [19468643.35117507, -4992713.813531134] -> [19468663.978290927, -4992713.813531134] in SweepLine tree. Please submit a bug report.
at SweepLine.process (/home/geoffj/src/basemaps/node_modules/polygon-clipping/dist/polygon-clipping.cjs.js:1544:24)
at Operation.run (/home/geoffj/src/basemaps/node_modules/polygon-clipping/dist/polygon-clipping.cjs.js:1766:35)
at intersection (/home/geoffj/src/basemaps/node_modules/polygon-clipping/dist/polygon-clipping.cjs.js:1805:20)
at /home/geoffj/src/basemaps/packages/cli/src/cog/__test__/cutline.test.ts:110:13
at processTicksAndRejections (internal/process/task_queues.js:79:11)
@mfogel Any ETA on a fix for this? This is a pretty critical bug in our project, and is causing some problems. If no fix is incoming, is there some sort of workaround to avoid the bug?
Hi @stephenpassero
I don't have any time available to fix bugs for this project for the foreseeable future. However, any pull request that
- doesn't break any of the existing tests
- fixes a bug, and includes a test case to prove it does so
would be very much appreciated!
As far as workarounds... AFAIK all open bugs on this project are caused by poor interaction between floating-point math and the algorithm this project implements. It often works to just 'jiggle' the coordinates a bit to avoid these bugs. For example:
- try rounding all the coordinates to X decimals before doing the operation
- try adding 100 to all the coordinates, do the operation, then subtract 100 from all the coordinates
- multiply all the coordinates by -1, do the operation, then multiply by -1 again
- etc...
OK. Right from the start there are issues in the comparison of points in the rounder due to the floating point numbers. For example, comparing the following two numbers. Are these equal?
prev 19468643.351175074 19468643.35117507
Obviously, the comparison of these values should be based on some kind of epsilon, and not the default comparison of SplayTree.
P.S. That message above means that the second value was dropped, favoring the left value in the Splaytree. And guess what? The example from @jacott fails later with "Unable to find segment 9 [19468643.35117507 , -4992713.813531134]"
poor interaction between floating-point math and the algorithm this project implements.
I generate polygons from line strings by buffering them in one of my analytic projects and I've encountered several problems with this library all probably due to this as well. My hack workaround is catch errors and apply a small buffer and try again, which works... obviously but manipulating the original object.
My thoughts is... if the library is so sensitive to floating point errors, perhaps it could utilise a library like BigNumber.js to avoid floating-point errors. Due to potential performance hit by using a BigNumber library, perhaps it could be an option that can be configured depending on the use-case. What are your thoughts?
