Umkreis um eine Koordinate berechnen und alle Koordinaten in DB suchen

[dwex]

Hallo Leute,

ich habe wieder mal ein SUPER-ergeiziges Projekt.

Also ich habe hier eine SQL-Tabelle in der stehen alle Postleitzahlen von Deutschland/Österreich/Schweiz und die dazugehörigen Koordinaten - also für München z.B. 11° 58' 33'' Östlicher Länge und 45° 15' 00'' Nördlicher Breite das Ganze steht in der DB im Format 11.5833 45.15.00 und eben die PLZ dazu.

So jetzt würde ich gerne eine Umgebungsberechnung machen.
Und zwar habe ich ca. 800 Personen ebenfalls in der DB (mit PLZ) jetzt möchte ich z.b. in einem Umkreis von 30 Km die nächsten 10 Personen anzeigen lassen.

Ich weiss jetzt das ich da eine Kreisberechnung brauche usw. aber leider keinen blassen Schimmer wie ich das in PHP oder überhaupt (auch nicht mal auf dem Papier) anstellen kann.

Als kleines Beispiel könntet Ihr mal die Beratunsstellensuche von http://www.altbayerischer.de nutzen dann wisst Ihr was ich machen möchte.

Vielen Dank im Voraus

 

[Mamphil]

Info (30.08.2008):
Inzwischen habe ich den unten stehenden Algorithmus überarbeitet, ein kleines Tutorial und eine fertige PHP-Klasse darauf gemacht:
http://www.mamat-online.de/umkreissuche/opengeodb.php

_______________________________________

Hallo!

Zuerst musst du die Koordinaten im Kugelkoordinatensystem (Grad-Breite / -Länge) ins kathesische Koordinatensystem umwandeln:

const
  Erdradius = 6371000;

// Umwandlung der Kugel-Koordinaten ins kathesische Koordinatensystem:
// Umrechnung ins Bogenmaß
lambda := geoLaenge * PI / 180;
phi    := geoBreite * PI / 180;

geoKoordX := Round(Erdradius * cos(phi) * cos(lambda));
geoKoordY := Round(Erdradius * cos(phi) * sin(lambda));
geoKoordZ := Round(Erdradius * sin(phi));

Wichtig: das ist Pascal / Delphi-Code. In PHP sollte das aber vom Prinzip her genauso und von den Befehlen her ähnlich aussehen...

Und dann kannst du die Entfernungen berechnen:

    // Umrechnung von Meter in Kilometer
    // Bei der Berechnung in Metern werden die Zahlen zu groß,
    // die Berechnung mit Floats ist allerdings kein Problem...

    rd := mysql_fetch_row(re);
    x1 := geoKoordX / 1000;
    y1 := geoKoordY / 1000;
    z1 := geoKoordZ / 1000;
    x2 := geoKoordX2 / 1000;
    y2 := geoKoordY2 / 1000;
    z2 := geoKoordZ2 / 1000;

    Entfernung := Round(
                  2 * ErdradiusKm *
                    arcsin(
                      sqrt(
                          sqr(x1 - x2)
                        + sqr(y1 - y2)
                        + sqr(z1 - z2)
                      ) / (2 * ErdradiusKm)
                    )
                  * 1000
                  );

Noch Fragen?

Mamphil

 

[dwex]

Hallo erstmal,

ich bin jetzt ziemlich fertig mit der Welt - das muss ich erst mal auf mich wirken lassen.
Bist du Mathematikprofessor?

Ich werde das mal, wenn es sich etwas "gesetzt" hat, ausprobieren - ich hoffe das klappt

Vielen Dank erstmal.

 

[Mamphil]

Hallo!

ich bin jetzt ziemlich fertig mit der Welt - das muss ich erst mal auf mich wirken lassen.
Bist du Mathematikprofessor?

Nein, dazu muss ich erst einmal mein Mathematikstudium hinter mich bringen.

Ein wenig Erklärung:
Die Erde stellen wir uns als Kugel vor. Diese legen wir in ein dreidimensionales Koordinatensystem, der Kugelmittelpunkt liegt im Ursprung. Von hier aus werden die Winkel abgemessen. Mit den entsprechenden trigonometrischen Funktionen kriegt man aus den Winkeln (wie oben dargestellt) die kathesischen Koordinaten (x/y/z).

