# Umkreis um eine Koordinate berechnen und alle Koordinaten in DB suchen



## dwex (17. August 2005)

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 (18. August 2005)

*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 (18. August 2005)

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 (18. August 2005)

Hallo!


			
				dwex hat gesagt.:
			
		

> 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 (7. September 2005)

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 (7. September 2005)

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 (7. September 2005)

Hallo,

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


----------



## Dr Gonzzo (9. September 2005)

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 (9. September 2005)

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 (9. September 2005)

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


----------



## dwex (9. September 2005)

Hallo Gonzzo,

ja aber an der Distanzüberprüfung scheitert es noch das habe ich nicht kapiert wie ich das machen soll - ausserdem soll ich ja dann jeweils den nächsten Ort ausgeben.

Wäre echt nett von dir wenn du mir das nochmals (für Doofe  :suspekt: ) erklären würdest.

Also im Konkreten möchte ich einfach mal von folgenden Gegebenheiten ausgehen.

Ort 1 = Breite 48.45 und Länge 12.35
Ort 2 = Breite 48.3667 und Länge 12.25

Wie errechne ich jetzt die Entfernung in Km - ich weis das das irgendwie mit cos und sin und evtl. acos funktioniert aber wie ist bisher nicht zu mir durchgedrungen.

Ausserdem habe ich mir jetzt mal was gebastelt:

```
$ursprungsbreite = 48.45;
$ursprungslaenge = 12.35;
$ursprungsbreite1 = 48.3667;
$ursprungslaenge1 = 12.25;

$e = (($ursprungsbreite1-$ursprungsbreite)+($ursprungslaenge-$ursprungslaenge1))*1000;
```
 könnte es sein, das ich jetzt die Entfernung in Km bekomme? Nur eine (wahrscheinlich dumme) Vermutung. Das würde nämlich genau passen. Wenn ich das aber mit einer Koordinate weiter weg mache wo ich auch die ungefähren Km weiss klappt es nicht - also ist meine Vermutung nicht richtig


----------



## dwex (10. September 2005)

Hallo Leute,

ich bin jetzt selber auf die Lösung gekommen.
Nach ein bischen suchen und graue Zellen anstrengen.

Hier der Code wie ich es momentan gelöst habe:

```
@mysql_connect(MYSQL_HOST, MYSQL_USER, MYSQL_PASS) OR die("Keine Verbindung zur Datenbank.<br>Fehlermeldung: ".mysql_error());
@mysql_select_db(MYSQL_DATABASE) OR die("Konnte Datenbank nicht benutzen.<br>Fehlermeldung: ".mysql_error());

// Koordinaten des Ortes
$ort = "Velden";
$ursprungsbreite = 48.3667;
$ursprungslaenge = 12.25;

$entf = 40; // max. Km-Entfernung von Startort
echo "Folgende grössere Orte liegen im Radius von $entf km um $ort:<br><br>";

$alpha = 180*$entf/(6378137/1000*3.14159);

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


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


$a = $ursprungsbreite/180*3.14159;
$b = $ursprungslaenge/180*3.14159;

$z = 1;

while($ds = mysql_fetch_assoc($abfrage)) {

$c = $ds['breite'];
$d = $ds['laenge'];
$c = $c/180*3.14159;
$d = $d/180*3.14159;

$e = sin($a)*sin($c);
$f = cos($a)*cos($c)*cos($d-$b);
$g = acos($e + $f);
$h = $g * 6378.137;
$ausgabe = sprintf("%01.2f", $h);
if($ausgabe > $entf) {
		continue;
	}
$ausgabe = str_replace(".", ",", $ausgabe);

echo "$z - Nach ".$ds['name_int']." sind es $ausgabe km.<br>";
$z++;
}
```


----------



## Dr Gonzzo (11. September 2005)

Hi dwex,

Glückwunsch, war doch eigentlich garnet so schwer, oder? Aber am Anfang stan dich auch erst mal so da  . Hatte gestern leider keine Zeit mehr zum posten.
Hast du die Formel von www.koordinaten.de ?
Ich habe die Entfernungsberechnung wie gesagt über ein kartesisches Koordinatensystem durchgeführt, wie es mamphil vorgeschlagen hat, aber ich werd es auch noch mit dieser Funktion probieren, weil ich mit der Laufzeit bei großen Umkreisen noch etwas unzufrieden bin und ich stark annehme, dass die andere Lösung weniger rechenintensiv ist.
Ich werd dich auf dem Laufenden halten. 
Viel Erfolg weiterhin.

