turf
turf copied to clipboard
Unable to find segment #244139 [-71.66191017921575, 19.182076213197277] -> [-71.65740874033601, 19.204588002723632] in SweepLine tree
Union boom crash with comment "Unable to find segment #244139 [-71.66191017921575, 19.182076213197277] -> [-71.65740874033601, 19.204588002723632] in SweepLine tree. Please submit a bug report."
- [x] The version of Turf you are using, and any other relevant versions.
npm ls @turf/turf
..
└── @turf/[email protected]
- [ ] GeoJSON data as a gist file or geojson.io (filename extension must be
.geojson
). - [ ] Snippet of source code or for complex examples use jsfiddle. ... naah
it('Should not bug', () => {
const p1 = multiPolygon([
[
[
[-73.06244448903232, 18.596801939748655],
[-73.05407828100999, 18.559574884443432],
[-73.02449897675693, 18.427747962201135],
[-73.00856378482453, 18.50884874486772],
[-72.99260735779502, 18.590014564484544],
[-73.06244448903232, 18.596801939748655],
],
],
[
[
[-73.04849828566886, 19.74713670181383],
[-73.01761830156346, 19.69103613572505],
[-73.03138982758604, 19.750747500261227],
[-73.04849828566886, 19.74713670181383],
],
],
[
[
[-72.65364940830283, 20.124248055459326],
[-72.65319619909113, 20.122267081451863],
[-72.6476195782836, 20.123415333285244],
[-72.65364940830283, 20.124248055459326],
],
],
[
[
[-72.55108447575863, 17.974866348840024],
[-72.45710334056436, 17.97227551144358],
[-72.46320521992928, 17.999399006529142],
[-72.50754265521213, 18.195904425399238],
[-72.51657860925029, 18.150057440187584],
[-72.54370663234872, 18.012340247890656],
[-72.55108447575863, 17.974866348840024],
],
],
[
[
[-71.8267836792031, 20.010057535093836],
[-71.80745153630141, 19.91312439376248],
[-71.78921192211703, 20.004868858937943],
[-71.8267836792031, 20.010057535093836],
],
],
[
[
[-71.66191017921575, 19.182076213197288],
[-71.6562049006765, 19.153360535270046],
[-71.65740874033601, 19.20458800272359],
[-71.66191017921575, 19.182076213197288],
],
],
]);
const p2 = multiPolygon([
[
[
[-73.06244448903232, 18.596801939748655],
[-73.05407828100999, 18.559574884443432],
[-73.02449897675693, 18.427747962201135],
[-73.00856378482453, 18.50884874486772],
[-72.99260735779502, 18.590014564484544],
[-73.06244448903232, 18.596801939748655],
],
],
[
[
[-73.04849828566886, 19.74713670181383],
[-73.01761830156346, 19.691036135725053],
[-73.03138982758604, 19.750747500261227],
[-73.04849828566886, 19.74713670181383],
],
],
[
[
[-72.65364940830283, 20.12424805545933],
[-72.65319619909113, 20.122267081451863],
[-72.6476195782836, 20.123415333285244],
[-72.65364940830283, 20.12424805545933],
],
],
[
[
[-72.55108447575863, 17.974866348840024],
[-72.45710334056436, 17.97227551144358],
[-72.46320521992928, 17.999399006529142],
[-72.50754265521213, 18.195904425399238],
[-72.51657860925029, 18.150057440187584],
[-72.54370663234872, 18.012340247890656],
[-72.55108447575863, 17.974866348840024],
],
],
[
[
[-71.8267836792031, 20.010057535093836],
[-71.80745153630141, 19.913124393762487],
[-71.78921192211703, 20.004868858937943],
[-71.8267836792031, 20.010057535093836],
],
],
[
[
[-71.66191017921577, 19.182076213197277],
[-71.6562049006765, 19.15336053527002],
[-71.65740874033601, 19.204588002723632],
[-71.66191017921577, 19.182076213197277],
],
],
]);
union(p1, p2);
});
@mkorpela indeed a bug. However it looks like the issue is related to the decimals of your coordinates:
const u = turf.union(turf.truncate(p1), turf.truncate(p2))
console.log(JSON.stringify(u))
// {"type":"Feature","properties":{},"geometry":{"type":"MultiPolygon","coordinates":[[[[-73.062444,18.596802],[-73.054078,18.559575],[-73.024499,18.427748],[-73.008564,18.508849],[-72.992607,18.590015],[-73.062444,18.596802]]],[[[-73.048498,19.747137],[-73.017618,19.691036],[-73.03139,19.750748],[-73.048498,19.747137]]],[[[-72.653649,20.124248],[-72.653196,20.122267],[-72.64762,20.123415],[-72.653649,20.124248]]],[[[-72.551084,17.974866],[-72.457103,17.972276],[-72.463205,17.999399],[-72.507543,18.195904],[-72.516579,18.150057],[-72.543707,18.01234],[-72.551084,17.974866]]],[[[-71.826784,20.010058],[-71.807452,19.913124],[-71.789212,20.004869],[-71.826784,20.010058]]],[[[-71.66191,19.182076],[-71.656205,19.153361],[-71.657409,19.204588],[-71.66191,19.182076]]]]}}
Thanks for the tip about the truncate! This bug case from internals of a fairly complex algorithmic manipulation.
I believe I'm hitting the same issue, I hope this information is helpful:
Version: 6.5.0 GeoJSON: https://gist.github.com/btisdall/f09ff07ebddefdc7f1944b1c491b01b2 Reproduction:
const turf = require('@turf/turf')
const feature1 = require('./feature1')
const feature2 = require('./feature2')
turf.difference(feature1, feature2)
Output:
/Users/ben.tisdall/src/me/tsp/node_modules/polygon-clipping/dist/polygon-clipping.cjs.js:1524 if (!node) throw new Error("Unable to find segment #".concat(segment.id, " ") + "[".concat(segment.leftSE.point.x, ", ").concat(segment.leftSE.point.y, "] -> ") + "[".concat(segment.rightSE.point.x, ", ").concat(segment.rightSE.point.y, "] ") + 'in SweepLine tree. Please submit a bug report.'); ^
Error: Unable to find segment #79 [13.502622212711804, 52.56208878589359] -> [13.503085411587817, 52.56225357203965] in SweepLine tree. Please submit a bug report. at SweepLine.process (/Users/ben.tisdall/src/me/tsp/node_modules/polygon-clipping/dist/polygon-clipping.cjs.js:1524:24) at Operation.run (/Users/ben.tisdall/src/me/tsp/node_modules/polygon-clipping/dist/polygon-clipping.cjs.js:1761:35) at Object.difference (/Users/ben.tisdall/src/me/tsp/node_modules/polygon-clipping/dist/polygon-clipping.cjs.js:1816:20) at Object.difference (/Users/ben.tisdall/src/me/tsp/node_modules/@turf/difference/dist/js/index.js:50:57) at Object.
(/Users/ben.tisdall/src/me/tsp/example.js:7:6) at Module._compile (node:internal/modules/cjs/loader:1105:14) at Object.Module._extensions..js (node:internal/modules/cjs/loader:1159:10) at Module.load (node:internal/modules/cjs/loader:981:32) at Function.Module._load (node:internal/modules/cjs/loader:822:12) at Function.executeUserEntryPoint [as runMain] (node:internal/modules/run_main:77:12)
@btisdall have you tried truncating the features?
turf.difference(
turf.truncate(feature1),
turf.truncate(feature2)
)
I'm hitting the same issue when doing union
on fairly complex polygons. Example features in the attachments.
feature1.txt
feature2.txt
Note: I've already run them through truncate
.
Edit: truncate
with precision set to 5 (or less) does the trick, which is sufficient for my needs. However, this might not be the case for everyone.
I'm also facing this issue but with difference
(version 6.5.0), already truncated to precision 6 (5 works though, but 6 is default for the turf.truncate):
turf.difference(feature-1.txt, feature-2.txt);
Uncaught Error: Unable to find segment #139 [13.630268, 52.723444] -> [13.630269, 52.723445] in SweepLine tree. Please submit a bug report.
We ran into the same issue. Although turf.truncate allows the processing to work without encountering the SweepLine error, this solution has a pretty drastic performance problem. We use union/difference to maintain our hierarchy shapes based on changes to lower shapes in the hierarchy. Making a change that used to take <3 seconds would take about 8 seconds using this approach. It is especially bad when dealing with shapes like Alaska where there are a large number of islands making up the state. Definitely not an acceptable performance hit. I'm not sure of the feasibility of changing the find segment logic to have a slight tolerance to account for the decimals issue when searching. Just a thought.