Geographischer Umkreis - Distanz

[Splitt3r]

Hallo,

ich habe verschiedene geographische Punkte die ich aus Google Maps ausgelesen habe.

Breitengrad, Längengrad.

Ich habe eine funktion mit der ich die entfernung zwischen zwei geographischen Punkten in km berechnen lasse.



Nun möchte ich aus einer Geographischen-Lage alle geographischen Punkte wissen die in einem umkreis von zb. 100 km liegen.

Das Problem ist dass ich nicht erst meine Ausgangslage mit allen anderen Punkten berechnen will um dann zu sehen welche in der nähe sind. (das sind viel zu viele Punkte).

gibt es eine formel die sagen kann in welchem zahlenbereich die Punkte liegen müssen die um 100 km um den ausgangspunkt liegen?

Danke und viele Grüße

 

[Albu]

Sowas kann man nicht in einer "Formel" abfackeln, was Du also suchst ist keine Formel, sondern ein Algorithmus. Eine Formel wäre sowas wie der Satz von Pythagoras, den Du in Deiner Funktion verwurstet hast.

Die Hauptschwierigkeit bei diesem Problem ist, dass die Berechnung der tatsächlichen Entfernen zwischen zwei Punkten teuer ist. Sie kostet zu viel Rechenzeit, als dass man mal eben alle Punkte mit allen kreuzen könnte.

Ich kenne jetzt zwar vermutlich nicht alle Algorithmen, aber der Hauptansatz dürfte sein, die Anzahl der zu prüfenden Punkte zu reduzieren.

Eine erste Näherung könnte also folgendes darstellen: Um den gesuchten Punkt herum steckst Du einen gedachten, quadratischen Bereich mit 100km Kantenlänge. Nun suchst Du alle Punkte, die in diesem Bereich liegen. Du erhälst eine Liste mit Punkten, die ziemlich nah liegen. Im zweiten Schritt werden diese Punkte einer tatsächlichen Prüfung unterzogen. Dadurch fallen die Punkte raus, die in den "Ecken" des Quadrats lungern.

Um den Rechenaufwand dieser Methode weiter zu reduzieren, bzw. das Auffinden der in Frage kommenden Punkte zu beschleunigen, könntest Du vorab ein Raster mit einer festen Kantenlänge (z.B. 100km) über die komplette Karte legen. Jeder Punkt ist also eindeutig einem Quadrat zuzuordnen. Wenn Du nun den Umkreis eines Punktes berechnen willst, musst Du nicht mehr alle Punkte betrachten, sondern berechnest nur, welche Quadrate in Frage kommen (bei 100km Kantenlänge und 100km Suchradius sind das maximal 9), und Du erhälst eine Liste mit Punkte aus den 9 Quadraten. Diese kannst Du wieder, wie oben beschrieben erst einer quadartischen und dann der exakten Suche unterziehen.

Sicherlich lassen sich noch mehr Optimierungen finden, es hängt auch von der Gesamtanzahl der Punkte ab.

 

[Splitt3r]

puh, das scheint ja ziehmlich kompliziert zu sein.

mir würde es schon reichen wenn ich eine anweisung hätte die alle geographischen daten auflistet die in einem quadrat um meinen punkt von X km liegen.

eine genaue abfrage würde ich hier nichtmal benötigen