Wie suche ich effizient nach allen Orientierungspunkten innerhalb eines Bereichs eines bestimmten Orientierungspunkts?

14

Ich versuche, mit einem Geosuchprojekt zu beginnen, das alle Orientierungspunkte in den 10 km / Meilen (für diese Geschichte nicht wichtig) eines bestimmten Orientierungspunkts findet.

Nehmen wir zum Beispiel an, ich habe eine Datenbank mit 1.000.000 Sehenswürdigkeiten. Um alle Orientierungspunkte im 10-Meilen-Bereich eines Orientierungspunkts mit bestimmten Koordinaten zu finden, müsste ich eine Entfernung zwischen einem Orientierungspunkt aus meiner Suche und 1.000.000 Orientierungspunkten berechnen.

Gibt es einen besseren Weg, das zu tun?

Als Alternative habe ich gedacht, Sehenswürdigkeiten wie Land, Region, Stadt, Nachbarschaft, Geschäft, Historie usw. so zu kategorisieren, dass das Geschäft Teil einer Nachbarschaft oder Stadt sein kann. Stadt ist ein Teil einer Region, eines Landes usw. Dies kann eine Liste von Berechnungen einschränken, aber es sieht nach viel Arbeit aus, um eine schnelle und genaue Suche zu ermöglichen.

Könnte das Google Maps API helfen?

Dario Granich
quelle
5
Sie könnten wahrscheinlich viele eliminieren, indem Sie einfach eine schnelle Manhattan-Entfernungsberechnung durchführen und anschließend einen zweiten Filter ausführen, um Orientierungspunkte auszuschließen, die sich innerhalb eines Quadrats von 10 km, jedoch außerhalb des Radius von 10 km befinden.
Neil
3
Welche Datenbanktechnologie verwenden Sie? Die Antwort ist nicht datenbankunabhängig.
jpmc26
1
@Neil Als zweiten Durchgang können Sie jede Landmarke einfügen, bei der x und y in 7 km Entfernung vom Ursprung liegen, ohne die tatsächliche Entfernung zu berechnen.
JimmyJames

Antworten:

10

Seit SQL Server 2008 gibt es einen geografischen Datentyp, der Standorte (Lat / Lon-Paare) speichert und das Schreiben standortbezogener Abfragen erleichtert.

Es gibt eine vorhandene StackOverflow-Antwort, die diese eingehende Beschreibung enthält.

Eine grundlegende Abfrage, um die nächsten 7 Elemente zu finden :

USE AdventureWorks2012  
GO  
DECLARE @g geography = 'POINT(-121.626 47.8315)';  
SELECT TOP(7) SpatialLocation.ToString(), City FROM Person.Address  
WHERE SpatialLocation.STDistance(@g) IS NOT NULL  
ORDER BY SpatialLocation.STDistance(@g);  

Eine grundlegende Abfrage, um alles innerhalb von 100 m zu finden (zweite Antwort auf die Frage)

-- Get the center point
DECLARE @g geography
SELECT @g = geo FROM yourTable WHERE PointId = something

-- Get the results, radius 100m
SELECT * FROM yourTable WHERE @g.STDistance(geo) <= 100
Flater
quelle
11
@KonradRudolph: Wie bei jeder SQL-Spalte, die zum Abfragen einer Tabelle mit einer großen Zeilenanzahl verwendet wird. Sie haben Recht, aber dieser Kommentar gilt für praktisch jede SQL-Abfrage, die als Antwort gesendet wird.
Flater
2
Wo haben Sie in der Frage "MS SQL Server" gelesen?
Doc Brown
3
@Flater Ich stimme zu, dass dies normalerweise offensichtlich und überflüssig wäre, aber der Wortlaut von OP scheint darauf hinzudeuten, dass sie solche Mechanismen nicht kennen.
Konrad Rudolph
2
@ jpmc26: Du bist entsetzt, dass ich eine gültige Option angegeben habe und keine andere Option angegeben habe? Was? Wenn Sie der Meinung sind, dass es wichtig ist, PostGIS hinzuzufügen, fügen Sie die Antwort selbst hinzu (was Sie getan haben), und kritisieren Sie andere nicht, weil sie nicht die gleiche Idee wie Sie haben.
Flater
3
Ihre Antwort erscheint mir im Grunde genommen nur als Verkaufsargument für MS SQL. Ihre Kommentare deuten darauf hin, dass sie Datenbanken auf etwas umstellen , das Zehntausende von Dollar kosten würde, ohne tatsächlich nachzufragen, was ihre Situation nur dazu führt, dass es mehr aussieht. Es wird nicht einmal beschrieben, wie das OP seine Abfrage tatsächlich implementieren kann, und es wird nicht beschrieben, dass dies und die Verwendung des räumlichen Index in MS SQL nicht so einfach ist wie in anderen DBs. Es wird auch keines der zugrunde liegenden Konzepte erörtert. Es ist eine schlechte Antwort, unabhängig davon, ob sie "gültig" ist. Deshalb stört es mich.
jpmc26
29