MfG
Dr Gonzzo


----------



## Dr Gonzzo (12. September 2005)

Hi dwex,

hab die Algorithmen jetzt mal gegeneinander getestet und war erst mal  :suspekt:
Ich habe wie gesagt schon vermutet, dass die direkte Abstandsberechnung schneller ist als der Umweg über die kartesischen Koordinaten, aber das Ergebnis ist schon   



> a1(50) = 7 sec
> a2(50) = 0 sec
> a1(100) = 25 sec
> a2(100) = 0 sec
> ...


Tja, ich glaub' ich muss nicht mehr dazu sagen, welche der beiden Lösungen ich jetzt verwenden werde... 

Bis denne
Dr. Gonzzo


----------



## dwex (12. September 2005)

Holla,

dann ist ja meine Lösung SUPER!

Was ich aber noch nicht kapiert habe ist das mit dem Viereck und dem Kreis um die Startkoordinate - momentan rechne ich ja das Viereck aus und nicht den Kreis.
Ausserdem ist mir aufgefallen, dass wenn ein Ort sagen wir mal er ist 31,7 km entfernt nicht aus der db gelesen wird wenn ich nach 35 km Umkreis suche. Wenn ich aber dann 40 km eingeben dann wird er gefunden. wenn ich dann über die einzelnen Koordinaten dann die Entfernungen ausrechne dann wird eben 31,7 km angezeigt.

Ich hoffe, dass war verständlich genug - wer hat eine Idee?


----------



## Dr Gonzzo (12. September 2005)

Hi dwex,

Kann das Problem nicht ganz nachvollziehen. Deine Abstandsberechnung sollte ja Stimmen, nehme ich jetzt mal an. Wenn er den Ort dann trotzdem nicht Anzeigt muss es demnach an deinem Vergleichsoperator liegen. 
Was bewirkt der Befehl?
	
	
	



```
$ausgabe = sprintf("%01.2f", $h);
```
. 
$ausgabe ist ja deine Entfernung wenn ich recht verstehe. Damit müsste deine Abfrage 
	
	
	



```
$ausgabe <= $entf
```
 heißen und nicht 
	
	
	



```
$ausgabe > $entf
```
Genau diese if- Abfrage macht aus deinem Quadrat einen Kreis (Bildlich gesehen).
Def. Kreis: Menge Aller Punkte, die genau den gleichen Abstand  von einem gemeinsamen Ursprungspunkt besitzen.
Def. Scheibe: Menge Aller Punkte, die maximal den gleichen oder einen geringeren Abstand von einem gemeinsamen Ursprungspunkt besitzen.


$ausgabe = $entf (Kreis)
Alle Punkte, die genau den gewünschten Abstand vom Ursprung haben. Liegen genau auf einem Kreisbogen um den Ursprung 
$ausgabe < $entf (Scheibe)
Alle Punkte innerhalb  dieses Kreisbogens
$ausgabe > $entf (Quadrat mit ausgeschnittenem Innenkreis - die vier Ecken)
Alle Punkte außerhalb  dieses Kreisbogens

Schau dir deinen Code nochmal an. Liegt bestimmt an so ner Kleinigkeit

Dr. Gonzzo


----------



## Dr Gonzzo (13. September 2005)

Hi dwex,

ok, kann das Problem jetzt doch nachvollziehen. Ist bei mir ähnlich, habe es nur noch nicht bemerkt. Das Problem liegt meiner Meinung nach bei der Vorselektion, bzw. daran, dass es 180 Breitengrade und 360 Längengrade gibt. Probier mal

```
$geo1 = $ursprungsbreite-$alpha; 
$geo2 = $ursprungsbreite+$alpha; 
$geo3 = $ursprungslaenge-2*$alpha; 
$geo4 = $ursprungslaenge+2*$alpha;
```
Hat in meinem Fall geklappt

mfG
Dr. Gonzzo


----------



## dwex (13. September 2005)

Hi Gonnzo,

nein leider habe ich jetzt noch größere Ungenauigkeiten als vorher. Jetzt werden mir Orte welche über 50Km entfernt sind angezeigt. Das ganze habe ich mit einem Radius von 35Km probiert.

