Union fails with error 'Unable to complete output ring starting at...'

[mfogel]

The following geometry causes an exception to be thrown: Error: Unable to complete output ring starting at [-118.472282, 34.027219]. Last matching segment found ends at [-118.467722, 34.025468]. Pulled over from #48.

polygonClipping.union(
  [
    [
      [-118.46571, 34.025348],
      [-118.465871, 34.025308],
      [-118.465936, 34.025348],
      [-118.467899, 34.025348],
      [-118.468194, 34.025197],
      [-118.468983, 34.025174],
      [-118.469245, 34.025348],
      [-118.46571, 34.025348]
    ]
  ],
  [
    [
      [-118.464605, 34.02561],
      [-118.465871, 34.025308],
      [-118.466413, 34.02565],
      [-118.467722, 34.025468],
      [-118.468194, 34.025197],
      [-118.468983, 34.025174],
      [-118.469433, 34.025494],
      [-118.470297, 34.025512],
      [-118.472282, 34.027219],
      [-118.464605, 34.02561]
    ]
  ]
);

[arunasank]

• Version: 0.9.2

• intersect(A,B) still fails with Error: Unable to complete output ring starting at [-105.029296875, 39.92126110424533]. Last matching segment found ends at [-105.015657, 39.943093]. when:

• A:

