在非常接近的點的大型數據集上計算沃羅諾圖

Question

我有一個很大的地理點數據集（大約22000點，但我可能會在將來更多），我需要計算他們的沃羅諾圖。我首先從(lat,lng)到(x,y)（使用Leaflet中的latLngToLayerPoint（））計算我的分數，然後根據Javascript implementation of Fortune's algorithm計算圖。我恢復或框圖的每個細胞更精確地va和vb，分別爲：

「具有x和y屬性定義開始 點（相對於沃羅諾伊站點左側）甲Voronoi.Vertex對象這個Voronoi.Edge 對象。「

和

「具有x和y屬性定義所述端 點（相對於左側沃羅諾伊點）此Voronoi.Edge 對象的Voronoi.Vertex對象」。

（參見文檔）

最後，我被投影回這些點用單張顯示圖。我知道，爲了計算圖，每個點都需要是唯一的，所以我在計算圖之前擺脫了重複。但事實是，我結束了一個非常糟糕的結果（非聯接的交叉口，複雜的多邊形）：

特寫

我有圖中孔我不知道爲什麼。這些要點是房屋地址，所以他們中的一些人，即使他們不是平等的，真的（真的）很接近。我想知道問題是否不是來自投影（如果(lat1,lng1)和(lat2,lng2)幾乎相等，(x1,y1)和(x2,y2)是否等於？）。我強烈懷疑這是問題的來源，但我不知道如何解決方法（建立一個閾值？）

編輯：我確切地說我刪除投影后的副本，所以它不是關於投影的精度，但更多關於如果兩點相距一個像素會發生什麼？

Answer 1

所以我找到了解決我的問題的方法，我發佈了它，以防任何人需要使用Leaflet和Turf在地圖上計算Voronoï圖並且遇到了實現Fortune算法（直到turf-voronoi工作）的麻煩。 Other sources of how to compute a Voronoï diagram on map can be found (but using d3)（我覺得D3也用這個Javascript實現財富的算法）

的問題不是由數據集的大小或點的接近造成的，而是我如何回收細胞。

所以，你首先需要投影貴一點從(lat,lng)到(x,y)（使用latLngToLayerPoint()），計算圖表：voronoi.compute(sites,bbox)，其中網站是貴點看起來像這樣[ {x: 200, y: 200}, {x: 50, y: 250}, {x: 400, y: 100} /* , ... */ ]（請注意，您的網站必須是獨特）和如果你想在屏幕的邊框爲您當前的變焦是你的BBOX中庸之道使用：

var xl = 0, 
    xr = $(document).width(), 
    yt = 0, 
    yb = $(document).height(); 

一旦你計算出的圖，只是恢復細胞（是carfull，如果你想正確的多邊形，你需要的邊緣按逆時針順序（或按順時針順序排列，但你將它們設爲o有趣的是，該算法提供了逆時針排列的給定Voronoï.Vertex的半邊）。要（用layerPointToLatLng()）

diagram.cells.forEach(function (c) { 
    var edges=[]; 

    var size = c.halfedges.length; 
    for (var i = 0; i < size; i++) { 

     var pt = c.halfedges[i].getEndpoint(); 
     edges.push(map.layerPointToLatLng(L.point(pt.x,pt.y))); 

    }; 

    voronoi_cells.push(L.polygon(edges)); 
}); 

最後恢復每個單元的頂點，你可以使用getStartpoint()或getEndpoint()沒有忘記對項目回從(x,y)到(lat,lng)，你必須使用一個FeatureCollection顯示圖：

Answer 2

我強烈推薦你不要自己實現Voronoi算法，而應該使用https://github.com/Turfjs/turf-voronoi。