Edit: Zu deiner Frage was das sprintf mach - es kürzt mir meine Flieskommazahl (bei der Entfernungsberechnung) auf 2 Stellen hinter dem Komma.


----------



## Dr Gonzzo (13. September 2005)

Servus

Hääh, moment mal, von Ungenauigkeiten hast du bisher nichts geschrieben, sondern nur, dass dir Einträge bei der Abfrage "verloren" gehen. Meinst du mit ungenauigkeiten falsch berechnete Abstandswerte oder zu wenige/zu viele Treffer  
Durch die erweiterung der Vorselektion solltest das andere Problem eigentlich machbar sein (hat bei mir zumindest geklappt)
Du hast doch nur bei den Längengraden den doppelten Winkel addiert bzw. subtrahiert. Nicht bei den Breitengraden 
("Ok, im Prinzip ist es natürlich egal(s.u.), du könntest auch beides mit einem beliebigen Faktor multiplizieren um Sicherzustellen, dass deine Vorauswahl(die man ja wie gesagt nicht mal zwingend braucht) nicht zu eng ist").
Aber bei den Längengraden muss es sein, wenn meine Überlegungen nicht völliger Schwachsinn waren   
Dadurch wird deine Vorselektion natürlich etwas größer (bei 35km Umkreis können durchaus Orte mit 50 km noch in der Vorauswahl vorkommen), die werden ja aber dann wieder durch deine Abstandsberechnung aussortiert.

Hoffe, es klappt
Dr. Gonzzo


----------



## dwex (13. September 2005)

Hallo,

ja das ist schon Richtig und die werden dann auch über die Abstandsberechnung aussortiert - nur kommt mir das doch sehr Spanisch vor - ich habe ein bischen getestet und festgestellt, dass wenn ich die Berechnung des Umkreises (also den KM-Wert - im Beispiel 35km) mit 1,45 Multipliziere dann klappt das


----------



## Dr Gonzzo (13. September 2005)

Noch mal langsam: Du multiplizierst deinen Suchradius (35km) mit 1,45? Und dann? Was machst du mit dem Wert? Was klappt dann?   
Sorry, aber du musst dich ein bischen konkreter ausdrücken...


----------



## dwex (13. September 2005)

Hallo nochmal,

ich habe das ganze jetzt mal mit meinem Atlas getestet und einfach mal um einen Ort einen 30Km-Radius mit dem Zirkel gezogen.
Jetzt habe ich folgendes festgestellt:

1. Wenn ich nach meiner "alten" Berechnung rechne dann habe ich eine Eiform - das heisst nach Norden und Süden habe ich in jede Richtung je 30km Ausdehnung und nach Ost und West weniger (wieviel kann ich nicht genau sagen).
2. Wenn ich jetzt nach der "neuen" Berechnung rechne dann bekommt mein Kreis auch eine Eiform aber diesesmal genau umgekehrt. Jetzt habe ich zwar immer noch 30Km nach Norden und nach Süden - nach Osten und Westen habe ich jedoch jetzt knapp über 50km ausdehnung.

Das kann kann doch der Weisheit letzter Schluss noch nicht sein - ODER?


----------



## dwex (13. September 2005)

Und nochmal - habe deinen Post von 14.03 erst jetzt gesehen.

Ja ich multipliziere die Entfernung mit 1,45 und rechne dann mit diesem "fehlerkorrigierten" Wert weiter. Die 1,45 habe ich mir zu recht getestet 

Hier der entsprechende Quelltextabschnitt:
	
	
	



```
$entf = 35; // max. Km-Entfernung von Startort
$fehlerquote = 1.45; // Ausgleich der Fehlerqoute in der Berechnung
echo "Folgende grössere Orte liegen im Radius von $entf km um $ort:<br><br>";

$alpha = 180*$entf*$fehlerquote/(6378137/1000*3.14159);
```


----------



## dwex (13. September 2005)

