kwn
kwn

Reputation: 919

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

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):

enter image description here

Close-up

enter image description here

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

Answers (2)

kwn
kwn

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 :

enter image description here

Upvotes: 1

IvanSanchez
IvanSanchez

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

Related Questions