@turf/intersect Error in v6.3.0: Unable to complete output ring

[mortvif]

Hi,

After updating Turf from version 5.6.1 to 6.3.0, I am facing an error when trying to find the intersection between these two polygons using @turf/intersect (find geojson definition in https://gist.github.com/mortvif/07e100eae623d6816b53e3bc9cccf91d):

On version 5.6.1, the intersection was returned as expected:

However, on version 6.3.0, the following error appears instead:

/home/turf/node_modules/polygon-clipping/dist/polygon-clipping.cjs.js:1252
              throw new Error("Unable to complete output ring starting at [".concat(firstPt.x, ",") + " ".concat(firstPt.y, "]. Last matching segment found ends at") + " [".concat(lastPt.x, ", ").concat(lastPt.y, "]."));
              ^
Error: Unable to complete output ring starting at [-3.83455192598234, 40.409050315155]. Last matching segment found ends at [-3.8342366248332023, 40.40931614783642].
    at Function.factory (/home/turf/node_modules/polygon-clipping/dist/polygon-clipping.cjs.js:1252:21)
    at Operation.run (/home/turf/node_modules/polygon-clipping/dist/polygon-clipping.cjs.js:1776:30)
    at Object.intersection (/home/turf/node_modules/polygon-clipping/dist/polygon-clipping.cjs.js:1800:20)
    at Object.intersect (/home/turf/node_modules/@turf/intersect/dist/js/index.js:49:51)
    at Object.<anonymous> `(/home/turf/testIntersection.js:8:33)

Code to reproduce bug:

let turf = require("@turf/turf");

let pol1= {"type":"Feature","properties":{},"geometry":{"type":"Polygon","coordinates":[[[-3.83455192598234,40.409050315155],[-3.8345491088924044,40.409032816373895],[-3.8345418625081247,40.40901607230197],[-3.8345304653068033,40.40900072640372],[-3.8345153552783007,40.40898736841227],[-3.834497113093057,40.408976511666445],[-3.8344764397871756,40.408968573383575],[-3.8344541298221237,40.40896385862635],[-3.8344310405543442,40.40896254857957],[-3.8344080592879837,40.40896469358739],[-3.83438606917682,40.408970211218694],[-3.8343659152856744,40.4089788894348],[-3.834348372115476,40.40899039473786],[-3.834177858760829,40.409126560378894],[-3.83375168422429,40.409032801990904],[-3.8337284856464264,40.40902956463916],[-3.833704904835557,40.4090299015569],[-3.8336818820896954,40.40903379930932],[-3.8336603354539585,40.409041102471356],[-3.83364112411339,40.409051519825255],[-3.8336250141327364,40.409064635972896],[-3.833612647909254,40.4090799278999],[-3.8336044119232677,40.40909284706399],[-3.8335729899859303,40.40911989936291],[-3.83354357775375,40.40912687044306],[-3.8335137989493044,40.40912125718645],[-3.833480309818796,40.40909557565847],[-3.833396901450346,40.40898192854682],[-3.8333837868735388,40.408967551586315],[-3.833367263037019,40.408955381441274],[-3.8333479559674717,40.40894587919202],[-3.8333265971366535,40.40893940484228],[-3.8330251177882237,40.40887304968846],[-3.8328484611333167,40.40876426559626],[-3.832734951264248,40.40843336454013],[-3.832726932462509,40.40841682588908],[-3.832714830355114,40.40840179621679],[-3.8326991100208536,40.40838885310396],[-3.8326803755836294,40.408378493945825],[-3.8326593469962735,40.40837111683777],[-3.832636832373328,40.408367005276865],[-3.832613696936004,40.40836631726752],[-3.8325908297626894,40.40836907924944],[-3.832569109622699,40.40837518508161],[-3.8325493712061665,40.40838440012121],[-3.832532373047783,40.40839637024059],[-3.8325187683769677,40.40841063543614],[-3.832509080014675,40.40842664750565],[-3.832503680281511,40.40844379111528],[-3.8325027766893167,40.40846140744634],[-3.832506403966127,40.408478819513206],[-3.832629725743574,40.40883832755169],[-3.832630673594837,40.408840282474216],[-3.8326312267798404,40.40884232335561],[-3.832634676039257,40.40884853742842],[-3.8326377445716466,40.40885486620945],[-3.8326391750873223,40.40885664276608],[-3.8326402405435473,40.40885856225713],[-3.8326452156545074,40.40886414454316],[-3.8326498467432972,40.40886989588979],[-3.832651704949721,40.4088714258083],[-3.832653241732515,40.40887315014393],[-3.8326595515049795,40.40887788611862],[-3.8326655671804466,40.40888283900928],[-3.832667781667827,40.40888406349555],[-3.832669730719638,40.40888552641043],[-3.832895130800659,40.40902432655466],[-3.8329147852579775,40.40903413960093],[-3.8329366023975,40.409040795056804],[-3.8332143756147303,40.40910193263683],[-3.8332819982841775,40.4091940714427],[-3.8333012883881694,40.409213565255875],[-3.83336948838725,40.40926586530512],[-3.8333859436734707,40.40927637405202],[-3.8334046261255996,40.409284440127564],[-3.8334249180008944,40.40928979682342],[-3.83351881811523,40.40930749684639],[-3.8335399766319913,40.40930996368926],[-3.8335613724013182,40.40930948223858],[-3.8335823026760876,40.40930606830765],[-3.833674702782557,40.40928416827969],[-3.833694495571647,40.40927792779691],[-3.8337124823739304,40.40926906767858],[-3.833728071449941,40.40925787940999],[-3.8337678988659136,40.40922359047],[-3.8341811162739527,40.40931449813965],[-3.83418743179838,40.40931538856986],[-3.8341936207298533,40.40931669648408],[-3.834198787843836,40.40931698966665],[-3.834203882679486,40.40931770799109],[-3.8342103049943153,40.40931764315093],[-3.8342167101145117,40.40931800657809],[-3.834221853061412,40.409317526560784],[-3.834227034046546,40.40931747425317],[-3.8342333163447924,40.40931645663443],[-3.8342396915076176,40.40931586160816],[-3.834244612646042,40.40931462683783],[-3.834249680677578,40.40931380590834],[-3.8342555815332413,40.409311874617664],[-3.834261681743722,40.40931034400458],[-3.834266191956608,40.40930840193288],[-3.834270952272051,40.40930684392955],[-3.834276244917819,40.40930407318568],[-3.834281835747566,40.40930166580659],[-3.8342857617095607,40.40929909106643],[-3.834290031372107,40.40929685586274],[-3.834294512414421,40.409293352144026],[-3.834299379010279,40.409290160513585],[-3.83451932993786,40.40911451550404],[-3.834533588198565,40.40910062523229],[-3.8345440136045337,40.40908488381169],[-3.834550205515344,40.40906789617728],[-3.83455192598234,40.409050315155]]]}};
let pol2 = {"type":"Feature","properties":{},"geometry":{"type":"Polygon","coordinates":[[[-3.83455192598234,40.409050315155],[-3.8345491088924044,40.409032816373895],[-3.8345418625081247,40.40901607230197],[-3.8345304653068033,40.40900072640372],[-3.8345153552783007,40.40898736841227],[-3.834497113093057,40.408976511666445],[-3.8344764397871756,40.408968573383575],[-3.8344541298221237,40.40896385862635],[-3.8344310405543442,40.40896254857957],[-3.8344080592879837,40.40896469358739],[-3.83438606917682,40.408970211218694],[-3.8343659152856744,40.4089788894348],[-3.834348372115476,40.40899039473786],[-3.8341860126530114,40.40912004898301],[-3.8336592689516156,40.40894040968877],[-3.8336560611269483,40.408853862971455],[-3.8336531483024934,40.40883639291525],[-3.8336458201698336,40.40881969002402],[-3.833634357725855,40.40880439476212],[-3.8336192004948124,40.40879109361868],[-3.8336009296747,40.40878029661897],[-3.8335802458513806,40.40877241776803],[-3.8335579421350627,40.40876775917592],[-3.833534873749143,40.408766499473685],[-3.8335119252374934,40.40876868696387],[-3.8329991583627283,40.40885706407902],[-3.8328484611367055,40.40876426560614],[-3.832734951264248,40.40843336454013],[-3.832726932462509,40.40841682588908],[-3.832714830355114,40.40840179621679],[-3.8326991100208536,40.40838885310396],[-3.8326803755836294,40.408378493945825],[-3.8326593469962735,40.40837111683777],[-3.832636832373328,40.408367005276865],[-3.832613696936004,40.40836631726752],[-3.8325908297626894,40.40836907924944],[-3.832569109622699,40.40837518508161],[-3.8325493712061665,40.40838440012121],[-3.832532373047783,40.40839637024059],[-3.8325187683769677,40.40841063543614],[-3.832509080014675,40.40842664750565],[-3.832503680281511,40.40844379111528],[-3.8325027766893167,40.40846140744634],[-3.832506403966127,40.408478819513206],[-3.832629725743574,40.40883832755169],[-3.832630673594837,40.408840282474216],[-3.8326312267798404,40.40884232335561],[-3.832634676039257,40.40884853742842],[-3.8326377445716466,40.40885486620945],[-3.8326391750873223,40.40885664276608],[-3.8326402405435473,40.40885856225713],[-3.8326452156545074,40.40886414454316],[-3.8326498467432972,40.40886989588979],[-3.832651704949721,40.4088714258083],[-3.832653241732515,40.40887315014393],[-3.8326595515049795,40.40887788611862],[-3.8326655671804466,40.40888283900928],[-3.832667781667827,40.40888406349555],[-3.832669730719638,40.40888552641043],[-3.832895130800659,40.40902432655466],[-3.832912826549752,40.40903334387367],[-3.832932361033984,40.40903979538643],[-3.8329530993491185,40.40904347140754],[-3.8329743674638825,40.40904425245991],[-3.832995474127387,40.409042113158],[-3.8334239904054592,40.4089682573086],[-3.8334252386134966,40.40900193691386],[-3.833427914072361,40.40901859790407],[-3.833434609021053,40.40903459013415],[-3.8334450902424826,40.4090493565116],[-3.833458992623358,40.409062382646496],[-3.833475831872736,40.409073214770295],[-3.8334950213922845,40.40908147554315],[-3.8341656220460503,40.40931017582205],[-3.8341685519810556,40.4093109223674],[-3.8341713106692126,40.409311981672516],[-3.834179509631203,40.40931371436887],[-3.834187578725782,40.40931577036844],[-3.8341906436391717,40.40931606733198],[-3.8341936207298533,40.40931669648408],[-3.8342021060938283,40.40931717794449],[-3.8342105469212235,40.409317995787504],[-3.834213629029606,40.40931783175702],[-3.8342167101145117,40.40931800657809],[-3.8342251557914957,40.40931721830024],[-3.834233643974112,40.4093167665573],[-3.8342366248332436,40.40931614783642],[-3.8342396915076176,40.40931586160816],[-3.8342477729339226,40.40931383388519],[-3.834255982274187,40.40931212991664],[-3.834258747330996,40.40931108028254],[-3.834261681743722,40.40931034400458],[-3.8342690883535533,40.409307154761045],[-3.8342767033700853,40.40930426404971],[-3.834279146364692,40.40930282383937],[-3.834281835747566,40.40930166580659],[-3.8342882829085267,40.4092974376036],[-3.8342950109596026,40.40929347123841],[-3.834297038009003,40.409291695798444],[-3.834299379010279,40.409290160513585],[-3.83451932993786,40.40911451550404],[-3.834533588198565,40.40910062523229],[-3.8345440136045337,40.40908488381169],[-3.834550205515344,40.40906789617728],[-3.83455192598234,40.409050315155]]]}}

console.log(JSON.stringify(turf.intersect(pol1, pol2)))

[idoros]

I also encountered the same issue, and also found that 5.1.6 doesn't have it.

I think I have a simpler case, and also a bit different, that might be helpful:

Changing either points to match the other will resolve the error:

const poly1 = polygon([
  [
    [973.2050807568878, 709.8076211353313],
    [923.2050807568877, 623.2050807568874], /* <- change to 623.2050807568876 */
    [923.2050807568877, 623.2050807568874], 
    [973.2050807568877, 536.6025403784436],
    [973.2050807568877, 536.6025403784436],
    [1073.2050807568876, 536.6025403784436],
    [1073.2050807568876, 536.6025403784436],
    [1123.2050807568878, 623.2050807568874],
    [1123.2050807568878, 623.2050807568874],
    [1073.2050807568878, 709.8076211353313],
    [1073.2050807568878, 709.8076211353313],
    [973.2050807568878, 709.8076211353313],
  ],
]);
const poly2 = polygon([
  [
    [1009.8076211353315, 573.2050807568876],
    [923.2050807568877, 623.2050807568876], /* <- change to 623.2050807568874 */
    [923.2050807568877, 623.2050807568876],
    [873.2050807568877, 536.6025403784438],
    [873.2050807568877, 536.6025403784438],
    [959.8076211353315, 486.60254037844373],
    [959.8076211353315, 486.60254037844373],
    [1009.8076211353315, 573.2050807568876],
  ],
]);
var intersection = intersect(poly1, poly2);

[padawanDeveloper]

const poly1 = {
type: 'Feature',
properties: {},
geometry: {
type: 'Polygon',
coordinates: [
[
[-37.03835344778681, -72.77586791664363],
[-37.022606172184794, -72.77586791664363],
[-37.022606172184794, -72.75551162660123],
[-37.03835344778681, -72.75551162660123],
[-37.03835344778681, -72.77586791664363]
]
]
}
};

const poly2 = {
type: 'Feature',
properties: {},
geometry: {
type: 'Polygon',
coordinates: [
[
[-37.04968884926708, -66.7482388650978],
[-37.04990168905576, -66.75947610848424],
[-37.03188742710995, -66.76000562559427],
[-37.03167472559009, -66.74877103252062],
[-37.04968884926708, -66.7482388650978]
]
]
}
};

console.log(turf.intersect(poly1, poly2)) // return null

i have same problem!!

[EmilyRagan]

I am having a similar issue with the difference function (same error thrown, difference between polygon and Multipolygon contained within it)

[mh4620]

change feature coordinates with transformRotate or buffer , use function and return result to orginal coordinates

[thisismhp]

finally i found solution! just fix coordinates to 8~10 decimals

[eric-g-97477]

finally i found solution! just fix coordinates to 8~10 decimals

@thisismhp how did you do that? What exactly did you do?

[markstos]

This seems like it could be closed as a dupe of #2277 (although that ticket is actually newer).

The fix proposed there is for Turf.js to replace polygon-clipping library with the polyclip-ts library, which resolves many issues.

You could try bypassing Turf.js for now and calling polyclip-ts directly.

[pelord]

Any updates?

[jcapogna]

I recently ran into the problem as well. I followed the advice to fix the coordinates to 8 decimals of precision.

Here is some code:

// truncates all of the coordinates of a feature to 8 digits
const truncateCoordinatesOfFeature = (feature: Feature<Polygon, any>): Feature<Polygon, any> => {
    // Clone the feature
    const truncatedFeature = turf.clone(feature) as Feature<Polygon, any>

    // Truncate coordinates of each geometry in the feature
    turf.coordEach(truncatedFeature, coord => {
        coord[0] = Number(coord[0].toFixed(8));
        coord[1] = Number(coord[1].toFixed(8));
    });

    return truncatedFeature;
}

// truncates a number to a certain precision
export const toFixed = (num: number, precision = 8): number => {
    return Math.trunc(num * Math.pow(10, precision)) / Math.pow(10, precision);
}

[markstos]

@pelord @jcapogna the open source team is short-staffed but seems open to the proposed fix to replace polygon-clipping library with the polyclip-ts. Right now, a volunteer to complete that would be welcome, or some dev could be hired to do it.

A workaround is to structure your code such that polyclip-ts is used directly, bypassing the part of Turf that would call the polygon-clipping library.

[markstos]

There's been some discussion recently about reviving the effort to get this fixed in Turf: luizbarboza/polyclip-ts#7