Verwenden Sie eine Datenbank mit Unterstützung für GIS- Abfragen (Geoinformationssysteme) . Die meisten Datenbanken unterstützen dies direkt oder haben Erweiterungen, aber die Details sind datenbankspezifisch (in ihrer Antwort) zeigt Flater die Syntax für SQL Server).

Wenn Sie solche Abfragen in Ihrer Anwendung implementieren müssen, können Sie eine Datenstruktur implementieren, die räumliche Abfragen ermöglicht, z . B. einen kd-Baum . Dies ähnelt einem binären Suchbaum, mit der Ausnahme, dass jede Ebene der Baumpartitionen auf einer anderen Koordinatendimension liegt. Auf diese Weise können Sie die Suche auf eine kleinere Anzahl möglicher Kandidaten beschränken. Tatsächlich übersetzen Sie Ihre Suche "10 km Radius" in Grenzen für jede Koordinatendimension und ziehen die Grenzen fester, wenn Sie in den Baum zurückkehren.

amon
quelle
5
Es gibt auch einen GIS-Stapelaustausch
BlueRaja - Danny Pflughoeft
8
PostGIS ist die erste kostenlose Option. Es unterstützt weit mehr als die grundlegenden GIS-Typen und -Funktionen von SQL Server. Dies ist jedoch die Grundfunktionalität.
jpmc26
@amon Ich finde den Kommentar von jpmc26 als eine gute Ergänzung und nicht so sehr als Kritik an deinem Beispiel. "Wenn Sie von vorne anfangen möchten, müssen Sie für eine lizenzierte Datenbank nichts bezahlen - diese kostenlose Open-Source-Datenbank macht den Trick auch wirklich gut."
Margarciaisaia
11

Ja, es gibt einen besseren Weg. Sie müssen einen räumlichen Index verwenden . Diese Indizes organisieren Metadaten zu Geometrien, um weit entfernte Geometrien sehr schnell herauszufiltern. Dadurch werden viele CPU-Zyklen gespart, indem die von Ihnen beschriebenen Berechnungen vermieden werden. Sie sollten sich nicht die Mühe machen, eine selbst zu implementieren, da alle wichtigen relationalen Datenbanken einen räumlichen Geometrietyp und dazugehörige Indizes bereitstellen.

Was Sie untersuchen möchten, sind Abfragen "innerhalb der Entfernung" (Abfragen für Geometrien innerhalb einer bestimmten Entfernung von einer anderen Geometrie). Dies sind sehr standardmäßige und weitgehend gelöste Probleme, die in allen oben genannten Datenbanken (und in mehreren integriert) möglich sind:

  • PostGIS: ST_DWithin
  • SQL Server: STDistance(Es ist nicht klar, ob die Indexverwendung in der 3D-Geografie-Version dieser Funktion unterstützt wird.)
  • Oracle: SDO_WITHIN_DISTANCE(Dies bedeutet nicht explizit, dass die Verwendung des Index ausgelöst wird. Ich würde den Abfrageplan noch einmal überprüfen. Möglicherweise müssen Sie einen anwenden SDO_FILTER, damit er den Index verwendet.)
  • MySQL: Ich finde das immer noch heraus.

Problemumgehung zum Auslösen der Indexverwendung

Im schlimmsten Fall, wenn Sie Probleme haben, das System dazu zu bringen, den räumlichen Index mit diesen Abfragen zu verwenden, können Sie einen zusätzlichen Filter hinzufügen. Sie erstellen einen quadratischen Begrenzungsrahmen mit Seiten der Länge 2 * (Suchabstand), der an Ihrem Suchpunkt zentriert ist, und vergleichen die Begrenzungsrahmen der Tabellengeometrien damit , bevor Sie den tatsächlichen Abstand überprüfen. Das macht PostGIS ' ST_DWithinoben sowieso intern.


Entfernung in GIS

