Umkreissuche

[Klaus]

Guten Abend,

habt ihr schon einmal eine Umkreissuche programmiert? z.B. ich befinde mich in Köln (50679) und möchte sagen zeig mir alle Daten an, die um Umkreis von 10km sind.

Wie könnte ich das lösen?

Gruß
Klaus

[Jörg Reinholz]

habt ihr schon einmal eine Umkreissuche programmiert?

Ja.

z.B. ich befinde mich in Köln (50679) und möchte sagen zeig mir alle Daten an, die um Umkreis von 10km sind.

Wie könnte ich das lösen?

Du berechnest die Koordinaten des Vierecks(!) in dem die Orte liegen dürfen und gibst aus der Datenbank alle Orte zurück, welche diese Bedingung erfüllen.

Im zweiten Schritt berechnest Du die Entfernung dieser Orte zum Ausgangspunkt und gibst die Orte zurück, die innerhalb des Umkreises liegen.

Aber beachte bitte, dass es Probleme mit Orten gegeben kann, die sich am selben Fluss (siehe Köln -> Rhein), Berg, Schlucht, Ländergrenze, Bahnstrecke oder Autobahn gegenüber liegen - und, weil keine direkte Verbindung existiert, nur über einen großen Umweg erreichbar sind.

Wenn Du das berücksichtigen willst, dann brauchst Du eine große Matrix (Tabelle) mit den Streckenkilometern von jedem Ort zu jedem Ort.

Jörg Reinholz

[suit]

Du berechnest die Koordinaten des Vierecks(!) in dem die Orte liegen dürfen und gibst aus der Datenbank alle Orte zurück, welche diese Bedingung erfüllen.

Im zweiten Schritt berechnest Du die Entfernung dieser Orte zum Ausgangspunkt und gibst die Orte zurück, die innerhalb des Umkreises liegen.

Das muss man ausprobieren, ob eine näherung mit einer Bounding-Box schneller ist als gleich direkt zu berechnen.

[Jörg Reinholz]

Das muss man ausprobieren, ob eine näherung mit einer Bounding-Box schneller ist als gleich direkt zu berechnen.

Davon würde ich immer dann ausgehen, wenn die Koordinaten-Spalten in der DB indexiert sind und die Datentabelle mehr als 30 zeilen enthält.

Wenn die Datenbank ordentlich optimiert, dann könnte auch die where-Klausel entsprechend gestaltet werden:

...  
WHERE  
laenge=betwen(minLaenge, maxLaenge)  
AND  
breite=betwen(minBreite, maxBreite)  
AND  
#Maxentfernung# <= ( (6378.388 * ACOS(SIN(#Breite Suchort#) * SIN(`breite`) + COS(#Breite Suchort#) * COS(`breite`) * COS(`laenge` - #Laenge Suchort#)) )  
...

Erst wenn die Länge und Breiten überhaupt in das vorberechnete Viereck passen wird die "etwas" teurere Berechnung durchgeführt - wenn der SQL-Server vernünftig optimiert.

Zur Formel siehe auch http://www.kompf.de/gps/distcalc.html

Jörg Reinholz

[suit]

Davon würde ich immer dann ausgehen, wenn die Koordinaten-Spalten in der DB indexiert sind und die Datentabelle mehr als 30 zeilen enthält.

Die größte derartige Geschichte die ich derzeit am Laufen habe ist eine Händlersuche für einen größeren Möbelhersteller - der hat derzeit 1132 Händler auf der Karte. Bei einem Versuch, die Berechnung mit einer Bounding-Box zu beschleunigen wurde die Suche sogar langsamer (im 2-stelligen ms-Bereich, also nicht signfikant).

laenge=betwen(minLaenge, maxLaenge)

Erst wenn die Länge und Breiten überhaupt in das vorberechnete Viereck passen wird die "etwas" teurere Berechnung durchgeführt - wenn der SQL-Server vernünftig optimiert.

Déjà-vu:
http://forum.de.selfhtml.org/archiv/2013/2/t212676/#m1452996