Für die Abstandsberechnung gehen wir davon aus, dass wir auf der idealen Kugel von einem Punkt zum nächsten Laufen. Wir betrachten das Dreieck Punkt1-Punkt2-Erdmittelpunkt.
Die Entfernung der Punkte zum Erdmittelpunkt ist gleich - die Entfernung der beiden Punkte lässt sich anhand der Koordinaten mit dem Satz des Pythagoras bestimmen.
Wenn wir die drei Seitenlängen haben, können wir den Winkel am "Erdmittelpunkt" berechnen. Das machen wir mit Hilfe des arcsin an einem rechtwinkligen Dreieck (das gleichschenklige Dreieck einmal geteilt). Der wird verdoppelt...

Wenn dieser Winkel 360° wäre, würden wir einmal um die ganze Erde laufen: Die Entfernung entspricht dem Umfang der Erde (U = 2*PI*r). Wir laufen aber nur den "Winkel"/360°'sten Teil auf der Erde....

Naja, auf alle Fälle steckt das alles in der Formel

Mamphil

 

[Dr Gonzzo]

Hallo zusammen,

kann es sein, dass Ihr etwas aneinander vorbeipostet? Wenn ich dwex richtig verstanden habe, will er nicht den Abstand zwischen zwei Punkten berechnen sondern die Teilmenge der Datensätze, die innerhalb des Radius liegen ausgeben.

Ich stehe z.Z. gerade vor dem gleichen Problem bzw. Herausforderung.
Der Ansatz ist sicher der erste Schritt in die richtige Richtung, aber so weit war ich schon. Wird auch auf http://www.koordinaten.de/online/formel.shtml noch mal an Beispieldaten erklärt.

Wenn ich jeden Datensatz (sind ca 18.000) einzeln auf seinen Abstand zum Ursprung überprüfen würde wäre das doch ziemlich umständlich und ineffektiv. Es muss doch einen vernünftigen Algorithmus für das Problem geben.

thx schon mal im Voraus

 

[Mamphil]

Naja, die Formeln müssen halt umgestellt werden. Eine Umkreissuche kann z. B. so aussehen:

SELECT * FROM abc WHERE (2 * ErdradiusKm *
                    arcsin(
                      sqrt(
                          sqr(12345 - x2)
                        + sqr(9876 - y2)
                        + sqr(33 - z2)
                      ) / (2 * ErdradiusKm)
                    )
                  * 1000) < 5000

Mamphil

 

[dwex]

Hallo,

@dr gonzo
Hättest du interesse an einem gemeinsamen Projekt - ich bin leider nicht so fit in Mathe.

 

[Dr Gonzzo]

Hi Leutz,

@dwex
Bin gestern Abend mit meiner Umkreissuche fertig geworden Aber ich helf dir trotzdem gerne weiter, denn ein bissel Mathematikverständnis ist bei dem Thema schon angebracht.

Als Parameter werden ja der Ort als Mittelpunkt sowie der gewünschte Suchradius s übergeben.
Stell dir nun die Erde als Kugel oder der Einfachheit halber mal als Kreis und unseren Ort als Punkt auf dem Kreisbogen vor.
Diese Kugel hat nun einen Radius R von ~6378,137 km. Der Umfang ergibt sich logischerweise aus

U =2*R*Pi  (~40.000 km)

d.h. (Werte gerundet!)
360° = 40000 km
1° (Grad) = 111 km
1'  (Minute)= 1°/60 = 1.85 km
1'' (Sekunde)= 1'/60 = 1°/3600 = 30 m

(ich denke das ist auch für Leute, die nich so stark in Mathe sind noch nachvollziehbar )
Wenn du nun von deinem Ursprungspunkt die Strecke s auf dem Kreisbogen "abläuft" erhältst du einen zweiten Punkt auf dem Kreis. Nun kannst du den Winkel zwischen den beiden Punkten berechnen:

alpha = 180*s/(R*Pi)

Mit diesem Winkel kannst du nun eine Vorauswahl deiner Daten Treffen

select *
from  tabelle
where 
 geoBreite >= ursprungsBreite-alpha &
 geoBreite <= ursprungsBreite+alpha &
 geoLänge >= ursprungsBreite-alpha &
 geoLänge <= ursprungsBreite+alpha