Während räumliche Indizes fantastisch und absolut die richtige Lösung für Ihr Problem sind, kann die Entfernungsberechnung logisch kompliziert werden. Insbesondere müssen Sie sich Gedanken darüber machen, in welcher Projektion (im Grunde alle Parameter für das Koordinatensystem) Ihre Daten gespeichert sind. Die meisten 2D-Projektionen (andere als Winkelkoordinatensysteme wie die verschiedenen Lat / Long-Projektionen) verzerren die Länge erheblich. Beispielsweise erweitert die Web Mercator-Projektion (die von Google, Bing und allen anderen großen Anbietern von Basiskarten verwendet wird) Bereiche und Entfernungen zunehmend, je weiter der Standort vom Äquator entfernt ist . Ich kann mich irren, da ich nicht offiziell in GIS ausgebildet bin, aber das Beste, was ich für 2D-Projektionen gesehen habe, sind einige spezifische, die korrekte Abstände von a versprecheneinzelner, konstanter Punkt in der ganzen Welt. (Nein, es ist nicht praktisch, für jede Abfrage eine andere Projektion zu verwenden. Dadurch werden Ihre Indizes unbrauchbar.)

Die Quintessenz ist, dass Sie sicherstellen müssen, dass Ihre Mathematik korrekt ist. Aus Sicht der Entwicklung ist dies am einfachsten, wenn Sie Winkelprojektionen (diese werden häufig als "geografisch" bezeichnet) und Funktionen verwenden, die das Berechnen mit einem Sphäroidmodell unterstützen. Diese Berechnungen sind jedoch etwas teurer als die 2D-Berechnungen und einige DBs unterstützen die Indizierung möglicherweise nicht. Wenn Sie mit ihnen jedoch eine akzeptable Leistung erzielen können, ist dies wahrscheinlich der richtige Weg. Eine weitere häufig verwendete Option sind regionale Projektionen (wie UTM-Zonen), mit denen Entfernungen und Bereiche nahezu korrigiert werden, wenn Ihre Daten auf einen bestimmten Teil der Welt beschränkt sind. Was für Ihre App am besten ist, hängt von Ihren spezifischen Anforderungen ab.

Dies gilt auch dann, wenn Sie keine integrierten räumlichen Indizes verwenden. Ihre Daten haben eine gewisse Projektion, unabhängig davon, welche Technologie oder Technik Sie derzeit verwenden oder in Zukunft verwenden. Sie wirken sich bereits auf alle Abfragen und Berechnungen aus, die Sie durchführen.

jpmc26
quelle
3

Ich würde zustimmen, dass die Verwendung von spezifischem Support in einer Datenbank, wenn möglich, der sinnvollste Weg ist, dies zu tun.

Wenn ich dies jedoch in einer Datenbank ohne spezielle Unterstützung tun müsste, würde ich zunächst nach einem Quadrat suchen, das den Zirkel einschließt, z. B. (y> (y1 - rad)) AND (y <(y1 + rad)) AND (x> ( x1 - rad)) AND (x <(x1 + rad)). Unter der Annahme, dass Ihre Punkte ungefähr gleichmäßig verteilt sind und Sie nach einem Quadrat suchen, erhalten Sie Ihre wahren Übereinstimmungen plus etwa 30% zusätzliche falsche Übereinstimmungen. Sie können dann die falschen Übereinstimmungen löschen.

Peter Green
quelle
Ohne einen geeigneten räumlichen Index durchsucht eine solche Abfrage jedoch im schlimmsten Fall die gesamte Datenbank, allenfalls alle Elemente innerhalb des angegebenen Längen- oder Breitengradbereichs, abhängig von Ihrem Index, dh ein "Band" anstelle eines Quadrats. Wenn Sie die Leistung nicht beeinträchtigen möchten, verwenden Sie eine Datenbank, die räumliche Indizes unterstützt!
Jcaron
Ich glaube, diese Abfrage könnte mit einem normalen B-Tree-Index für xund optimiert werden y. (Vielleicht kombiniert, vielleicht getrennt. Ich möchte ein wenig herausfinden, was in der Praxis besser funktioniert.)
jpmc26
@ jpmc26 Nein, das geht nicht. Überleg es dir, du wirst sehen.
Jcaron
@jcaron Vielleicht wäre es besser, wenn du etwas nicht kryptisch finden würdest, was eindeutig nicht einfach ist. B-Bäume können für BETWEENAbfragen verwendet werden. Ich verstehe nicht, warum Sie im schlimmsten Fall nicht zwei Indizes haben konnten und die gefilterten Ergebnisse aus jedem Index dann zusammengeführt werden. (Dies tun RDBMS intern, wenn sie die Verwendung mehrerer Indizes für sinnvoll erachten.) Wenn ein kombinierter Index funktioniert, sollte er eine Dimension auf der ersten Ebene vollständig herausfiltern und auf der zweiten Ebene relativ schnell eingrenzen.
jpmc26
2
@ jcaron tatsächlich können Sie Index für etwas verwenden, y between -68 and -69 and x between 10 and 11aber natürlich räumliche Index einen besseren Job für diese Aufgabe
Juan Carlos Oropeza