Berechnen Voronoï Diagramm auf einem großen Datensatz von sehr nahen Punkten

Question

Ich habe einen großen Datensatz von geographischen Punkten (rund 22 000 Punkte, aber ich könnte mehr in der Zukunft sein) und ich muss ihre Voronoï-Diagramm berechnen. Ich projiziere zuerst meine Punkte von (lat,lng) bis (x,y) (mit latLngToLayerPoint() aus Leaflet) und berechne dann das Diagramm basierend auf einem Javascript implementation of Fortune's algorithm. I zu jede Zelle der Diagramme oder genauer va und vb jeweils infrage kommen:

„A Voronoi.Vertex Objekt mit einer x und y-Eigenschaft Definition den Start- Punktes (bezogen auf die Voronoi Stelle auf der linken Seite) von diesem Voronoi.Edge Objekt. "

und

"A Voronoi.Vertex Objekt mit einer x und einer y-Eigenschaft definiert, um das Ende Punkt (bezogen auf Voronoi Stelle auf der linken Seite) dieses Voronoi.Edge Objekt."

(vgl Dokumentation)

Schließlich Projekt, das ich diese Punkte wieder das Diagramm angezeigt werden Faltblatt mit. Ich weiß, dass jeder Punkt einzigartig sein muss, um das Diagramm zu berechnen, also werde ich die Duplikate los, bevor ich das Diagramm berechne. Aber die Sache ist, dass ich mit einem ziemlich schlechten Ergebnis am Ende (nicht-knotigen Kreuzungen, komplexe Polygone):

Nahaufnahme

Ich habe Löcher in dem Diagramm und ich bin mir nicht sicher warum. Die Punkte sind Hausadresse, also sind einige von ihnen, selbst wenn sie nicht gleich sind, wirklich (wirklich) nah. Und ich frage mich, ob das Problem nicht von der Projektion kommt (wenn (lat1,lng1) und (lat2,lng2) fast gleich sind, werden (x1,y1) und (x2,y2) gleich sein?). Ich vermute stark, dass ist, wo das Problem herkommen, aber ich weiß nicht, wie man umgehen kann (einen Schwellenwert festlegen?)

Bearbeiten: Ich präzis, dass ich die Duplikate nach der Projektion löschen, so ist es nicht über die Präzision der Projektion, aber mehr darüber, was passiert, wenn zwei Punkte ein Pixel auseinander liegen?

Answer 1

So fand ich die Lösung für mein Problem, ich poste es für jeden Fall muss ein Voronoï-Diagramm auf einer Karte mit Leaflet und Turf berechnen und hat Probleme mit der Implementierung des Fortune-Algorithmus (bis Turf-Voronoi funktioniert). Other sources of how to compute a Voronoï diagram on map can be found (but using d3) (ich glaube, d3 auch diese verwenden Javascript Implementierung der Fortune-Algorithmus)

Das Problem ist nicht durch die Größe des Datensatzes oder die Nähe der Punkte verursacht wurde, sondern davon, wie ich die Zellen gewonnen.

So müssen Sie zuerst Punkt (lat,lng)-(x,y) (mit latLngToLayerPoint()) projizieren, berechnen Sie das Diagramm: voronoi.compute(sites,bbox), wo die Standorte Ihre Punkte sind, die wie dieser [ {x: 200, y: 200}, {x: 50, y: 250}, {x: 400, y: 100} /* , ... */ ] (beachten Sie, dass Ihre Seiten einzigartige sein muss) und wenn Sie den Rahmen des Bildschirms für das aktuelle Zoom möchten Ihre bbox juste nutzen sein:

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

Nachdem Sie das Diagramm berechnet, nur die Zellen wiederherzustellen (sein carfull, wenn Sie die richtigen Polygone wollen, müssen Sie die Ränder im Gegenuhrzeigersinn angeordnet sein (oder im Uhrzeigersinn geordnet, aber du bist o Der Algorithmus liefert die halben Kanten eines vorgegebenen Voronoï.Vertex entgegen dem Uhrzeigersinn geordnet). den Scheitelpunkt jeder Zelle erholen Sie entweder getStartpoint() oder getEndpoint() ohne zu vergessen, können sie (x,y)-(lat,lng) (mit 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)); 
}); 

schließlich zurück zum Projekt, müssen Sie ein FeatureCollection verwenden Sie das Diagramm angezeigt werden:

Answer 2

Ich empfehle Ihnen, einen Voronoi-Tesselationsalgorithmus nicht selbst zu implementieren und stattdessen https://github.com/Turfjs/turf-voronoi zu verwenden.