So ich habe mir jetzt mal die Arbeit gemacht, um einen Ort einen 20km-Radius zu ziehen und alle Orte mir dann auf eine Karte zu legen.
Ich habe dabei die Berechnung mit 180° auf der Breíte und 360° auf der Länge genommen.
Siehe da es ist genauso wie ich es befürchtet habe.
Es gibt einen breiteren Radius nach West und Ost - die Nord/Süd-Ausrichtung stimmt auffallend. Das Bild unter http://www.dwex.de/wartenberg-20km.jpg hat Nordausrichtung.
Der blaue Punkt ist der Ausgangsort und der rote Kreis wäre dann der 20km-Radius - die roten Punkte sind die gefundenen Orte

Was sagst du dazu?


----------



## Dr Gonzzo (13. September 2005)

Hossa,

was nicht passt wird passend gemacht, oder   

Wie gesagt, die längen und breitengrad Skala ist unterschiedlich, was dazu führt, dass du ein Rechteck statt einem Quadrat erhältst. 
Mit deinem Faktor 1.45 machst du das Ding einfach größer, wie ich schon geschrieben habe. 
Eine Elipse (auch liebevoll "Ei" genannt   )  würdest du  jedoch nur erhalten, wenn du deine Abstandsberechnung mit variablem, periodisch veränderndem Abstand durchführen würdest. Nehm ich aber mal nicht an  . Was du eher hast ist ein Kreis, an dem man links und rechts bzw. oben und unten einen Kreisabschnitt entfernt hat. Das passiert, wenn der Umkreisdurchmesser größer ist, als die kurze Seite deines Rechtecks (eigentlich sollten sie ja identisch sein)
Tja, der Fehlerteufel steckt halt doch immer im Detail...

Good Luck
Dr. Gonzzo


----------



## dwex (13. September 2005)

Hallo,

schau dir bitte mal meinen Kreis nochmal an - da ist nichts entfernt - da ist vielmehr was zuviel


----------



## Dr Gonzzo (13. September 2005)

Hi dwex,

ok, also fals du die "Fehlerquote" bei der Abstandsberechnung mit einbeziehst kriegst du natürlich dadurch auch mehr Treffer. Anderst kann ich mir das ja fast nicht erklären  
Kannst du vielleicht nochmal deinen gesamten Code posten, dann fällt es mir leichter den Fehler zu suchen. Wie gesagt, bei mir läuft es mit dem gleichen Prinzip sehr zufriedenstellend, was mich annehmen lässt, dass bei deiner Implementierung was nicht stimmt.
Wäre doch gelacht, wenn wir das nicht hinkriegen, oder?

Bis dann
Dr.Gonzzo


----------



## papole (13. November 2005)

Hallo, ich möchte dieses Thema nochmal aufgreifen, weil mir einiges noch nicht klar ist.

Es geht hier zwar hauptsächlich um die Umkreissuche von Städten, doch wollte ich wegen meiner Frage kein neues Thema aufmachen: Ich habe eine Deutschlandkarte (auch die von OpenGeoDb) und wollte nun die Punkte der Städte auf die Karte eintragen.

Ich habe die Polarkoordinaten und die Breiten- sowie Längengrade der Städte. Wie bekomm ich das nun auf die Karte. Wenn ich die Erde als Kugel missachte und linear die Koordinaten auf Deutschland zeichnen lasse, ist es je weiter ich nach Süden und/oder Osten gehe immer ungenauer.

Kann mir einer helfen?

Danke im Vorraus


----------



## Torsten_E (23. Januar 2007)

Ja ich weis, ist über ein Jahr her dieses Thema, aber ich stehe vor dem gleichen Problem.
Ort in 15 km Entfernung werden bei einer 20 km-Radius Suche nicht mit einbezogen.
Stelle ich den Radius auf 25-30 km sind die Orte mit 15 km Entfernung ebenfalls enthalten.
Ich habe den hier vorgeschlagenen Fehlerfaktor bisher nicht berücksichtigt.

Mich würde viel mehr interessieren, ob es vielleicht in der Zwischenzeit eine "genauere" Lösung gibt, als mit dem Fehlerfaktor zu arbeiten ?

Grüße

Torsten.E


----------



## Mamphil (23. Januar 2007)

Hi,

welche Daten hast du verwendet? Welches Script bzw. welche Querys hast du verwendet?

Mamphil


----------



## Torsten_E (23. Januar 2007)

http://www.tutorials.de/forum/1148147-post12.html


----------



## Mamphil (8. August 2008)

Hallo,

