Wie kann ich eine effiziente Bereichssuche durchführen + mit Breiten-/Längengraddaten zählen?

Question

Ich arbeite mit einer großen Anzahl von Punkten, die durch Breiten-/Längengradpaare repräsentiert werden (die Punkte sind nicht unbedingt eindeutig, es könnte mehrere Punkte in der Menge geben, die sich am selben Ort befinden). Die Punkte werden in einer Datenbank gespeichert.

Was ich tun muss, ist herauszufinden, wie man effektiv eine Suche durchführt, um die Anzahl der Punkte zu erhalten, die innerhalb eines bestimmten Radius (z. B. 25 Meilen) eines beliebigen Punktes liegen. Die Zählung muss nicht 100% genau sein - wichtiger ist, dass sie nur schnell und einigermaßen nahe an der korrekten Anzahl sein muss. Dies ist mit SQL möglich, indem eine Abfrage mit einer Trigonometrie in der WHERE-Klausel verwendet wird, um Punkte anhand ihrer Entfernung zu einem Referenzpunkt zu filtern. Leider ist diese Abfrage sehr, sehr teuer und Caching wird wahrscheinlich nicht viel Hilfe bieten, da die Standorte sehr verteilt sein werden.

Ich möchte letztendlich eine Art In-Memory-Struktur aufbauen, die diese Art von Operation effizient abwickeln kann - ein wenig Genauigkeit und Lebendigkeit der Daten abzutun (vielleicht nur einmal am Tag) als Gegenleistung für die Geschwindigkeit. Ich habe etwas über kd-Bäume geforscht, aber ich bin noch nicht klar darüber, wie gut dies auf Breiten-/Längengraddaten angewendet werden kann (im Gegensatz zu x, y-Daten in einer 2d-Ebene).

Wenn jemand irgendwelche Ideen oder Lösungen hat, die ich untersuchen sollte, würde ich es sehr schätzen - also danke im Voraus.

Answer 1

Verwenden Sie eine Art Suchbaum für räumliche Daten, z. a quad tree. Weitere solche Datenstrukturen sind unter "Siehe auch" aufgeführt.

Answer 2

Können Sie vielleicht ein Beispiel Ihrer vorhandenen teuren Abfrage liefern?

Wenn Sie eine korrekte Großkreisberechnung basierend auf dem Sinus() und Kosinus() des Referenzpunkts und der anderen Datenpunkte durchführen, dann könnte eine sehr substantielle Optimierung durch tatsächliches Speichern dieser sin/cos vorgenommen werden Werte in der Datenbank zusätzlich zu den Lat/Long-Werten.

Alternativ verwenden Sie einfach Ihre Datenbank, um ein Rechteck von lat/long Bereichen zu extrahieren, die übereinstimmen, und filtern Sie nur diejenigen heraus, die außerhalb des wahren kreisförmigen Radius sind.

Bedenken Sie jedoch, dass ein Längengrad in hohen Breiten eine etwas kürzere Entfernung ist als am Äquator. Es sollte jedoch leicht sein, das richtige Seitenverhältnis für dieses Rechteck herauszufinden. Sie hätten auch Fehler, wenn Sie Bereiche sehr nahe an den Polen betrachten müssten, da eine rechteckige Auswahl nicht mit einem Kreis umgehen würde, der einen Pol überlappt.

Answer 3

Verwenden Sie R-Trees.

CREATE INDEX ix_spatial ON spatial_table (locations) INDEXTYPE IS MDSYS.SPATIAL_INDEX; 

, die ein R-Tree für Sie und suchen über sie schaffen:

In Oracle mit Oracle Spatial, können Sie einen Index erstellen.

Sie können eine beliebige Earth Model wie: WGS84, PZ-90 usw. verwenden.

Answer 4

Diese UDF (SQL Server) werden Sie den Abstand zwischen zwei lat/lon Punkte:

CREATE FUNCTION [dbo].[zipDistance] (
    @Lat1 decimal(11, 6), 
    @Lon1 decimal(11, 6), 
    @Lat2 decimal(11, 6), 
    @Lon2 decimal(11, 6) 
) 
RETURNS 
    decimal(11, 6) AS 
