search

Turfjs / turf

A modular geospatial engine written in JavaScript and TypeScript
https://turfjs.org/
MIT License
9.35k stars 941 forks source link

Error thrown when using @turf/union #1983

Open qihua opened 3 years ago

qihua commented 3 years ago

@turf/turf 6.2.0-alpha2


var a=turf.polygon([[[-138.73721748279914,2.0783782250758946],[-141.54971748279917,6.2849421612509815],[-134.07528251720086,11.208361735012105],[-131.26278251720083,7.043979226170151],[-138.73721748279914,2.0783782250758946]]])

var b = turf.polygon([[[-160.6896965377851,40.88860081193033],[-160.6583451950261,40.510672000926164],[-160.66190372037752,40.51037133348589],[-160.55753360319002,39.79663191716156],[-160.55397491337683,39.796935800275115],[-160.5499089989524,39.74740308604976],[-160.44421528791327,39.320082232246875],[-160.2699121404418,38.90384497183405],[-160.10443662874945,38.629423306699906],[-160.11113808103656,38.62686332599969],[-158.70488808103653,36.396208817797614],[-158.69818219705635,36.398850979301976],[-158.62349842129717,36.2712317120243],[-158.32126165579726,35.88632497556583],[-157.9617182982814,35.53342756235644],[-157.85881540923663,35.454636702811],[-157.86352414522221,35.45092643468119],[-156.4572741452222,34.29726262080686],[-156.4572741452222,34.29726262080683],[-153.6447741452222,31.94201233811576],[-153.64006527501178,31.945887812934107],[-153.64006527501172,31.94588781293406],[-153.64477414522213,31.942012338115703],[-152.7580924416708,31.184737367454044],[-151.6736380810366,29.316714166213814],[-151.66691734698864,29.319592686835602],[-151.5922484212972,29.18135443047673],[-151.2900116557973,28.764710578780907],[-150.93046829828143,28.383033827238847],[-150.82756518327554,28.297881796676013],[-150.83227414522221,28.293848637631797],[-148.54231573224416,26.254481087538338],[-146.04863808103656,21.710149065891883],[-146.04190027704684,21.71323661891839],[-145.9672484212972,21.565942101783975],[-145.66501165579726,21.12236003249639],[-145.3054682982814,20.716395937851374],[-145.20256517950813,20.62590423782137],[-145.20727414522216,20.62158943658075],[-141.64443015181178,17.246138281182418],[-139.77228869117522,12.721283006524027],[-140.21920699785207,12.48151816830945],[-140.6755385622785,12.157608896072702],[-141.08671829828143,11.779880155476036],[-141.44626165579726,11.354094542168014],[-141.74849842129723,10.886789091976254],[-141.9886621404418,10.385185343533806],[-142.16296528791327,9.85708541123391],[-142.2686589989524,9.310754969389762],[-142.30407642059762,8.754794702435646],[-142.2686589989524,8.198002417459364],[-142.16296528791327,7.649228576493812],[-141.9886621404418,7.117228426861487],[-141.74849842129723,6.610514144945441],[-141.44626165579726,6.137210441272217],[-141.08671829828143,5.704916907523355],[-140.6755385622785,5.320580048136904],[-140.21920699785207,4.990377478814594],[-139.72492022637246,4.719616250957969],[-139.4877534841437,4.626019936874601],[-139.4915764205976,4.565473550710294],[-139.45615899895233,4.004105450791968],[-139.35046528791327,3.451213987601406],[-139.17616214044176,2.9155938231043734],[-138.93599842129717,2.4057718307890354],[-138.7307903740528,2.0826480404896484],[-138.73721748279917,2.078378225075909],[-135.92471748279917,-2.139418494751368],[-135.91828230639197,-2.1351298091717252],[-135.82126165579726,-2.287911612394268],[-135.46171829828143,-2.722108514777048],[-135.35881716745445,-2.818613899829967],[-135.36352414522216,-2.8233183805339905],[-131.66025962391583,-6.512074033718909],[-130.57988808103653,-8.655273541009365],[-130.57307698563218,-8.65189168023775],[-130.49849842129717,-8.808614737044621],[-130.19626165579723,-9.278941809131354],[-129.8367182982814,-9.707601974613453],[-129.42553856227846,-10.087977628647835],[-128.96920699785207,-10.414229095773521],[-128.4749202263724,-10.681373630031246],[-127.95047344549843,-10.885350042822523],[-127.4041374942538,-11.023069333499564],[-126.84452841695492,-11.09245189439632],[-126.56249999999999,-11.09245189439632],[-126.56249999999999,-11.10114928472835],[-125.15624999999999,-11.10114928472835],[-125.15624999999999,-11.09245189439632],[-124.87422158304506,-11.09245189439632],[-124.31461250574617,-11.023069333499564],[-123.76827655450154,-10.885350042822523],[-123.24382977362757,-10.681373630031246],[-122.74954300214795,-10.414229095773521],[-122.29321143772151,-10.087977628647835],[-121.88203170171857,-9.707601974613468],[-121.52248834420274,-9.278941809131354],[-121.22025157870283,-8.808614737044621],[-120.98008785955822,-8.303922905899086],[-120.80578471208672,-7.772745720890754],[-120.70009100104764,-7.223419751437234],[-120.66467357940238,-6.6646075621725345],[-120.66467357940238,-5.266007882805482],[-120.70009100104764,-4.705196218483266],[-120.80578471208672,-4.152787095858088],[-120.98008785955822,-3.6175719807714444],[-121.2202515787028,-3.108078602871174],[-121.52248834420274,-2.63242849864686],[-121.88203170171857,-2.198202391381244],[-121.9849335215584,-2.1016305086610645],[-121.98022585477779,-2.096945069926207],[-123.3864758547778,-0.691146592624932],[-123.39118333960779,-0.6958409934070753],[-123.39118333960789,-0.6958409934069764],[-123.38647585477788,-0.6911465926248184],[-123.50766945008958,-0.5699560417625025],[-123.51259100104767,-0.49173766653407824],[-123.61828471208676,0.06232212094137424],[-123.71595348826418,0.36290960538168665],[-123.70766646786156,0.3656711949315081],[-125.11391646786154,4.579539815662798],[-125.12221533513642,4.576778020412499],[-125.19883785955825,4.81185565150021],[-125.36441457809373,5.162348372750518],[-125.35761191896344,5.165743831278121],[-126.76386191896341,7.959530796303497],[-126.7706713392258,7.95614520389963],[-126.84525157870281,8.113146620363906],[-127.05047956609502,8.433106178826797],[-127.04403251720086,8.437379616632285],[-129.70078671927314,12.354727326722355],[-130.90361628448954,14.693864989481934],[-133.6359250839431,21.19092402842235],[-133.63633785955824,21.19211050070126],[-133.63685064122322,21.193124877862967],[-133.6421759881453,21.205787829196495],[-133.64307983026706,21.205447368180977],[-133.8765015787028,21.667198844155763],[-134.17873834420274,22.109115131915928],[-134.5382817017186,22.51119320766078],[-134.64117871395456,22.600341802546218],[-134.63647585477784,22.604769237348435],[-138.3458118725443,25.97860069463627],[-140.8263619189634,30.36183966418845],[-140.83322212303318,30.35882881270289],[-140.9077515787028,30.495610093036802],[-141.20998834420274,30.905110807080362],[-141.56953170171857,31.277289181267648],[-141.67242637169784,31.35972599692654],[-141.6677258547778,31.36385129809915],[-143.96601717531868,33.30090148459311],[-145.0451119189634,35.091469225371696],[-145.05198163997304,35.08860290822834],[-145.12650157870283,35.218310913523766],[-145.42873834420274,35.60645353663534],[-145.78828170171857,35.959028058764005],[-145.89117505429087,36.03708360338239],[-145.88647585477787,36.041004510381356],[-147.29272585477787,37.169848760576585],[-147.29272585477787,37.16984876057657],[-150.1052258547778,39.37752590372085],[-150.1052258547778,39.37752590372084],[-151.00153308598706,40.06494873317625],[-151.71763492940048,41.15175148455148],[-151.73433651399748,41.264680637113344],[-151.7379176861147,41.26437805619925],[-151.74196111823514,41.312807656725454],[-151.84765482927423,41.7276464729546],[-152.02195797674574,42.12676009771624],[-152.26212169589033,42.504153999354656],[-152.56435846139027,42.854271974661685],[-152.9239018189061,43.172058758712296],[-153.33508155490907,43.45301018304946],[-153.79141311933543,43.69321200722706],[-154.28569989081507,43.889368886946215],[-154.81014667168907,44.0388251177572],[-155.3564826229337,44.139578807949164],[-155.91609170023258,44.19029100023394],[-156.48014853414242,44.19029100023394],[-157.0397576114413,44.139578807949164],[-157.58609356268596,44.0388251177572],[-158.11054034355993,43.889368886946215],[-158.60482711503957,43.69321200722706],[-159.06115867946593,43.45301018304946],[-159.47233841546893,43.172058758712296],[-159.83188177298476,42.854271974661685],[-160.13411853848467,42.504153999354656],[-160.37428225762926,42.12676009771624],[-160.54858540510077,41.7276464729546],[-160.65427911613986,41.312807656725454],[-160.6896965377851,40.88860081193033]]])

turf.union(a,b)

Uncaught Error: Unable to complete output ring starting at [-160.6896965377851, 40.88860081193033]. Last matching segment found ends at [-134.07528251720086, 11.208361735012105].

I found that if you delete [-138.73721748279917,2.078378225075909] in b, it’s ok, so strange.Is it because [-138.73721748279917,2.078378225075909] and [-138.73721748279914,2.0783782250758946] are about the same value?

markstos commented 3 years ago

The heavy lifting for this is done by the polygon-clipping library, which already has open bug reports about this as well. In this bug report against polygon-clipping, I found a solution which solved the problem for me.

The solution is to truncate the coordinates involved as apparently the bug is triggered by floating point number calculations.

Turf.js includes a truncate method for this purpose. It has a good default value of 6 digits beyond the decimal, which is likely all you need anyway-- that's about a precision down to a meter. Is your underlying data actually more accurate than that?

https://stackoverflow.com/a/1947615/254318

Until a better fix is developed, the docs for turf.union could be updated to recommend using truncate if there's a problem.

https://github.com/mfogel/polygon-clipping/issues/83