search

Fil / d3-geo-voronoi

Voronoi / Delaunay tessellations on the sphere
ISC License
229 stars 24 forks source link

Error in hull #37

Closed Fil closed 3 years ago

Fil commented 3 years ago

This polygon has a broken hull (thanks @harrystevens for the example).

[
  [-99.99981816168162,35.88112731556315],
  [-99.99981816168162,36.055516432754324],
  [-99.99981816168162,36.49965029279292],
  [-100.00340745567455,36.49965029279292],
  [-100.54539084860848,36.49965029279292],
  [-100.95457036380363,36.49965029279292],
  [-101.08378494754947,36.49965029279292],
  [-101.62217904649046,36.49965029279292],
  [-102.03135856168561,36.50050935248352],
  [-102.16416243942439,36.50050935248352],
  [-103.00405723377233,36.50050935248352],
  [-103.0004679397794,36.60273745566455],
  [-103.0004679397794,37.00048209241092],
  [-102.77793171221711,36.99962303272032],
  [-102.69896724437244,36.995327734267335],
  [-102.04212644366443,36.99275055519555],
  [-102.02776926769268,36.99275055519555],
  [-101.5539824606246,36.995327734267335],
  [-101.06583847758478,36.99790491333913],
  [-100.94380248182482,36.99790491333913],
  [-100.63153390443904,36.99962303272032],
  [-100.08955051150511,37.002200211792115],
  [-100.00340745567455,37.00134115210152],
  [-99.5403885305853,36.99962303272032],
  [-99.45783476874769,36.99962303272032],
  [-99.0019944316443,36.99962303272032],
  [-98.54615409454094,36.998763973029725],
  [-98.34874292492924,36.99790491333913],
  [-98.11184952139521,36.99790491333913],
  [-97.80317023800238,36.998763973029725],
  [-97.46218730867308,36.998763973029725],
  [-97.14632943729437,36.998763973029725],
  [-96.75150709807097,36.998763973029725],
  [-96.52538157651576,36.998763973029725],
  [-96.00134465354652,36.998763973029725],
  [-95.96545171361713,36.998763973029725],
  [-95.78598701397013,36.99962303272032],
  [-95.52396855248551,36.99962303272032],
  [-95.40911114471145,36.99962303272032],
  [-95.07171750937509,36.99962303272032],
  [-95.00711021750217,36.99962303272032],
  [-94.61946646626465,36.998763973029725],
  [-94.61946646626465,36.76681785656856],
  [-94.61946646626465,36.668025992149914],
  [-94.61946646626465,36.49965029279292],
  [-94.56203776237761,36.16203983438834],
  [-94.5512698803988,36.101905656046554],
  [-94.49384117651176,35.759140839498386],
  [-94.47230541255412,35.638872482814826],
  [-94.43641247262472,35.42840285861858],
  [-94.43282317863178,35.38630893377933],
  [-94.44718035460355,34.93358447683476],
  [-94.45435894258942,34.7291282704727],
  [-94.4615375305753,34.507490870298696],
  [-94.46871611856118,34.18963878477784],
  [-94.47589470654707,33.94051147450474],
  [-94.48666258852587,33.638122463414625],
  [-94.51896623446234,33.61664597114971],
  [-94.5871628203282,33.67935732856328],
  [-94.64459152421524,33.66818955258552],
  [-94.64818081820817,33.687947925469246],
  [-94.70919881608816,33.687088865778655],
  [-94.73791316803168,33.705988178971786],
  [-94.77380610796108,33.75495458133581],
  [-94.82764551785517,33.741209626286256],
  [-94.87071704577045,33.745504924739244],
  [-94.94609221962219,33.8125115806058],
  [-94.97121727757278,33.86233704266042],
  [-95.05018174541745,33.864055162041616],
  [-95.12196762527626,33.93106181790817],
  [-95.1542712712127,33.93707523574235],
  [-95.22964644506445,33.961128907079065],
  [-95.25477150301502,33.902712848118476],
  [-95.30861091290913,33.880377296162955],
  [-95.34091455884558,33.869209520185194],
  [-95.46295055460554,33.872645758947584],
  [-95.46295055460554,33.88553165430654],
  [-95.53832572845728,33.87951823647236],
  [-95.56345078640786,33.93192087759877],
  [-95.59934372633725,33.93449805667056],
  [-95.68548678216781,33.88982695275952],
  [-95.75727266202662,33.89240413183131],
  [-95.76086195601955,33.872645758947584],
  [-95.77162983799838,33.84343772946729],
  [-95.8003441899419,33.861477982969824],
  [-95.84700501185011,33.8408605503955],
  [-95.93673736167361,33.88724977368773],
  [-95.94032665566655,33.861477982969824],
  [-96.04800547545474,33.83656525194252],
  [-96.10184488534885,33.84773302792027],
  [-96.09825559135591,33.830551834108334],
  [-96.14850570725707,33.83742431163311],
  [-96.1772200592006,33.76010893947939],
  [-96.22747017510174,33.74808210381103],
  [-96.2956667609676,33.764404237932375],
  [-96.32079181891818,33.694820402994026],
  [-96.36386334683347,33.69224322392223],
  [-96.37822052280522,33.725746551855515],
  [-96.42847063870639,33.77900825267252],
  [-96.50384581255813,33.77385389452894],
  [-96.53256016450165,33.822820296892964],
  [-96.57204239842397,33.819384058130574],
  [-96.62947110231102,33.845155848848485],
  [-96.58998886838867,33.894981310903106],
  [-96.67613192421923,33.90872626595265],
  [-96.70484627616275,33.83484713256132],
  [-96.76945356803567,33.827115595345944],
  [-96.78381074400744,33.86319610235102],
  [-96.83047156591566,33.87522293801938],
  [-96.85200732987329,33.84687396822968],
  [-96.88431097580975,33.8683504604946],
  [-96.9058467397674,33.949961131101304],
  [-96.93456109171092,33.95425642955429],
  [-96.94532897368973,33.94910207141071],
  [-96.99557908959089,33.94910207141071],
  [-96.98481120761207,33.88639071399714],
  [-97.04223991149911,33.83742431163311],
  [-97.08890073340733,33.85374644575445],
  [-97.04941849948499,33.81766593874938],
  [-97.0960793213932,33.79876662555625],
  [-97.08531143941438,33.74378680535805],
  [-97.12479367333673,33.71715595494955],
  [-97.16427590725907,33.7291827906179],
  [-97.20734743517434,33.80993440153401],
  [-97.17145449524494,33.83570619225192],
  [-97.17863308323082,33.89240413183131],
  [-97.21093672916729,33.91645780316803],
  [-97.24682966909668,33.90013566904668],
  [-97.25400825708256,33.864055162041616],
  [-97.30066907899078,33.880377296162955],
  [-97.33297272492725,33.87436387832878],
  [-97.37245495884959,33.819384058130574],
  [-97.44424083870838,33.82367935658356],
  [-97.46218730867308,33.849451147301465],
  [-97.45859801468015,33.903571907809074],
  [-97.48372307263072,33.91559874347743],
  [-97.5626875404754,33.89755848997489],
  [-97.5985804804048,33.91817592254922],
  [-97.58781259842598,33.953397369863694],
  [-97.65600918429183,33.98947787686876],
  [-97.6883128302283,33.98690069779697],
  [-97.73138435814357,33.93707523574235],
  [-97.83547388393883,33.85804174420743],
  [-97.87854541185412,33.85031020699206],
  [-97.97904564365643,33.88982695275952],
  [-97.95392058570586,33.937934295432946],
  [-97.97186705567056,33.93707523574235],
  [-97.94674199771997,33.988618817178164],
  [-97.97186705567056,34.00580001099011],
  [-98.01852787757878,33.99377317532175],
  [-98.08672446344463,34.003222831918315],
  [-98.12261740337402,34.08139726376263],
  [-98.09390305143052,34.111464352933524],
  [-98.10826022740227,34.15441733746337],
  [-98.14056387333873,34.141531442104416],
  [-98.16927822528224,34.11404153200532],
  [-98.24106410514105,34.13294084519845],
  [-98.29490351503514,34.13294084519845],
  [-98.36310010090101,34.15699451653516],
  [-98.42411809878098,34.083974442834425],
  [-98.48513609666097,34.0624979505695],
  [-98.57127915249151,34.144967680866806],
  [-98.61076138641386,34.15699451653516],
  [-98.64665432634325,34.164726053750535],
  [-98.68972585425854,34.13294084519845],
  [-98.76510102811028,34.13637708396083],
  [-98.8117618500185,34.15871263591635],
  [-98.85842267192672,34.161289814988145],
  [-98.91944066980669,34.18190724756247],
  [-98.95174431574316,34.21283339642396],
  [-98.98763725567255,34.22142399332993],
  [-99.0450659595596,34.19822938168381],
  [-99.07736960549605,34.211115277042765],
  [-99.12044113341133,34.2016656204462],
  [-99.12761972139721,34.218846814258136],
  [-99.19222701327013,34.21626963518634],
  [-99.21017348323483,34.33653799186991],
  [-99.27478077510774,34.384645334543336],
  [-99.26042359913599,34.403544647736474],
  [-99.31785230302303,34.407839946189455],
  [-99.38245959489595,34.45680634855348],
  [-99.3968167708677,34.37777285701856],
  [-99.43988829878299,34.37433661825618],
  [-99.47578123871239,34.396672170211694],
  [-99.51885276662766,34.41471242371423],
  [-99.57987076450765,34.41643054309542],
  [-99.60140652846528,34.37433661825618],
  [-99.70908534825348,34.38722251361513],
  [-99.79522840408404,34.45422916948169],
  [-99.84547851998519,34.5066318106081],
  [-99.92803228182281,34.577074705237045],
  [-99.99622886768867,34.56075257111571],
  [-99.99981816168162,34.746309464284636],
  [-99.99981816168162,35.030658221872216],
  [-99.99981816168162,35.18271178710786],
  [-99.99981816168162,35.4223894407844],
  [-99.99981816168162,35.61911410993109],
  [-99.99981816168162,35.88112731556315]
];
Fil commented 3 years ago

It probably happens here https://github.com/Fil/d3-geo-voronoi/blob/e08201f5ecad997a8fd21a0dae2dee06b19c10bb/src/delaunay.js#L389

HarryStevens commented 3 years ago

Notebook with some examples https://observablehq.com/d/872d36b2aa6d4caf

Fil commented 3 years ago

more hull errors seen on https://observablehq.com/@fil/pole-of-inaccessibility-of-every-country (see Canada and Western Sahara)