Umkreissuche in PHP – Teil 2

Lesetipps

1. Umkreissuche in PHP – Teil 1
2. MeinPHP: Typsicheres Set – Auflösung Teil 3
3. Der Iterator – Teil 2

Hier ist nun der zweite Teil meines Umkreissuche-Artikels. Es tut mir leid, falls der eine oder andere vor Aufregung nicht schlafen konnte, aber jetzt ist ja auch schon der nächste Tag und wir machen weiter. Wir haben jetzt also alle Einzelteile, die man für eine Umkreissuche benötigt. Jetzt müssen wir sie nur noch anhand der OpenGeoDB zusammenführen. Sollte ja eigentlich kein Problem sein.

Aber vielleicht reiße ich nochmal schnell unsere Vorgehensweise und die Problemstellung an. Wir haben also einen User und wollen ihm anzeigen, welche andere User in 50km Umkreis wohnen. Klingt ja ganz einfach. Fangen wir also an. Zuerst benötigen wir die PLZ des Benutzers, was nicht wirklich ein Problem sein sollte, denn in unserer Community können wir ja selbst bestimmen, welche Daten der User beim Anmelden hinterlegen muss. Schritt Zwei wäre alle Postleitzahlen zu suchen, die nicht weniger als 50km entfernt sind. Im dritten und letzten Schritt suchen wir uns die User raus, die in diesem PLZ Bereich wohnen. Tadaaa wir sind fertig. Natürlich kann man noch irgendwelche Heuristiken einführen, es darf z.B. die erste Stelle der PLZ nur um eine Zahl abweichen oder ähnliches. Hier ist der Kreativität keine Grenze gesetzt. Wir bleiben aber bei unserem einfachen Beispiel und der nicht ganz so performanten Methode. Wer von euch das ganze verbessern will kann dies natürlich tun, werde dann hier auch drüber berichten.

Eigentlich hatte ich mir hier vorgenommen noch ein paar SQL Anfragen zu posten, mit denen man z.B. den Abstand zwischen Karlsruhe und Berlin ausrechen kann. Da ich aber gerade nicht so viel Zeit habe und die GeoDB ca. 50 MB groß ist und ich mich da erstmal wieder einarbeiten muss, werde ich das ganze einfach auf eine andere Session verschieben. Natürlich könnt ihr das auch über positives Feedback beschleunigen. Wenn ihr Beispiel habt, dann könnt ihr die hier auch posten.

So das war auch schon wieder meine kleine Einführung in die Umkreissuche. Ich hoffe, dass ich wenigstens einigen von euch einen Einblick geben konnte und ihm/ihr auch die Angst davor genommen habe. Spielt einfach ein wenig mit rum und ihr werdet sehen, dass es gar nicht so schwer ist,

5 Kommentare »

• 
  

  Zoer Znu

  am 8. März 2009 um 18:47 Uhr

  Methoden zur Vereinfachung, die mit der PLZ rechnen, wie “die erste Stelle der PLZ nur um eine Zahl abweichen oder ähnliches”, sind absolut gefährlich. PLZ sind, obwohl das “Z” in PLZ für Zahl steht, keine Zahlen, sondern Nummern. Das ist also so, als ob man mit einer Telefonnummer rechnet.

  Was die Umkreissuche langsam macht ist, dass bei der Kreisberechnung schlecht ein Index der Datenbank benutzt werden kann. Also Full-Table-Scan!

  Was hier hilft ist, zuerst alle PLZ rauszuwerfen, die sich nicht innerhalb eines Quadrates mit der Seitenlänge der Umkreissuche und Mittelpunkt in der aktuellen Position befinden. Also Abfrage wie folgt:

  where b.breitengrad between a.breitengrad – :UMKREIS and a.breitengrad + :UMKREIS
  and b.längengrad between a.längengrad – :UMKREIS and a.längengrad + :UMKREIS
  and sqrt(power(abs(a.breitengrad – b.breitengrad), 2) + power(abs(a.längengrad – b.längengrad), 2)) <= :UMKREIS

  Jetzt kann ein Index auf breitengrad und längengrad genutzt werden. Erst im Anschluss wird auf den verbliebenen PLZ die teuere Abfrage ausgeführt. Dem Quadrat werden also die Ecken abgeschnitten, so dass nur der Kreis (Umkreis) bleibt.

  Das ist die beste mir bekannte Methode, die ein richtiges Ergebnis liefert und schnell genug für einen realen Einsatz ist.

  Wer es noch schneller braucht, kann auch vorab die Entfernungen von jeder Postleitzahlen zu jeder Postleitzahl berechnen und in einer Tabelle speichern. Ist natürlich noch schneller, aber braucht auch mehr speicher und man muss auf Datenkonsistenz achten (aber wie oft ändert sich schon die Koordinaten einer PLZ ).

• 
  

  Olli

  am 25. März 2009 um 15:16 Uhr

  Hi.. der Thread ist hochinteressant. Würde mich sehr über ein konkretes Beispiel mitQeulltext freuen und eine Quelle für aktuelle Geodaten. OpenGeoDB hat doch noch sehr viele Altlasten in der Datenbank (4stellige deutsche Postleitzahlen..)

  Gruss Olli

• 
  

  Skywalker

  am 9. April 2009 um 09:03 Uhr

  Recht interessant diesbezüglich ist vielleicht noch das Open Source Projekt GeoClass (http://sourceforge.net/projects/geoclassphp/). Laut Kurzbeschreibung bei Sourceforge unterstützt die Klasse direkt OpenGeoDb.

  Gruß Skywalker

• 
  

  maxhb

  am 23. April 2009 um 20:54 Uhr

  Hi!
  habe eine entsprechende Suche schon einmal realisiert und folgende Vereinfachung als (erhebliche) Beschleunigung für die Suche verwendet:
  - Tabelle mit Geo-Daten um eine Spalte Mittelpunkt vom Typ POINT erweitern
  - Den Schwerpunkt jedes PLZ-Bereich mittels der MySQL-Funktion centroid() berechnen und in der zuvor angelegten Spalte speichern
  - Distanzberechnung nur noch auf den Mittelpunkten der PLZ-bereiche durchführen

  Pros:
  - Jeder PLZ-Bereich hat zu sich selbst die Entfernung 0 (Erwartungskonform
  - Distanzberechnung geht sehr schnell

  Cons:
  - Etwas ungenaue Distanzberechnung, insbesondere bei lang gestreckten PLZ-Bereichen

  Nur mal so als kleine Anregung
  Gruß
  maxhb

• 
  

  Matthias Meyer

  am 28. April 2010 um 00:14 Uhr

  OpenGeoDb stellt auch Tabellen zur Verfügung die für die Umkreissuche speziell in Deutschland besser geeignet sind. Hierzu einfach sich mal die *.tab-Dateien genauer anschauen (http://fa-technik.adfc.de/code/opengeodb/).
  Dort sind die Daten bereits aufbereitet, sodass die Enfternungsberechnung bei weitem einfacher (ohne joins) und auch schneller ist. Zudem benötigten die Tab-Daten bei weitem nicht soviel Speicherplatz.

  Vorsicht auch bei der Kombination bzw. Verwendung von OpenGeoDaten und GoogleMapsDaten. Ich habe dort unterschiede feststellen können. In wie weit das relevant ist, ist je nach Aufgabenstellung natürlich unterschiedlich.

  Viele Grüße,
  Matthias Meyer

RSS Feed für Kommentare zu diesem Artikel. TrackBack URL

Hinterlasse einen Kommentar