Was bei deiner Näherung fehlt ist die Tatsache dass wir von einer Kugeloberfläche ausgehen - während die Längengrade rundherumlaufen tun es die Breitengrade nicht. Länge 359 und Länge 1 sind näher zusammen als Länge 1 und Länge 10, würden von deiner Formel aber ausgeschlossen.

Zur Formel siehe auch http://www.kompf.de/gps/distcalc.html

Die Formel dort ist richtig, bei Radius der Erde geht sie aber von einem falschen Wert aus:
Der Wert dort entstammt der großen Halbachse des Hayford-Ellipsoid - er ist also einerseits falsch, weil die große Halbachse verwendet wird und andererseits weil sie einem hoffnungslos veralteten Standard entstammt :)

[Jörg Reinholz]

Déjà-vu:
http://forum.de.selfhtml.org/archiv/2013/2/t212676/#m1452996

Jaja. Und wie Du sehen konntest habe ich den Spaß inzwischen weiter durchdacht und in die where-Klausel verlegt.

Mit dem Verweis auf das Testen der Performance hast Du durchaus recht. Es kommt sehr auf die Datenbank (welche Software, Größe, Indexierung ..) an.

Wenn die Datenbank also die AND- verknüpften WHERE-Klauseln in der Reihenfolge abarbeitet und beim ersten false damit abbricht (hier also auf die Berechnungen verzichtet) und den Datensatz verwirft, dann sollte das wirklich schneller gehen.

Über die verwendete Formel kann man sich sehr lange unterhalten. Die Frage ist immer das Preis (Rechenzeit)-Leistungs-(Genauikeits)verhältnis. Denn die Erde ist "kartoffelförmig". Da kann man es sehr kompliziert machen ... oder Ungenauigkeiten bewusst hinnehmen.

Aber auch das hatten wir schon.

Jörg Reinholz

[suit]

Über die verwendete Formel kann man sich sehr lange unterhalten.

Um die Formel gings mir nicht - sondern um den Wert der für den Radius angenommen wurde - natürlich lässt sich darüber streiten welchen Wert man nimmt, aber der dort verwendete Wert ist sowas von falsch - falscher gehts kaum :)

[Jörg Reinholz]

Über die verwendete Formel kann man sich sehr lange unterhalten.

Um die Formel gings mir nicht - sondern um den Wert der für den Radius angenommen wurde - natürlich lässt sich darüber streiten welchen Wert man nimmt, aber der dort verwendete Wert ist sowas von falsch - falscher gehts kaum :)

Hm. Wikipedia sagt:
Äquator- – Poldurchmesser* 12.756,32 – 12.713,55[2] km

Demnach wären:
Radius über die Pole: 6378.16 km
Radius am Äquator:  6356.775 km

Der für unsere Breiten mal angenommene Durchschnitt aus beiden wäre: 6367.4675 km.

Verwendet wurde: 6378.388. Naja. Das sind fast 2% Unterschied. Linear hochgerechnet also 20m auf 10km. Also wenn man nun die Entfernung von Untergenauheim nach Obergenauheim (laut Formel: 999.457m, laut Laser-Entfernungsmesser: 10000564.34578m +/- 0.32m*10^-15) berechnet, dann ist das schon so falsch, dass sagen kann "falscher gehts kaum".

In einem Punkt aber hast Du recht: die Zahl ist falsch.

Jörg Reinholz

[suit]

Hm. Wikipedia sagt:
Äquator- – Poldurchmesser* 12.756,32 – 12.713,55[2] km

Demnach wären:
Radius über die Pole: 6378.16 km
Radius am Äquator:  6356.775 km

Von welcher Wikipedia reden wir?
https://de.wikipedia.org/wiki/Erdradius

Der für unsere Breiten mal angenommene Durchschnitt aus beiden wäre: 6367.4675 km.

Verwendet wurde: 6378.388. Naja. Das sind fast 2% Unterschied.

Mit 1,6 % Unterschied hat schon Eratosthenes gearbeitet - das war aber um rund 240 vor Christus ;)

[Jörg Reinholz]

