Unable to find segment #244139 [-71.66191017921575, 19.182076213197277] -> [-71.65740874033601, 19.204588002723632] in SweepLine tree

[mkorpela]

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."

• 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);
    });

[stebogit]

@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]]]]}}

[mkorpela]

Thanks for the tip about the truncate! This bug case from internals of a fairly complex algorithmic manipulation.

[btisdall]

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)

[stebogit]

@btisdall have you tried truncating the features?

turf.difference(
  turf.truncate(feature1),
  turf.truncate(feature2)
)

[YaroslavKormushyn]

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.

[pomm0]

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):

feature-1.txt
feature-2.txt

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.

[aldensc]

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.