Damit hast du quasi ein Quadrat mit der Seitenlänge 2s und unserem Ort als Mittelpunkt auf die Erdkugel gelegt und untersuchen weiterhin nur noch die Orte in diesem Bereich. Dieser Schritt ist theoretisch nicht nötig, aber aus Performance Gründen auf jeden Fall zu empfehlen (ich gehe davon aus, dass du ebenfalls die OpenGeoDB nutzt und die hat ~18.000 Einträge). Ich habe es mal Spaßeshalber mit und ohne Vorselektion laufen lassen un das Testergebnis spricht für sich...
Mit Vorselektion: ~7 Sek
Ohne Vorselektion: >3.5 Min

Nun musst du die L/B-Grade der Orte in kartesische Koordinaten(XYZ) umrechnen aus denen du dann den Verbindungsvektor(Abstand) ermitteln kannst, aber das hat Mamphil ja schon ganz schön ausgeführt. Wenn du die Koordinaten hast ist der Abstand nix anderes wie der Satz des Pythagoras nur halt in 3D.

2D:  sqr(a) + sqr(b) = sqr(c)
3D:  sqr(a) + sqr(b) + sqr(c) = sqr(d) [d = Entfernung]

Der Abstand muss natürlich <= dem Suchradius sein. Dadurch wird aus unserer "Umquadratsuche" eine "Umkreissuche"
Schau auch mal auf Wikipedia. Hat mir sehr beim Verstehen der Zusammenhänge geholfen.
Deine Suchergebnisse kannst du auf http://www.ebaas.de/ebaas-distance-test validieren.
So, ich hoffe, dass ich dir jetzt weiterhelfen konnte und wünsch dir weiterhin viel Erfolg mit deinem Projekt. Kannst ja nochmal Posten, wenn es nicht so klappt wie's soll...

Bis denne euer
Dr. Gonzzo

 

[dwex]

Hallo Gonzzo,

ich habe mal teile deiner Ausführungen - soweit ich auf Anhieb folgen konnte nachgestellt und folgenden Code gebaut:

$ursprungsbreite = 48.45;
$ursprungslaenge = 12.35;

$alpha = 180*20/(6371*3.14);

$geo1 = $ursprungsbreite-$alpha;
$geo2 = $ursprungsbreite+$alpha;
$geo3 = $ursprungslaenge-$alpha;
$geo4 = $ursprungslaenge+$alpha;


echo $geo1."<br>";
echo $geo2."<br>";
echo $geo3."<br>";
echo $geo4."<br>";


$abfrage = mysql_query("SELECT * FROM `$tabelle` WHERE breite >= '$geo1' AND breite <= '$geo2' AND laenge >= '$geo3' AND laenge <= '$geo4'");

while($ds = mysql_fetch_assoc($abfrage)) {
echo $ds['name_int']."<br>";
}

Es geht mir jetzt zum ersten um $alpha - meine Frage:
Ist das so Richtig was ich schreibe wenn ich im Umkreis von 20km suchen möchte?

Zum Zweiten:
Das mit dem Koordinatensystem habe ich noch nicht überissen - könntest du mir es nochmals erklären anhand meines Codes oben.

Wäre nett wenn Ihr/Du mir die Fragen beantworten könntest.

 

[Dr Gonzzo]

Hi dwex,

sieht doch ganz gut aus wobei ich nix über die Syntax sagen kann, da ich kein PHP behersche. Ich habe alles in SQL gemacht. Du solltest vielleicht

6378137/1000*3,14159 (=20037,49)
statt
6371*3,14 (=20004,94)

verwenden,wegen der Genauigkeit

Mit dem bisherigen Code erhältst du halt auch noch Treffer in den Ecken des Quadrats, (können bis zum Faktor 1,41 also 40% außerhalb deines Radius liegen). Deshalb habe ich wie gesagt diese Ergebnistabelle zwischengespeichert und dann die Distanzüberprüfung drübergejubelt.

Ich hoffe ich konnte dir die Zusammenhänge ein bischen näher bringen. Grade der Wiki-Artikel ist echt gut. Ich hab diese Woche jedenfalls reichlic neues über Navigation gelernt

Viel Erfolg noch weiterhin.

Dr. Gonzzo