Mit 1,6 % Unterschied hat schon Eratosthenes gearbeitet - das war aber um rund 240 vor Christus ;)

Ich sagte ja, man könne sich sehr lange über das Thema unterhalten. ;-)

Jörg

[Kay]

Wenn ich mich ganz schwach erinnere macht man eine Umkreisberechnungen mit M-Trees ((Geo)-Spatial, B+Tree, R-Tree, waren so Stichworte) und spätestens nach dem dritten Knotenzugriff sind die Ergebnisse da. In der MongoDB Dokumentation oder in einer englischen Doktorarbeit über die Geospitalfunktion, war die Funktionsweise von Entfernungsrechnungen recht genau beschrieben.

PostGIS für PostgreSQL  oder http://www.osgeo.org/ könnte auch hilfreich zum Thema sein.

Ob es passt weis ich nicht, ist nicht die Doktorarbeit die ich meinte.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.21.1108&rep=rep1&type=pdf

Aber ob sich der Aufwand lohnt bei so ein paar Datensätzen?

Für die PHP und MySQL Wrickler

http://www.mamat-online.de/umkreissuche/opengeodb.php#copyright

[suit]

habt ihr schon einmal eine Umkreissuche programmiert? z.B. ich befinde mich in Köln (50679) und möchte sagen zeig mir alle Daten an, die um Umkreis von 10km sind.

Definiere "Umkreis" :)

Wie könnte ich das lösen?

Ich gehe davon aus, du willst eine einfache übliche Möglichkeit verwenden. Dabei gehen wir von folgenden Faktoren aus:

1. du willst die Luftlinie berechnen und vernachlässigst, wie Jörg schon angedeutet hat irgendwelche Hindernisse wie Flüsse ohne Bücken oder Berge.

2. du gehst davon aus, dass die Erde näherungsweise eine Kugel ist und nimmst dafür einen fertigen Standard her GRS 80 definiert hier das WGS84 Ellipsoid, welches unter anderem auch für GPS verwendet wird. Wir nehmen die dortige Definition des Ellipsoids und legen das auf eine Volumengleiche um - das entspricht dann einem mittleren Erdradius von 6371000,785 Metern

3. wir ignorieren sämtliche Abplattungs oder positionsabhängigen Radiusabweichungen und nutzen _nur_ diese Kugel - das führt in Europa, den USA - also "unseren Breiten" zu guten Ergebnisse, scheitert aber um einige Meter wenn es um Berechnungen in Pol- oder Äquatornähe geht oder welche die sich von der Nord- in die Südhalbkugel erstrecken.

Das einzige was jetzt noch zu tun ist, ist eine Orthodrome zu berechnen - das ist ein Teilstück aus einem Großkreis auf einer Kugeloberfläche.

Die Formel zur Berechnung dieser Strecke findet sich auch in der deutschsprachigen Wikipedia
https://de.wikipedia.org/wiki/Orthodrome#Strecke

Ein Fallstrick hierbei: Längen und Breitengrade werden mit Winkelgraden (voller Winkel = 360 Grad) angegeben, die meisten Script- und Programmiersprachen erwarten aber bei trigonometrischen Funktion eine Angabe in Radiant. Und dann natürlich nicht vergessen: das Ergebnis ist in Metern.

[Linuchs]

Hallo Klaus,

ich denke, das ganze Fachgesimpel mit der Kartolffelform der Erde nutzt dir nichts. Wahrscheinlich willst du gar keine Grenzsteine setzen, die auf den Millimeter stimmen müssen.

In meinem Veranstaltungskalender mache ich genau das, was du brauchst. Ein Zentrum und einen Radius in km:
http://remso.eu/?LO=kompakt&ORT=8328&KM=10

Für jede ort_id ist in der Datenbank der GPS-Wert abgelegt, den hole ich mir für 50679 Köln:
Länge = 6.98103, Breite = 50.9374

