在非常接近的点的大型数据集上计算 Voronoï 图

Question

我有一个很大的地理点数据集（大约 22 000 个点，但将来可能会更多），我需要计算它们的 Voronoï 图。我首先将我的点从 (lat,lng) 投影到 (x,y)（使用 Leaflet 中的 latLngToLayerPoint()），然后根据 Javascript implementation of Fortune's algorithm 计算图表。我恢复了图表的每个单元格或更准确地说 va 和 vb，分别是：

"A Voronoi.Vertex object with an x and a y property defining the start point (relative to the Voronoi site on the left) of this Voronoi.Edge object."

和

"A Voronoi.Vertex object with an x and a y property defining the end point (relative to Voronoi site on the left) of this Voronoi.Edge object."

（参见文档）

最后，我将这些点投影回来，以使用传单显示图表。我知道，为了计算图表，每个点都必须是唯一的，所以我在计算图表之前去掉了重复项。但问题是，我最终得到了一个非常糟糕的结果（非节点交叉点，复杂的多边形）：

特写

图表中有漏洞，我不确定为什么。这些点是房屋地址，所以其中一些点，即使它们不相等，也确实（真的）很接近。我想知道问题是否不是来自投影（如果 (lat1,lng1) 和 (lat2,lng2) 几乎相等，那么 (x1,y1) 和 (x2,y2) 会相等吗？）。我强烈怀疑这就是问题所在，但我不知道如何解决（建立阈值？）

Edit ：我准确地说我删除了投影后的重复项，所以这与投影的精度无关，但更多的是如果两点相距一个像素会发生什么？

Answer 1

我强烈建议您不要自己实现 Voronoi 曲面细分算法，而是使用 https://github.com/Turfjs/turf-voronoi。

Answer 2

所以我找到了我的问题的解决方案，我 post 它是为了防止有人需要使用 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 Fortune 算法的实现）

问题不是由数据集的大小或点的接近引起的，而是我如何恢复细胞引起的。

因此您首先需要将您的点从 (lat,lng) 投影到 (x,y)（使用 latLngToLayerPoint()），计算图表：voronoi.compute(sites,bbox)，其中站点是您的点看起来像这样 [ {x: 200, y: 200}, {x: 50, y: 250}, {x: 400, y: 100} /* , ... */ ]（请注意，您的网站需要唯一），如果您希望当前缩放的屏幕框架成为您的 bbox juste 使用：

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

一旦你计算出图表，只需恢复单元格（小心点，如果你想要正确的多边形，你需要边逆时针排序（或顺时针排序，但你要排序），谢天谢地算法提供给定 Voronoï.Vertex 逆时针排序的半边）。要恢复每个单元格的顶点，您可以使用 getStartpoint() 或 getEndpoint() 而不会忘记将它们从 (x,y) 投影回 (lat,lng)（使用 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));
});

最后，您必须使用 FeatureCollection 来显示图表：

在非常接近的点的大型数据集上计算 Voronoï 图

Compute Voronoï diagram on a large dataset of very close points

javascript

gis

voronoi

computational-geometry

leaflet