polygon-clipping
polygon-clipping copied to clipboard
Published
20 hours ago •
mfogel
mfogel
Regression 0.14.3 vs 0.14.2
The following arguments where working on v0.14.2:
{
"type": "FeatureCollection",
"features": [
{
"type": "Feature",
"properties": {},
"geometry": {
"coordinates": [
[
[
[-94.5106109975048, 42.82347141213997],
[-94.51060749700446, 42.823919887550915],
[-94.51060749700446, 42.823919887550815],
[-94.5106109975048, 42.82347141213997]
]
],
[
[
[-94.51060749700446, 42.823919887550915],
[-94.5105786, 42.8276221],
[-94.51050466783008, 42.827621183697666],
[-94.51057433951064, 42.82761817796059],
[-94.5106000883243, 42.82470359749422],
[-94.51059420431768, 42.82470309713836],
[-94.51060749700446, 42.823919887550915]
]
],
[
[
[-94.5104674326479, 42.82469231690777],
[-94.51000785709768, 42.82465323616983],
[-94.50986420581197, 42.82482444412345],
[-94.51000463956008, 42.82464969511515],
[-94.5104674326479, 42.82469231690777]
]
],
[
[
[-94.5096972239665, 42.82518176830861],
[-94.509664683104, 42.82536375137847],
[-94.50966238975526, 42.82535986208039],
[-94.5096972239665, 42.82518176830861]
]
],
[
[
[-94.51039356432732, 42.82660379766182],
[-94.51039409519582, 42.8266047000388],
[-94.51037963140404, 42.826683198601366],
[-94.51039356432732, 42.82660379766182]
]
],
[
[
[-94.51030975336975, 42.82706244391441],
[-94.51030826450734, 42.82707052433769],
[-94.51022155488808, 42.82722692929472],
[-94.51030975336975, 42.82706244391441]
]
],
[
[
[-94.50599033472126, 42.82306101847848],
[-94.5060286, 42.8230107],
[-94.5062582, 42.8228704],
[-94.506210410281, 42.82289960251558],
[-94.50599033472126, 42.82306101847848]
]
],
[
[
[-94.5062582, 42.8228704],
[-94.5062568, 42.8228133],
[-94.50626572361868, 42.82279357729024],
[-94.50625701412238, 42.82282203313413],
[-94.5062582, 42.8228704]
]
],
[
[
[-94.506445, 42.8214863],
[-94.5062279, 42.8219445],
[-94.5061381, 42.8220829],
[-94.5057891, 42.8222918],
[-94.5053543, 42.8224363],
[-94.5047239, 42.8227076],
[-94.5045431, 42.8229387],
[-94.5044911, 42.8232374],
[-94.5044726, 42.8237056],
[-94.5044882, 42.8238773],
[-94.5043667, 42.8239932],
[-94.5020064, 42.8240356],
[-94.502002, 42.8236675],
[-94.5020592, 42.8235692],
[-94.5022148, 42.8234957],
[-94.5034194, 42.8235021],
[-94.5034565, 42.8234805],
[-94.5034514, 42.8234598],
[-94.5034278, 42.8234479],
[-94.5021898, 42.8234354],
[-94.5020628, 42.8233882],
[-94.5020092, 42.8233042],
[-94.5019831, 42.8204504],
[-94.5056357, 42.8204892],
[-94.5061462, 42.8206348],
[-94.5064006, 42.8208873],
[-94.5063976, 42.8211725],
[-94.506445, 42.8214863]
],
[
[-94.5038663, 42.8228955],
[-94.5038667, 42.8229164],
[-94.5038873, 42.822931],
[-94.5039324, 42.8229204],
[-94.5041951, 42.8224342],
[-94.5045205, 42.822234],
[-94.5045337, 42.8222154],
[-94.5045251, 42.8221954],
[-94.5044724, 42.822192],
[-94.5041325, 42.8224028],
[-94.5038663, 42.8228955]
]
],
[
[
[-94.5105765, 42.8211688],
[-94.5101845, 42.8209762],
[-94.5101935, 42.8205644],
[-94.5117041, 42.8205628],
[-94.5117017, 42.820746],
[-94.5115431, 42.8207422],
[-94.5114553, 42.8209655],
[-94.5113586, 42.8210169],
[-94.5112621, 42.8211302],
[-94.5110099, 42.8212396],
[-94.5107632, 42.8212286],
[-94.5105765, 42.8211688]
]
],
[
[
[-94.5071340389188, 42.82206524426755],
[-94.5071038, 42.8221846],
[-94.5068975420672, 42.82243555854111],
[-94.5068975420672, 42.82243555854111],
[-94.50689732547356, 42.82243582207531],
[-94.5068958430136, 42.82243552814658],
[-94.50664329502617, 42.82243101029189],
[-94.50640512186716, 42.822537765735504],
[-94.50674977554031, 42.82207723785174],
[-94.50674977554031, 42.82207723785172],
[-94.5067516, 42.8220748],
[-94.5068373, 42.8217649],
[-94.5068348477478, 42.82177376759573],
[-94.5068351035125, 42.82177855129397],
[-94.50683856005529, 42.821766451828395],
[-94.50683817933611, 42.8218360800014],
[-94.50684070456192, 42.82188331059465],
[-94.50684070456192, 42.82205958246773],
[-94.50712605874644, 42.82206509023808],
[-94.50712609264885, 42.82206509074553],
[-94.50713519951417, 42.82206066329333],
[-94.5071340389188, 42.82206524426755]
]
],
[
[
[-94.503091, 42.8275293],
[-94.5028281, 42.8274167],
[-94.5025245, 42.826947],
[-94.5019451, 42.8263206],
[-94.501929, 42.8249066],
[-94.5038992, 42.8249003],
[-94.5040494, 42.8249882],
[-94.5041531, 42.825097],
[-94.5047602, 42.8271982],
[-94.5048042, 42.8272196],
[-94.5048342, 42.8271927],
[-94.5042872, 42.8252395],
[-94.5043935, 42.8250601],
[-94.5047023, 42.8250181],
[-94.5051638, 42.824909],
[-94.505476, 42.8249389],
[-94.5058815, 42.8250939],
[-94.50589656811924, 42.82488722434553],
[-94.50589656829834, 42.82511278005304],
[-94.50595320742175, 42.82514576840401],
[-94.50618948046608, 42.82528201126543],
[-94.50651867961092, 42.82505942913988],
[-94.5067381494552, 42.824910826851536],
[-94.50674333408618, 42.82490483172827],
[-94.5067752, 42.8233668],
[-94.50674330113368, 42.8249064222051],
[-94.5067323, 42.8254374],
[-94.5068726, 42.8254585],
[-94.50683520557293, 42.82479859834568],
[-94.50683519204098, 42.82479835954684],
[-94.50683614616538, 42.82479723750743],
[-94.50741684433524, 42.82412404841416],
[-94.50742191965443, 42.82411835469384],
[-94.5074308, 42.8234954],
[-94.507623329065, 42.82326831973579],
[-94.50760463782451, 42.82311751942089],
[-94.5075906458826, 42.823086966149155],
[-94.50741684182584, 42.822710326102786],
[-94.50738475690213, 42.822689486775936],
[-94.5076513, 42.8223375],
[-94.5075872, 42.8222582],
[-94.5069848, 42.8230439],
[-94.50729964074937, 42.8226332586043],
[-94.50729915718496, 42.82263388930903],
[-94.50713826548152, 42.82252938930068],
[-94.50703544126792, 42.822463206423926],
[-94.50703392417978, 42.82246290562943],
[-94.5068215, 42.8227144],
[-94.5071537, 42.8223211],
[-94.5072696, 42.8219765],
[-94.50726203199233, 42.82199900160008],
[-94.50726610423771, 42.821997021811065],
[-94.50757700540208, 42.821785104246096],
[-94.50767973446088, 42.82171477880564],
[-94.5077018313072, 42.82150077187951],
[-94.50771617732244, 42.82134819705607],
[-94.50746950092294, 42.82113107909275],
[-94.5074176489652, 42.82108614730528],
[-94.5070445709974, 42.821085179677205],
[-94.50698258149605, 42.82112577605148],
[-94.50693485150624, 42.8211605129468],
[-94.5068441223038, 42.82121645174767],
[-94.50682429074966, 42.82122943925646],
[-94.5068223, 42.8211475],
[-94.50682840952796, 42.821103313919],
[-94.5068619, 42.8208611],
[-94.50702132353818, 42.82075818405077],
[-94.5070608, 42.8207327],
[-94.50708357165298, 42.820732395475666],
[-94.5072627, 42.82073],
[-94.5076212, 42.8207825],
[-94.5080295, 42.8209601],
[-94.5084098, 42.8212639],
[-94.5088785, 42.8213721],
[-94.5092981, 42.821378],
[-94.5095524, 42.8212946],
[-94.510249, 42.8211939],
[-94.5103586, 42.8212267],
[-94.5104706, 42.8212],
[-94.5107432, 42.8213093],
[-94.5110324, 42.8213186],
[-94.5113452, 42.821196],
[-94.5114499, 42.8210596],
[-94.5115669, 42.8209389],
[-94.5116955, 42.8209083],
[-94.5116558, 42.8212978],
[-94.5116065, 42.8215308],
[-94.5112084, 42.8217369],
[-94.5106237, 42.821844],
[-94.5106109975048, 42.82347141213997],
[-94.51010012613554, 42.82348390192665],
[-94.50925040218866, 42.82427710038179],
[-94.50919032096864, 42.82503251741424],
[-94.50939631475195, 42.825542418999035],
[-94.50946497890985, 42.82654332426689],
[-94.5091518140463, 42.82681434570487],
[-94.5058651, 42.8267693],
[-94.5058385, 42.826777],
[-94.505827, 42.8267962],
[-94.5058564, 42.8268235],
[-94.50908949400126, 42.8268682791763],
[-94.50903582546744, 42.8269147253933],
[-94.50869250271354, 42.82699026436085],
[-94.50827729728192, 42.82759063808],
[-94.5100073179855, 42.82761336523842],
[-94.51000640706286, 42.82761500834118],
[-94.503091, 42.8275293]
],
[
[-94.5074308, 42.8234954],
[-94.50741917012569, 42.82431123365672],
[-94.50741821909584, 42.82437794823468],
[-94.5074021, 42.8255087],
[-94.5075111, 42.8255187],
[-94.5074936, 42.8247984],
[-94.5075207, 42.8246379],
[-94.5076109, 42.8245109],
[-94.507544, 42.8243174],
[-94.5075228495647, 42.82400345776551],
[-94.50769042916365, 42.823809681129454],
[-94.50763697205564, 42.82337839093631],
[-94.5075848, 42.8234362],
[-94.50763842829394, 42.82337677735654],
[-94.50763842829394, 42.823376777356536],
[-94.50798187173812, 42.82299622604992],
[-94.5080235, 42.8229501],
[-94.5079897, 42.8228362],
[-94.5074308, 42.8234954]
],
[
[-94.5046756, 42.8252678],
[-94.5050751, 42.8266425],
[-94.5051122, 42.8266641],
[-94.5051384, 42.8266558],
[-94.5051489, 42.8266363],
[-94.504696, 42.8251639],
[-94.5046756, 42.8252678]
],
[
[-94.5094049, 42.8261515],
[-94.5070906, 42.8261189],
[-94.5060963, 42.8261205],
[-94.5060977, 42.8261777],
[-94.5094103, 42.8262097],
[-94.5094049, 42.8261515]
],
[
[-94.5081516, 42.8252097],
[-94.5081624, 42.8252291],
[-94.5081887, 42.8252372],
[-94.5082152, 42.8252293],
[-94.5082263, 42.82521],
[-94.5082371, 42.8239038],
[-94.5082263, 42.8238843],
[-94.5081999, 42.8238762],
[-94.5081734, 42.8238841],
[-94.5081623, 42.8239034],
[-94.5081516, 42.8252097]
],
[
[-94.5087689, 42.8218722],
[-94.5087428, 42.8218808],
[-94.5087328, 42.8219005],
[-94.508764, 42.8219266],
[-94.509427, 42.8219112],
[-94.5103516, 42.8217293],
[-94.5103792, 42.821701],
[-94.5103008, 42.8216756],
[-94.509419, 42.8218566],
[-94.5087689, 42.8218722]
]
]
],
"type": "MultiPolygon"
}
},
{
"type": "Feature",
"properties": {
"stroke": "#555555",
"stroke-width": 2,
"stroke-opacity": 1,
"fill": "#555555",
"fill-opacity": 0.5
},
"geometry": {
"coordinates": [
[
[
[-94.503091, 42.8275293],
[-94.5028281, 42.8274167],
[-94.5025245, 42.826947],
[-94.5019451, 42.8263206],
[-94.501929, 42.8249066],
[-94.5038992, 42.8249003],
[-94.5040494, 42.8249882],
[-94.5041531, 42.825097],
[-94.5047602, 42.8271982],
[-94.5048042, 42.8272196],
[-94.5048342, 42.8271927],
[-94.5042872, 42.8252395],
[-94.5043935, 42.8250601],
[-94.5047023, 42.8250181],
[-94.5051638, 42.824909],
[-94.505476, 42.8249389],
[-94.5058815, 42.8250939],
[-94.50589656811924, 42.82488722434553],
[-94.50589656829834, 42.82511278005304],
[-94.50618839211528, 42.82528274713438],
[-94.50673770865252, 42.824911336563105],
[-94.50674333408618, 42.82490483172827],
[-94.5067752, 42.8233668],
[-94.5067323, 42.8254374],
[-94.5068726, 42.8254585],
[-94.50683520557293, 42.82479859834568],
[-94.5074218934064, 42.82412019598943],
[-94.5074308, 42.8234954],
[-94.507623329065, 42.82326831973579],
[-94.50760459847515, 42.823117201951575],
[-94.50741577122244, 42.82270800606425],
[-94.5073854915987, 42.82268851656332],
[-94.5076513, 42.8223375],
[-94.5075872, 42.8222582],
[-94.5069848, 42.8230439],
[-94.50729964074937, 42.8226332586043],
[-94.50703429389372, 42.82246246791572],
[-94.5068215, 42.8227144],
[-94.5071537, 42.8223211],
[-94.5072696, 42.8219765],
[-94.5072612784434, 42.82200124209154],
[-94.50768184491608, 42.82171333404703],
[-94.50771617732244, 42.82134819705607],
[-94.50741576991278, 42.821083786496],
[-94.50704669834522, 42.821083786496],
[-94.50682429074966, 42.82122943925646],
[-94.5068223, 42.8211475],
[-94.5068619, 42.8208611],
[-94.5070608, 42.8207327],
[-94.5072627, 42.82073],
[-94.5076212, 42.8207825],
[-94.5080295, 42.8209601],
[-94.5084098, 42.8212639],
[-94.5088785, 42.8213721],
[-94.5092981, 42.821378],
[-94.5095524, 42.8212946],
[-94.510249, 42.8211939],
[-94.5103586, 42.8212267],
[-94.5104706, 42.8212],
[-94.5107432, 42.8213093],
[-94.5110324, 42.8213186],
[-94.5113452, 42.821196],
[-94.5114499, 42.8210596],
[-94.5115669, 42.8209389],
[-94.5116955, 42.8209083],
[-94.5116558, 42.8212978],
[-94.5116065, 42.8215308],
[-94.5112084, 42.8217369],
[-94.5106237, 42.821844],
[-94.5106109975048, 42.82347141213997],
[-94.51010012613554, 42.82348390192665],
[-94.50925040218866, 42.82427710038179],
[-94.50919032096864, 42.82503251741424],
[-94.50939631475195, 42.825542418999035],
[-94.50946497890985, 42.82654332426689],
[-94.5091518140463, 42.82681434570487],
[-94.5058651, 42.8267693],
[-94.5058385, 42.826777],
[-94.505827, 42.8267962],
[-94.5058564, 42.8268235],
[-94.50908949400126, 42.8268682791763],
[-94.50903582546744, 42.8269147253933],
[-94.50869250271354, 42.82699026436085],
[-94.50827729728192, 42.82759063808],
[-94.5100073179855, 42.82761336523842],
[-94.51000640706286, 42.82761500834118],
[-94.503091, 42.8275293]
],
[
[-94.5074308, 42.8234954],
[-94.5074021, 42.8255087],
[-94.5075111, 42.8255187],
[-94.5074936, 42.8247984],
[-94.5075207, 42.8246379],
[-94.5076109, 42.8245109],
[-94.507544, 42.8243174],
[-94.5075228495647, 42.82400345776551],
[-94.50769042916365, 42.823809681129454],
[-94.50763697205564, 42.82337839093631],
[-94.5075848, 42.8234362],
[-94.5080235, 42.8229501],
[-94.5079897, 42.8228362],
[-94.5074308, 42.8234954]
],
[
[-94.5046756, 42.8252678],
[-94.5050751, 42.8266425],
[-94.5051122, 42.8266641],
[-94.5051384, 42.8266558],
[-94.5051489, 42.8266363],
[-94.504696, 42.8251639],
[-94.5046756, 42.8252678]
],
[
[-94.5094049, 42.8261515],
[-94.5070906, 42.8261189],
[-94.5060963, 42.8261205],
[-94.5060977, 42.8261777],
[-94.5094103, 42.8262097],
[-94.5094049, 42.8261515]
],
[
[-94.5081516, 42.8252097],
[-94.5081624, 42.8252291],
[-94.5081887, 42.8252372],
[-94.5082152, 42.8252293],
[-94.5082263, 42.82521],
[-94.5082371, 42.8239038],
[-94.5082263, 42.8238843],
[-94.5081999, 42.8238762],
[-94.5081734, 42.8238841],
[-94.5081623, 42.8239034],
[-94.5081516, 42.8252097]
],
[
[-94.5087689, 42.8218722],
[-94.5087428, 42.8218808],
[-94.5087328, 42.8219005],
[-94.508764, 42.8219266],
[-94.509427, 42.8219112],
[-94.5103516, 42.8217293],
[-94.5103792, 42.821701],
[-94.5103008, 42.8216756],
[-94.509419, 42.8218566],
[-94.5087689, 42.8218722]
]
],
[
[
[-94.5106109975048, 42.82347141213997],
[-94.51060749700446, 42.823919887550915],
[-94.51060749700446, 42.823919887550815],
[-94.5106109975048, 42.82347141213997]
]
],
[
[
[-94.51060749700446, 42.823919887550915],
[-94.5105786, 42.8276221],
[-94.51050466783008, 42.827621183697666],
[-94.51057433951064, 42.82761817796059],
[-94.5106000883243, 42.82470359749422],
[-94.51059420431768, 42.82470309713836],
[-94.51060749700446, 42.823919887550915]
]
],
[
[
[-94.5104674326479, 42.82469231690777],
[-94.51000785709768, 42.82465323616983],
[-94.50986420581197, 42.82482444412345],
[-94.51000463956008, 42.82464969511515],
[-94.5104674326479, 42.82469231690777]
]
],
[
[
[-94.5096972239665, 42.82518176830861],
[-94.509664683104, 42.82536375137847],
[-94.50966238975526, 42.82535986208039],
[-94.5096972239665, 42.82518176830861]
]
],
[
[
[-94.51039356432732, 42.82660379766182],
[-94.51039409519582, 42.8266047000388],
[-94.51037963140404, 42.826683198601366],
[-94.51039356432732, 42.82660379766182]
]
],
[
[
[-94.51030975336975, 42.82706244391441],
[-94.51030826450734, 42.82707052433769],
[-94.51022155488808, 42.82722692929472],
[-94.51030975336975, 42.82706244391441]
]
],
[
[
[-94.5071340389188, 42.82206524426755],
[-94.5071038, 42.8221846],
[-94.5068975420672, 42.82243555854111],
[-94.50664329502617, 42.82243101029189],
[-94.50640512186716, 42.822537765735504],
[-94.5067516, 42.8220748],
[-94.5068373, 42.8217649],
[-94.5068348477478, 42.82177376759573],
[-94.50684070456192, 42.82188331059465],
[-94.50684070456192, 42.82205958246773],
[-94.5071340389188, 42.82206524426755]
]
],
[
[
[-94.50599033472126, 42.82306101847848],
[-94.5060286, 42.8230107],
[-94.5062582, 42.8228704],
[-94.506210410281, 42.82289960251558],
[-94.50599033472126, 42.82306101847848]
]
],
[
[
[-94.5062582, 42.8228704],
[-94.5062568, 42.8228133],
[-94.50626572361868, 42.82279357729024],
[-94.50625701412238, 42.82282203313413],
[-94.5062582, 42.8228704]
]
],
[
[
[-94.506445, 42.8214863],
[-94.5062279, 42.8219445],
[-94.5061381, 42.8220829],
[-94.5057891, 42.8222918],
[-94.5053543, 42.8224363],
[-94.5047239, 42.8227076],
[-94.5045431, 42.8229387],
[-94.5044911, 42.8232374],
[-94.5044726, 42.8237056],
[-94.5044882, 42.8238773],
[-94.5043667, 42.8239932],
[-94.5020064, 42.8240356],
[-94.502002, 42.8236675],
[-94.5020592, 42.8235692],
[-94.5022148, 42.8234957],
[-94.5034194, 42.8235021],
[-94.5034565, 42.8234805],
[-94.5034514, 42.8234598],
[-94.5034278, 42.8234479],
[-94.5021898, 42.8234354],
[-94.5020628, 42.8233882],
[-94.5020092, 42.8233042],
[-94.5019831, 42.8204504],
[-94.5056357, 42.8204892],
[-94.5061462, 42.8206348],
[-94.5064006, 42.8208873],
[-94.5063976, 42.8211725],
[-94.506445, 42.8214863]
],
[
[-94.5038663, 42.8228955],
[-94.5038667, 42.8229164],
[-94.5038873, 42.822931],
[-94.5039324, 42.8229204],
[-94.5041951, 42.8224342],
[-94.5045205, 42.822234],
[-94.5045337, 42.8222154],
[-94.5045251, 42.8221954],
[-94.5044724, 42.822192],
[-94.5041325, 42.8224028],
[-94.5038663, 42.8228955]
]
],
[
[
[-94.5105765, 42.8211688],
[-94.5101845, 42.8209762],
[-94.5101935, 42.8205644],
[-94.5117041, 42.8205628],
[-94.5117017, 42.820746],
[-94.5115431, 42.8207422],
[-94.5114553, 42.8209655],
[-94.5113586, 42.8210169],
[-94.5112621, 42.8211302],
[-94.5110099, 42.8212396],
[-94.5107632, 42.8212286],
[-94.5105765, 42.8211688]
]
]
],
"type": "MultiPolygon"
}
}
]
}
on v 0.14.3 I get the following error:
polygon-clipping.umd.js:2497 Uncaught Error: Unable to pop() left SweepEvent [-94.5074308, 42.8234954] from segment #278 [-94.5074308, 42.8234954] -> [-94.5074218934064, 42.82412019598943] from queue. Please file a bug report.
It is important to notice than when the coordinates are rounded to 7 digits the operation works again, this is the second time we find an issue that is solved by rounding the inputs to a reasonable number of decimals, I wonder if enforcing this in the library would solve many cases like this in the future, here's an interesting take on decimals vs accuracy and something else.
For now we will be rounding on our end before giving the arguments to the library, but I do think that there is an overkill precision that can be avoided here, after all:
The ninth decimal place is worth up to 110 microns: we are getting into the range of microscopy. For almost any conceivable application with earth positions, this is overkill and will be more precise than the accuracy of any surveying device.
I'm seeing the same error on similarly "high precision" values. I've wrapped all this to work with turfjs. Inside each function I'm rounding all coordinates to 7 decimal places and it fixes the errors:
function round(x, precision) {
const shift = Math.pow(10, precision);
return Math.round(x * shift) / shift;
}
function roundCoordinates(geometry, precision) {
if (typeof geometry === "number") {
return round(geometry, precision);
}
return geometry.map(x => roundCoordinates(x, precision));
}
I see a similar issue with "high-precision" floats, but with error Unable to find segment #7086 [1250.457315361585, 216.27426718577993] -> [1292.2812684624473, 162.8691871590578] in SweepLine tree. Rounding to a smaller number of decimal places makes the problem go away.