auch wenn dieser Thread schon recht alt ist, hole ich ihn einmal aus der Versenkung - schließlich gibt es immer wieder _Linkbacks_ dazu...

Inzwischen hat sich die Struktur der OpenGeoDB etwas geändert, deshalb habe ich einen kleinen Artikel / Tutorial dazu geschrieben. Dieser ist unter http://www.mamat-online.de/umkreissuche/opengeodb.php zu finden. 

Über Feedback würde ich mich sehr freuen. Viel Spaß


----------



## versuch13 (11. August 2008)

Mathematisch ist mir das auf jeden Fall viel zu hoch und ich finde es bewundernswert. Ich wollte mich in nächster Zeit aber auch mal mit dem Thema auseinandersetzen und hoffte darauf eine fertige Lösung zu finden. Daher wird mir diese Thema und dein Beispiel sicher auch weiter helfen, danke.

Bei meiner Recherche habe ich mir eine Google Code FAQ Seite gebookmarked auf der man eine Query findet:


```
SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin( radians( lat ) ) ) ) AS distance 
FROM markers HAVING distance < 25 ORDER BY distance LIMIT 0 , 20;
```

"find the closest 20 locations that are within a radius of 25 miles to the 37, -122 coordinate"
Nur wie kommt man an die Koordinaten (37,122)?
So könnte man einen Umkreis von 25 Meilen abfragen. 
"To search by kilometers instead of miles, replace 3959 with 6371"

Das wirkt auf mich, für mich als Anwender, als super einfach einzusetzen. Jetzt
frage ich mich nur, da eure Lösungen mir nicht so simple erscheinen, ob mit dem 
Beispiel evtl doch was nicht ganz in Ordnung ist (es irgendwelche Nachteile mit sich
bringt usw., das Query wird hier ja nicht an einer kompletten Koordinaten DB durchgeführt).


----------



## Patrick Oberlies (11. August 2008)

```
SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin( radians( lat ) ) ) ) AS distance 
FROM markers HAVING distance < 25 ORDER BY distance LIMIT 0 , 20;
```

Ich würd mal sagen durch die 37 und -122 in dem Query kommt man an die Koordinaten. Wenn man die Zahl 37 und die Zahl -122 ersetzen würde mit anderen Zahlen bekommt man mit Sicherheit den Umkreis von 25 Meilen um diese Koordinate. Man müsste aber beachten das die 37 zweimal in dem Query vorkommt. Also müsste man auch beide ersetzten.


----------



## Chumper (11. August 2008)

Ich habe eine Geosuche auf Basis der Googlemap gebaut.
Dort habe ich die Abfrage des Users an Google geschickt und den vermeintlichen Ort in Geokoordinaten erhalten, aufgrund dieser Informationen habe ich dann den Code benutzt den ich auf http://geokodierung.net/
gefunden habe. Habe ihn noch ein bisschen angepasst, aber das ist dann kein Problem mehr.


----------



## Mamphil (11. August 2008)

Hi,

die Mathematik hinter Google's Vorschlag werde ich mir mal ansehen. Prinzipiell scheint es aber recht ähnlich gelagert zu sein.

Um Werbung für meinen Vorschlag zu machen: die trigonometrischen Funktionen sind recht aufwändig zu berechnen (z. B. über Tabellen) - Subtraktion und Quadrieren (wie in meinem kurzen Artikel) sollte deutlich schneller sein 

Die 37 und -122 werden einfach die Länge und Breite eines Ortes sein (nämlich San Francisco:  37° 47? N, 122° 25? W laut Wikipedia). Im _Rechtssystem_ werden Angaben nach Norden und Osten positiv, nach Süden und Westen mit negativem Vorzeichen betrachtet, daher +37 für 37° N und -122 für 122° W.

Mamphil


----------



## gerirre (23. Juli 2011)

Hallo Zusammen,

Dieses nun mitlerweile sehr alte Thema würde ich auch gerne nochmal hoch holen  
Gibt es mitlerweile eine ideale Lösung? Ich habe auch mit der ersten Formel und einer "Fehlertoleranz" von 1.45 gearbeitet und bekomme so schon sehr akzeptable Werte. Aber eben nicht zu 100% genau :/ 
Ich würde mich freuen wenn jemand nochmals eine Lösung vorstellen könnte.

Viele Grüße
Geri


----------