BEGIN 

    IF @Lat1 = @Lat2 AND @Lon1 = @Lon2 
     RETURN 0 /* same lat/long points, 0 distance = */ 

    DECLARE @x decimal(18,13) 
    SET @x = 0.0 

    /* degrees -> radians */ 
    SET @Lat1 = @Lat1 * PI()/180 
    SET @Lon1 = @Lon1 * PI()/180 
    SET @Lat2 = @Lat2 * PI()/180 
    SET @Lon2 = @Lon2 * PI()/180 

    /* accurate to +/- 30 feet */ 
    SET @x = Sin(@Lat1) * Sin(@Lat2) + Cos(@Lat1) * Cos(@Lat2) * Cos(@Lon2 - @Lon1) 
    IF 1 = @x 
     RETURN 0 

    DECLARE @EarthRad decimal(5,1) 
    SET @EarthRad = 3963.1 

    RETURN @EarthRadius * (-1 * ATAN(@x/SQRT(1 - @x * @x)) + PI()/2) 

END 

Und natürlich können Sie dies in einer separaten Abfrage verwenden wie:

SELECT * FROM table WHERE [dbo].[zipDistance] < 25.0 

Answer 5

ich glaube nicht, sollten Sie diese Lösung verwenden. Nachdem ich vor ein paar Tagen zufällig darüber nachgedacht habe, denke ich, dass das Messen der Entfernung von einem bestimmten Punkt die Orte der Gitterquadrate auf Kreisen statt auf einem uniformierten Gitter basieren wird. Je weiter weg von 0,0 Sie sind, desto ungenauer wird dies sein!

Was ich getan habe, war 2 zusätzliche Werte auf meiner PostalCode-Klasse zu haben. Immer, wenn ich zu aktualisieren, um die Lang/Lat auf einem Postal ich eine X berechnen, Y Abstand von Long 0, Lat 0.

public static class MathExtender 
{ 
    public static double GetDistanceBetweenPoints(double sourceLatitude, double sourceLongitude, double destLatitude, double destLongitude) 
    { 
     double theta = sourceLongitude - destLongitude; 
     double distance = 
      Math.Sin(DegToRad(sourceLatitude)) 
      * Math.Sin(DegToRad(destLatitude)) 
      + Math.Cos(DegToRad(sourceLatitude)) 
      * Math.Cos(DegToRad(destLatitude)) 
      * Math.Cos(DegToRad(theta)); 
     distance = Math.Acos(distance); 
     distance = RadToDeg(distance); 
     distance = distance * 60 * 1.1515; 
     return (distance); 
    } 


    public static double DegToRad(double degrees) 
    { 
     return (degrees * Math.PI/180.0); 
    } 

    public static double RadToDeg(double radians) 
    { 
     return (radians/Math.PI * 180.0); 
    } 
} 

Dann habe ich meine Klasse aktualisieren, wie so:

private void CalculateGridReference() 
{ 
    GridReferenceX = MathExtender.GetDistanceBetweenPoints(0, 0, 0, Longitude); 
    GridReferenceY = MathExtender.GetDistanceBetweenPoints(0, 0, Latitude, 0); 
} 

So, jetzt habe ich eine x, y Rasterentfernung (in Meilen) vom Rasterbezug 0,0 für jede Zeile in meinem DB. Wenn ich alle Orte mit 5 Meilen von langer finden wollen/lat würde ich zuerst die X bekommen, Y-Gitterreferenz (etwa 25,75), dann würde ich 20..30, 70..80 in der DB suchen, und weiter filtern die Ergebnisse im Speicher mit

MathExtensder.GetDistanceBetweenPoints(candidate.Lat, candidate.Long, search.Lat, search.Long) < TheRadiusOfInterest 

die in DB Teil schnell extrem ist, und der in dem Speicherteil arbeitet in einem kleineren Satz es extrem präzise zu machen.

Answer 6

Sie können eine ausgezeichnete explaination der Bombe Vorschlags in dem Jan Philipp Matuschek Artikel „Finding Points Within a Distance of a Latitude/Longitude Using Bounding Coordinates“ finden.