Dann ermittle ich in einem SQL-Kommando für alle Veranstaltungen die Entfernung und filtere die raus, die kleiner oder gleich 10 km sind. Erstaunlicherweise geht das sehr schnell, die für Menschen recht umständliche Entfernungs-Formel scheint ein "Klacks" zu sein für die Datenbank.

Erstmal bis hierher. Wenn du mehr wissen möchtest, melde dich bitte nochmal.

Linuchs

[suit]

ich denke, das ganze Fachgesimpel mit der Kartolffelform der Erde nutzt dir nichts.

So weit muss der OP doch garnicht gehen - die korrekte Formel zur Berechnung habe ich in meinem ersten Beitrag direkt verlinkt, steht groß mit Erklärung in der Wikipedia

Für jede ort_id ist in der Datenbank der GPS-Wert abgelegt,

Das glaube ich nicht :)

den hole ich mir für 50679 Köln:
Länge = 6.98103, Breite = 50.9374

Das sind Längen- und Breitengrade - GPS-Koordinaten sind eine Nummer komplizierter, die beinhalten zusätzlich zu Längen- und Breitengraden auch noch ein Gitter mit Korrekturwerten sowie zusätzlich Referenzpunkte die das Referenzgeoid mit den tatsächlichen Messpunkten vergleichen:
https://en.wikipedia.org/wiki/Military_grid_reference_system

Dann ermittle ich in einem SQL-Kommando für alle Veranstaltungen die Entfernung und filtere die raus, die kleiner oder gleich 10 km sind.

Interessant wäre, _wie_ du das machst - sprich welche Formel du verwendest.

die für Menschen recht umständliche Entfernungs-Formel scheint ein "Klacks" zu sein für die Datenbank.

Unter den Annahmen die ich vorgegeben habe ist auch die Formel für einen Menschen einen Klacks, wenn man mit Trigonometrie umgehen kann - das ist zumindest in
Österreich Pflichtschulstoff :)

[Linuchs]

Länge = 6.98103, Breite = 50.9374

Das sind Längen- und Breitengrade - GPS-Koordinaten sind eine Nummer komplizierter, ...

Mag sein, mich interessiert von den GPS-Satelliten die Info über
window.location.href = "http://[HOST]/?zp=p591a&GPS=" +position.coords.latitude +"," +position.coords.longitude;

Interessant wäre, _wie_ du das machst - sprich welche Formel du verwendest.

$sql_umkreis = "AND ROUND( 6366.19773095 * ACOS( SIN(".$rad_lat1.") *SIN(RADIANS(ort1.geo_breite)) +COS(".$rad_lat1.") *COS(RADIANS(ort1.geo_breite)) *COS(RADIANS(ort1.geo_laenge) -".$rad_lon1." ))) <= '".$arr_in['KM']."'";

Unter den Annahmen die ich vorgegeben habe ist auch die Formel für einen Menschen einen Klacks, wenn man mit Trigonometrie umgehen kann - das ist zumindest in
Österreich Pflichtschulstoff :)

Naja, ob du für 200 Orte in 0,1 sec die Entfernung berechnen kannst ...

Linuchs

[suit]

Interessant wäre, _wie_ du das machst - sprich welche Formel du verwendest.
$sql_umkreis = "AND ROUND( 6366.19773095 * ACOS( SIN(".$rad_lat1.") *SIN(RADIANS(ort1.geo_breite)) +COS(".$rad_lat1.") *COS(RADIANS(ort1.geo_breite)) *COS(RADIANS(ort1.geo_laenge) -".$rad_lon1." ))) <= '".$arr_in['KM']."'";

Das ist die Formel mit der man eine Orthodrome berechnen kann - eine andere "Magie" hab' ich nicht erwarete :)

btw, hier gibts einen Fehler: http://remso.eu/?GPS=Rothenburg%20ob%20der%20Tauber

Unter den Annahmen die ich vorgegeben habe ist auch die Formel für einen Menschen einen Klacks, wenn man mit Trigonometrie umgehen kann - das ist zumindest in
Österreich Pflichtschulstoff :)
Naja, ob du für 200 Orte in 0,1 sec die Entfernung berechnen kannst ...

Eh klar :D