{"type":"Feature","properties":{"@id":33153017,"@type":"way","@version":1,"@changeset":501814,"@uid":36121,"@user":"Chris Lawrence","@timestamp":1239673272,"is_in":"USA, Colorado","place":"city","source":"TIGER/Line® 2008 Place Shapefiles (http://www.census.gov/geo/www/tiger/)","boundary":"administrative","tiger:CPI":"N","wikipedia":"Broomfield,_Colorado","created_by":"polyshp2osm-multipoly","place_name":"Broomfield","tiger:LSAD":"25","tiger:NAME":"Broomfield","admin_level":"8","border_type":"city","is_in:state":"Colorado","tiger:MTFCC":"G4110","is_in:country":"USA","tiger:CLASSFP":"C1","tiger:PCICBSA":"N","tiger:PLACEFP":"09280","tiger:PLACENS":"02409919","tiger:PLCIDFP":"0809280","tiger:STATEFP":"08","tiger:FUNCSTAT":"A","tiger:NAMELSAD":"Broomfield city","tiger:PCINECTA":"N","tiger:reviewed":"no","is_in:iso_3166_2":"US:CO","is_in:state_code":"CO","is_in:country_code":"US"},"geometry":{"type":"Polygon","coordinates":[[[-105.1171875,39.93246492196627],[-105.11703503318131,39.93233701944206],[-105.11682800017297,39.93216406142747],[-105.11679505929351,39.93213700255325],[-105.11658903211355,39.931964044033236],[-105.11443706229329,39.930166046523595],[-105.1140570268035,39.92940001607897],[-105.1139320526272,39.92914902001354],[-105.11394403874874,39.9291410498289],[-105.11407203041017,39.929052027945545],[-105.11403607204556,39.928981003183026],[-105.11396901682019,39.92884101026792],[-105.11385904625058,39.928611030468176],[-105.11383507400751,39.92855601003262],[-105.11383306235075,39.92855106076232],[-105.11383004486561,39.92854501879546],[-105.11382702738047,39.9285380126843],[-105.11380800046027,39.92849301929277],[-105.11377103626728,39.92839403372733],[-105.11375905014575,39.92836202407878],[-105.11370708234608,39.92818802759487],[-105.11369107291102,39.9281150093598],[-105.11369006708264,39.92810800320464],[-105.1135990396142,39.92768101204564],[-105.11359702795744,39.9276730416901],[-105.11359501630068,39.92766500705653],[-105.1135940104723,39.92765902928858],[-105.11358604766428,39.92762104152507],[-105.11354204267263,39.92748805204812],[-105.11353206820786,39.92745700613497],[-105.11352905072272,39.92744903575331],[-105.11352301575243,39.927430009677295],[-105.11347205378115,39.92732105957927],[-105.11340307071805,39.927204010342706],[-105.11332503519952,39.92709705249078],[-105.11326108127832,39.92702101204131],[-105.11315907351673,39.92691206129237],[-105.11305103078485,39.926808059766756],[-105.11298506520689,39.92674802420348],[-105.11298003606498,39.92674403897152],[-105.11293401941657,39.92670200118789],[-105.11290300637484,39.92667404026247],[-105.11289705522358,39.92666902657808],[-105.11288708075881,39.92666002765645],[-105.11288305744529,39.92665604241938],[-105.11279907077551,39.92657903730867],[-105.11275506578386,39.92654104894589],[-105.11265305802226,39.926453052132814],[-105.11236907914281,39.92620705898079],[-105.11236203834414,39.926201016807056],[-105.11235508136451,39.92619503891123],[-105.11227402836084,39.926129024908846],[-105.11226505972445,39.926122018550416],[-105.11224603280425,39.92610601319683],[-105.11192106641829,39.925841056558994],[-105.11185107752681,39.925791047646214],[-105.11184504255652,39.92578706235852],[-105.11182308197021,39.92577105692666],[-105.11168201453984,39.92566904631505],[-105.11165904812515,39.925654005039945],[-105.11163105256855,39.9256360069287],[-105.11147506535053,39.925532003464554],[-105.11138303205371,39.92547505218053],[-105.11137607507408,39.925471002595316],[-105.11131505481899,39.92543301361766],[-105.11099302209914,39.92523304083457],[-105.11098304763436,39.92522706285425],[-105.11097407899797,39.925221020593995],[-105.11095806956291,39.92521105729145],[-105.11090300045907,39.925177053492945],[-105.11087005957961,39.92515706259414],[-105.11080007068813,39.92511405964402],[-105.11079403571784,39.92511001003746],[-105.11078204959631,39.92510300357475],[-105.11076704598963,39.92509400444732],[-105.11074701324105,39.92508204846183],[-105.11062807403505,39.925009026913926],[-105.11045406572521,39.92490804364144],[-105.11021400801837,39.92477003507082],[-105.11007704772055,39.92469804166788],[-105.11007000692189,39.92469502051446],[-105.1100610382855,39.924690006685154],[-105.11004301719368,39.9246800433053],[-105.11002700775862,39.92467104412225],[-105.10998006910086,39.924648031920185],[-105.10996506549418,39.92464102541021],[-105.10992106050253,39.92462000587594],[-105.10982600972056,39.924575009909375],[-105.10964102111757,39.924507001663756],[-105.10952702723444,39.92447306179571],[-105.10941202752292,39.92443802914906],[-105.10914204642177,39.92435600768982],[-105.10914104059339,39.92458600178392],[-105.1090520247817,39.92561903727662],[-105.10904305614531,39.925744059804146],[-105.10902302339673,39.92587403156759],[-105.10925905779004,39.92602200109883],[-105.10926702059805,39.926027014830595],[-105.1105840690434,39.926850033207415],[-105.1109170820564,39.927058035973175],[-105.11118907481432,39.927252025622124],[-105.11147900484502,39.92748805204812],[-105.11155804619193,39.9275600425172],[-105.11178402230144,39.927785012245124],[-105.11196607723832,39.92798902701057],[-105.11212005279958,39.9281850065955],[-105.11213203892112,39.928200047314476],[-105.11219004169106,39.9282840567397],[-105.11226908303797,39.92839904728538],[-105.11240805499256,39.92862600681738],[-105.11329603381455,39.93024902514176],[-105.11344606988132,39.93054102423528],[-105.11351505294442,39.930702031347096],[-105.11356903240085,39.93086200969506],[-105.11357506737113,39.93088206320206],[-105.11357900686562,39.930895046559215],[-105.11360608041286,39.93099402850817],[-105.11363600380719,39.931163004504555],[-105.11365000158548,39.93127901859302],[-105.11365704238415,39.93144002396892],[-105.11365201324224,39.931597044016655],[-105.11362602934241,39.93180503235871],[-105.11359702795744,39.93194206265156],[-105.1135660149157,39.93205505459102],[-105.1135440543294,39.93211804205308],[-105.11354103684425,39.93212601189106],[-105.11348806321621,39.93227506054541],[-105.11338806711137,39.93247906192914],[-105.11330106295645,39.93262701718365],[-105.11323207989335,39.93273100986886],[-105.1131550502032,39.932830053435055],[-105.11297500692308,39.93303405316465],[-105.11287400498986,39.93313303202041],[-105.1127750147134,39.93321902781915],[-105.11250402778387,39.93342604715758],[-105.11236807331443,39.933518019845025],[-105.11231107637286,39.933555040262945],[-105.11229305528104,39.93356705904017],[-105.1100140158087,39.93503905406757],[-105.10997906327248,39.93506206277664],[-105.1093580480665,39.935463042920134],[-105.10922402143478,39.93554601511681],[-105.10904104448855,39.93566401413261],[-105.10904104448855,39.93575405572838],[-105.10903903283179,39.93606100605976],[-105.10903903283179,39.93611904111211],[-105.10903802700341,39.93612405410437],[-105.10903802700341,39.93613401581865],[-105.10903601534665,39.936484024549316],[-105.10879000648856,39.93646802161851],[-105.10874600149691,39.936465000984555],[-105.10872705839574,39.93646403695243],[-105.10870400816202,39.93646300865146],[-105.10867802426219,39.936461016318304],[-105.10802004486322,39.9364190487708],[-105.10798500850797,39.93641705643637],[-105.10788601823151,39.93641101516383],[-105.10753900744021,39.93638601457292],[-105.10271907784045,39.93638601457292],[-105.09379302151501,39.936385050539656],[-105.091010062024,39.93638601457292],[-105.09099002927542,39.936387042875026],[-105.090944012627,39.936387042875026],[-105.09093403816223,39.93776103351141],[-105.09082607924938,39.939882023971165],[-105.09081208147109,39.94007404931395],[-105.09080805815756,39.94013002447139],[-105.09073304012418,39.941316031538804],[-105.09073102846742,39.94135503992925],[-105.09072105400264,39.941510045043515],[-105.09067503735423,39.94306200475205],[-105.09067503735423,39.94306804543743],[-105.09067403152585,39.94308006254397],[-105.09067403152585,39.9430940075259],[-105.09067302569747,39.94313905558184],[-105.09054101072252,39.94313706344306],[-105.09030506014824,39.94313706344306],[-105.08573901839554,39.94318500328308],[-105.0761210359633,39.9429230045786],[-105.07610100321472,39.94293502171064],[-105.07610100321472,39.94460705331474],[-105.0761020090431,39.946353006807044],[-105.0761020090431,39.94753903452428],[-105.07610402069986,39.950592011877205],[-105.07582708261907,39.950592011877205],[-105.07251807488501,39.9505860361117],[-105.07224105298519,39.9505860361117],[-105.07173805497587,39.950585008022955],[-105.071778036654,39.957502024879346],[-105.07178004831076,39.957785041352764],[-105.07193301804364,39.957785041352764],[-105.07227801717818,39.95778703306499],[-105.07463903166354,39.95780001131749],[-105.07531201466918,39.957802003029286],[-105.07585801184177,39.95780303100955],[-105.07658606395125,39.95780502272126],[-105.07682302035391,39.95780502272126],[-105.07733104750514,39.95781003412466],[-105.07916601374745,39.95782603206382],[-105.07930205203593,39.95782905175474],[-105.07972902618349,39.95784003828862],[-105.08002800866961,39.95784704139996],[-105.08030503056943,39.95780804241309],[-105.0806020013988,39.95782204864156],[-105.08096602745354,39.95783901030893],[-105.0824480317533,39.957908013412265],[-105.08246303535998,39.957908013412265],[-105.08253403007984,39.95791103309955],[-105.08275606669486,39.95791206107816],[-105.08280107751489,39.95791206107816],[-105.08326107636094,39.95791501651664],[-105.08326702751219,39.9582670340219],[-105.08396306075156,39.95830204935271],[-105.08489102125168,39.958201050955296],[-105.08537901565433,39.95808803794068],[-105.08541002869606,39.95808103485402],[-105.08547607809305,39.9580660007023],[-105.08555000647902,39.95805000281928],[-105.08561102673411,39.95803606088603],[-105.08563801646233,39.95803002152235],[-105.08565000258386,39.95802700184032],[-105.08566307835281,39.95802404640668],[-105.08568302728236,39.958020062995985],[-105.08570205420256,39.958016015336455],[-105.08571705780923,39.95800303712497],[-105.08573407307267,39.957988002956114],[-105.08575402200222,39.95797104132569],[-105.08579400368035,39.95793801753325],[-105.08584605529904,39.95789304347119],[-105.08686101995409,39.957849033110364],[-105.086948024109,39.95784305797892],[-105.08731506764889,39.957833035176606],[-105.08772402070463,39.95783804657793],[-105.08783407509327,39.95783901030893],[-105.0878410320729,39.95783901030893],[-105.08787003345788,39.95784003828862],[-105.08829801343381,39.95785102482074],[-105.08833204396069,39.95785301653103],[-105.08844100870192,39.95785802793097],[-105.08858802728355,39.95786503104043],[-105.08859707973897,39.95791906418211],[-105.088613005355,39.95803002152235],[-105.08861401118338,39.958037024614214],[-105.08861501701176,39.95804203600062],[-105.08861602284014,39.958052058772324],[-105.08863605558872,39.9581820334287],[-105.08774807676673,39.95819700330651],[-105.08774807676673,39.95957100569183],[-105.08739301934838,39.95955500816089],[-105.08731003850698,39.95955102483936],[-105.08703301660717,39.959538046919164],[-105.08695104159415,39.95974100331961],[-105.08685800246894,39.95997203494352],[-105.08608200587332,39.96004302754102],[-105.08600204251707,39.960050030426714],[-105.08598200976849,39.96005202207297],[-105.08596105501056,39.96005401371917],[-105.0859500747174,39.96005504166558],[-105.08594202809036,39.96005504166558],[-105.08587706834078,39.96006101660379],[-105.08576408028603,39.96008401689858],[-105.08558303117752,39.960123014587424],[-105.08402701467276,39.960454012197715],[-105.08209305815399,39.96096701677979],[-105.08195701986551,39.9610030586602],[-105.08056201972067,39.96137304898639],[-105.07999003864825,39.961613005177526],[-105.07988501340151,39.961657013115854],[-105.0786320026964,39.96218202242315],[-105.07570001296699,39.964623018625446],[-105.07473500445485,39.96575200449996],[-105.0730590429157,39.96730803948617],[-105.07188607938588,39.96854400273378],[-105.07046802900732,39.96972103781113],[-105.06960502825677,39.97022703525511],[-105.06742003373802,39.971289058841364],[-105.06660900078714,39.97192505744536],[-105.06352705881,39.97344401733878],[-105.06096806377172,39.97456302988326],[-105.06044503301382,39.974768061364955],[-105.05784002132714,39.97578704328822],[-105.05765402689576,39.9758600106494],[-105.05468800663948,39.976889060532784],[-105.05405022762716,39.97712009843963],[-105.029296875,39.97712009843963],[-105.029296875,39.92126110424533],[-105.0300770625472,39.92126502551338],[-105.0308630336076,39.92126701828886],[-105.03165101632476,39.921276017919325],[-105.03243707120419,39.921284053302685],[-105.03322404809296,39.92129202440205],[-105.03438100218773,39.92130500957805],[-105.03439508378506,39.92130500957805],[-105.03438904881477,39.92122401289549],[-105.03439206629992,39.92115503707362],[-105.03440405242145,39.920888004205864],[-105.03440505824983,39.92080501424118],[-105.03441100940108,39.920471060577995],[-105.03440606407821,39.919492010904634],[-105.03440505824983,39.919288035103705],[-105.03440505824983,39.91918100060016],[-105.03440304659307,39.917579063017286],[-105.03440304659307,39.91753701960647],[-105.03438301384449,39.91710700531846],[-105.03436306491494,39.91656904972086],[-105.03436205908656,39.915622024168215],[-105.03436205908656,39.91542800156776],[-105.03434705547988,39.91418104929875],[-105.03882802091539,39.91419403582316],[-105.03907000645995,39.914195000168945],[-105.04173603840172,39.91420400072883],[-105.04197802394629,39.91420502936418],[-105.04299206659198,39.91420805098039],[-105.04347804933786,39.91420901532598],[-105.04368801601231,39.91421004396125],[-105.04384400323033,39.91421100830678],[-105.04410702735186,39.91421203694205],[-105.04629403352737,39.91421904451917],[-105.046441052109,39.91422000886459],[-105.04771501757205,39.91422701644092],[-105.04854407161474,39.91421402992273],[-105.04876007325947,39.91421705153857],[-105.05295705981553,39.91422405911521],[-105.05293702706695,39.91407702843517],[-105.0528840534389,39.913795052666785],[-105.05310902372003,39.913795052666785],[-105.05400907248259,39.913797045659635],[-105.05475606769323,39.91378900939776],[-105.0547850690782,39.91378900939776],[-105.05479202605784,39.91378804504626],[-105.05482303909957,39.91378804504626],[-105.05509603768587,39.91378502341152],[-105.05537104792893,39.91378200177661],[-105.05542100407183,39.9129170372361],[-105.05756207741797,39.91289601410287],[-105.05780003964901,39.91289903577686],[-105.05780003964901,39.91410004418992],[-105.05779601633549,39.914271054862866],[-105.0590770225972,39.91425003214525],[-105.05907802842557,39.91410403015783],[-105.05907903425395,39.91393404770727],[-105.05908305756748,39.912921023272844],[-105.05922705866396,39.912927002327535],[-105.05934700369835,39.91292005890915],[-105.06053606048226,39.912939024726285],[-105.06055408157408,39.9141070517785],[-105.0605530757457,39.91425601108395],[-105.06224202923477,39.914286034348834],[-105.06224404089153,39.91411701669685],[-105.06224404089153,39.913881008467484],[-105.06224806420505,39.913002029776095],[-105.06217505782843,39.91181000298394],[-105.0621710345149,39.91177104204726],[-105.0621710345149,39.91176506289162],[-105.06217002868652,39.91175606201122],[-105.06216902285814,39.911751047234475],[-105.06215301342309,39.91159803207552],[-105.06215301342309,39.91158703811607],[-105.06210356019437,39.90973623453718],[-105.10599724017084,39.90973623453718],[-105.10662202723324,39.91003700075464],[-105.10763506405056,39.91067106150646],[-105.10754101909697,39.91076801532026],[-105.10659202001989,39.91187403774265],[-105.1065830513835,39.911885031656055],[-105.10656704194844,39.91190406205166],[-105.10656000114977,39.911912034242846],[-105.10656503029168,39.91191402729049],[-105.10721705853939,39.912237028827604],[-105.10722401551902,39.91223002104769],[-105.10723206214607,39.91222204889351],[-105.10724706575274,39.91223002104769],[-105.10749408043921,39.91235905409155],[-105.1075530052185,39.91239004255914],[-105.10762601159513,39.9124280387731],[-105.1076330523938,39.912432024838296],[-105.10822607204318,39.91274100847815],[-105.10823302902281,39.91274505881623],[-105.10822204872966,39.91275804561292],[-105.10817804373801,39.912810057066054],[-105.10815901681781,39.91283101593464],[-105.10805306956172,39.912954004503604],[-105.10802004486322,39.9129920004047],[-105.10765400715172,39.913416061518745],[-105.10811400599778,39.91376605782861],[-105.10894004255533,39.91438504031109],[-105.10895605199039,39.91438504031109],[-105.10924405418336,39.91437906138364],[-105.11011401191354,39.91436003167567],[-105.1119570247829,39.914287062982936],[-105.11363105848432,39.914221037499686],[-105.1145330350846,39.914186063897574],[-105.11555302888155,39.914146011386464],[-105.1156250294298,39.914143054057234],[-105.1163380779326,39.914115023713265],[-105.1171875,39.914115023713265],[-105.1171875,39.93246492196627]]]}}

