Reputation: 919
I have a large dataset of geographical points (around 22 000 points, but I could be more in the future) and I need to compute their Voronoï diagram. I first project my points from (lat,lng)
to (x,y)
(using latLngToLayerPoint() from Leaflet) and then compute the diagram based on a Javascript implementation of Fortune's algorithm . I recover each cells of the diagrams or more precisely va
and vb
, being respectively :
"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."
and
"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."
(cf. Documentation)
Finally, I project back these points to display the diagram using leaflet. I know that, in order to compute the diagram each point needs to be unique, so I get rid of duplicates before computing the diagram. But the thing is, I end up with a pretty bad result (non-noded intersections, complex polygons):
Close-up
I have holes in the diagram and I'm not sure why. The points are house Address so some of them, even if they are not equals, are really (really) close. And I wonder if the issue doesn't come from the projection (if (lat1,lng1)
and (lat2,lng2)
are almost equals, will (x1,y1)
and (x2,y2)
be equals ?). I strongly suspect that is where the issue come from, but I don't know how to workaround (establish a threshold ?)
Edit : I precise that I delete the duplicates after the projection, so it's not about the precision of the projection but more about what happen if two points are one-pixel apart ?
Upvotes: 4
Views: 566
Reputation: 919
So I found the solution to my problem, I post it in case of anyone need to compute a Voronoï diagram on a map using Leaflet and Turf and is having troubles implementing the Fortune's algorithm (until turf-voronoi works). Other sources of how to compute a Voronoï diagram on map can be found (but using d3) (I think d3 also use this Javascript implementation of Fortune's algorithm)
The problem was not caused by the size of the dataset or the proximity of the points, but by how I recovered the cells.
So you first need to project your point from (lat,lng)
to (x,y)
(using latLngToLayerPoint()
), compute the diagram : voronoi.compute(sites,bbox)
, where the sites are your points looking like this [ {x: 200, y: 200}, {x: 50, y: 250}, {x: 400, y: 100} /* , ... */ ]
(note that your sites needs to be unique) and if you want the frame of the screen for your current zoom to be your bbox juste use :
var xl = 0,
xr = $(document).width(),
yt = 0,
yb = $(document).height();
Once you computed the diagram, just recover the cells (be carfull, if you want the right polygons you need the edges to be counterclockwise ordered (or clockwise ordered, but you them to be ordered), thankfully the algorithm provides the half edges of a given Voronoï.Vertex
counterclockwise ordered). To recover the vertex of each cell you can use either getStartpoint()
or getEndpoint()
without forgetting to project them back from (x,y)
to (lat,lng)
(using 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));
});
Finally, you have to use a FeatureCollection
to display the diagram :
Upvotes: 1
Reputation: 19069
I highly recomment you don't implement a Voronoi tesselation algorithm by yourself, and use https://github.com/Turfjs/turf-voronoi instead.
Upvotes: 0