• B

{"type":"Feature","properties":{"STATEFP":"08","COUNTYFP":"014","COUNTYNS":"01945881","GEOID":"08014","NAME":"Broomfield","NAMELSAD":"Broomfield County","LSAD":"06","CLASSFP":"H6","MTFCC":"G4020","CSAFP":"216","CBSAFP":"19740","METDIVFP":null,"FUNCSTAT":"C","ALAND":85478932,"AWATER":1411395,"INTPTLAT":"+39.9532103","INTPTLON":"-105.0519954"},"geometry":{"type":"Polygon","coordinates":[[[-105.1171875,39.953339048583],[-105.117109,39.953381],[-105.117096,39.953387],[-105.115972,39.953907],[-105.113654,39.954809],[-105.113353,39.954908],[-105.112798,39.955089],[-105.111751,39.955416],[-105.110948,39.955666],[-105.109537,39.956105],[-105.109528,39.956457],[-105.109525,39.956586],[-105.109521,39.956698],[-105.10952,39.956807],[-105.109517,39.956996],[-105.110587,39.956667],[-105.111657,39.956333],[-105.11188,39.956264],[-105.113183,39.955858],[-105.113311,39.955818],[-105.114389,39.955458],[-105.115643,39.954984],[-105.116505,39.954622],[-105.117094,39.95433],[-105.1171875,39.95428783761682],[-105.1171875,39.953339048583]],[[-105.082566,39.959277],[-105.082052,39.958861],[-105.081887,39.958727],[-105.081378,39.958408],[-105.081217,39.958337],[-105.081081,39.958287],[-105.080958,39.958246],[-105.080722,39.958184],[-105.080466,39.958138],[-105.080371,39.958128],[-105.080183,39.958109],[-105.080044,39.958104],[-105.080048,39.957928],[-105.079718,39.957925],[-105.078538,39.957914],[-105.077609,39.957906],[-105.076348,39.957927],[-105.075878,39.957936],[-105.07299,39.957937],[-105.072977,39.957937],[-105.071954,39.957938],[-105.071937,39.957938],[-105.071787,39.957937],[-105.07168,39.957936],[-105.071663,39.957786],[-105.068111,39.957793],[-105.068016,39.957793],[-105.064899,39.9578],[-105.063463,39.957767],[-105.062361,39.957766],[-105.061561,39.957771],[-105.061079,39.957765],[-105.060983,39.957765],[-105.060959,39.957765],[-105.060939,39.957765],[-105.060909,39.957765],[-105.060861,39.957765],[-105.060774,39.957765],[-105.060156,39.957766],[-105.059992,39.957766],[-105.059831,39.957767],[-105.059701,39.957767],[-105.059332,39.957763],[-105.059328,39.958708],[-105.058195,39.958716],[-105.058207,39.957894],[-105.058173,39.95789],[-105.057627,39.957883],[-105.055337,39.957856],[-105.055225,39.957855],[-105.05482,39.957852],[-105.054584,39.95785],[-105.053725,39.957838],[-105.052889,39.957826],[-105.052875,39.959771],[-105.052846,39.962028],[-105.052839,39.962521],[-105.052837,39.962784],[-105.052833,39.964319],[-105.052828,39.965892],[-105.053804,39.965875],[-105.054202,39.96587],[-105.056228,39.967444],[-105.057747,39.968636],[-105.057724,39.972362],[-105.057713,39.974121],[-105.057709,39.974669],[-105.058473,39.974345],[-105.061442,39.973099],[-105.062232,39.972783],[-105.062262,39.972767],[-105.062378,39.972706],[-105.062376,39.972747],[-105.062804,39.972554],[-105.063517,39.972232],[-105.064311,39.971894],[-105.065075,39.971554],[-105.065619,39.971283],[-105.065985,39.971102],[-105.066138,39.971018],[-105.067269,39.970369],[-105.06833,39.969662],[-105.069801,39.968482],[-105.069877,39.968414],[-105.069953,39.968346],[-105.071903,39.966566],[-105.073362,39.965202],[-105.074735,39.963935],[-105.076567,39.962466],[-105.076796,39.962306],[-105.078562,39.961238],[-105.078836,39.96107],[-105.078931,39.96102],[-105.081217,39.959818],[-105.081672,39.959634],[-105.082349,39.959364],[-105.082566,39.959277]]]}}

[rowanwins]

Resolved by this commit

[mfogel]

Thanks @arunasank and @rowanwins for following up on this

@arunasank - based on the error message you posted it looks like the coordinates you used to generate this error are different than the ones that this bug started out with. If you still have those other coordinates around... once a new version of this library is released to NPM (it will be v0.10, will be released later today), could you check to see if this error is now fixed for those other coordinates? If you still get an error, please either re-open this bug or open a new one.