Umkreissuche

[Sven Rautenberg]

Moin!

wieso haben die Leute die Angewohnheit immer etwas gleich als komplett falsch zu bezeichnen?

Ich habe deinen Ansatz als "komplett etwas anderes" sowie "grob fehlerhaft" und auch "grausam falsch" bezeichnet. Aber nicht als komplett falsch.

Außerdem habe ich Korinthen billig abzugeben (Tütenware).

Aber einfach nur so "komplett falsch" reinzurufen ohne handfeste Begründung und offensichtlich ohne das Konzept des anderen in Vollständigkeit verstanden zu haben ist unhöflich und auch nur sehr wenig wissenschaftlich.

Eine Begründung meiner Ansicht lag meinem Posting bei.

ich kann mir auch nicht vorstellen, dass die Geoinformationen auswerten, denn das wäre eine viel zu große Datenmasse für diesen kleinen Zweck, die teuer zu beschaffen ist.

Wieso das denn?

Weil es viele Orte, sehr viele Postleitzahlen, enorm viele Strassen und unfassbar viele Hausnummern in Deutschland gibt. Um halbwegs echte Distanzen zwischen Adressen auszurechnen musst du schon Geokoordinaten auf der Straßenebene besitzen. Wenn du nur pro Postleitzahl eine Koordinate hast, dann bist du in etwa bei dem Verfahren, das ich anfangs vorgeschlagen habe. Ich erkläre gleich warum.

Aber ist es denn so unwahrscheinlich dass diese "Website eines sehr bekannten Internet-Auktionshauses" nicht einfach so eine umfangreiche Geo-Datenbank eingekauft oder lizensiert hat, um Umkreissuchen mit echten oder zumindest realistisch guten Ergebnissen zu produzieren.

Sollte sich deine "wieso" Frage nicht auf die Menge, sondern auf die Kosten der Daten bezogen haben, dann habe ich dazu Folgendes zu erwidern. Es mag sein dass man eine Koordinate pro Postleitzahl von der OpenGeoDB kostenlos bekommt, aber wie gesagt befriedigt das noch nicht die Distanzen auf der Strassenebene.

Ich vermute, ebay dürfte sich daran nicht stören, dass sie für Geodaten zahlen müssen.

Und für kleinere Websites ist die OpenGeoDB eigentlich brauchbar genug - IMHO.

Ich war gerade erst vor ein paar Monaten an der entwicklung eines Navigationssystems für PDAs beteiligt. Wir haben uns gründlich nach Quellen für Geodaten umgesehen und keine Möglichkeit gefunden uns die Daten in adequater Granularität auch nur für eine im Vergleich beschränkte Region einer Stadt mit unserem begrenzten Budget einzukaufen. Dies ist auch verständlich, denn es steckt eine unglaubliche Menge Arbeit dahinter alle Straßen und sogar Hausnummer genau zu vermessen. Wenn dir eine Quelle bekannt ist, wo man die Geodaten in gewünschter Form kostenfrei oder erschwinglich bekommen kann, bitte lass es mich wissen.

Ein Navigationssystem hat ja auch ganz andere Anforderungen an die Geodaten, als eine Umkreissuche für ein Internetauktionshaus.

Ansprechpartner für Navigationskartendaten wären amtliche Stellen (Vermessungsamt) oder Landkartenverlage. Die aber sicherlich entsprechendes Geld sehen wollen.

Nein, dein Ansatz ist etwas komplett anderes.

Nein es ist nicht etwas komplett anderes, es ist eine sehr einfache Approximation.

Die falsch ist.

Unter der Annahme, dass wir uns alle Postleitzahlengebiete kreisförmig mit gleichem Radius vorstellen

Das entspricht nicht der Realität.

und unter der Bedingung, dass ein Gebiet genau 10 Gebiete der um 1 kleineren Dimension beinhaltet,

Das ist ebenfalls nicht der Fall

rechnet das Verfahren genau die vom OP gewünschte Aufgabe.

Beispiel: sagen wir der Kreis mit dem Radius 10 für das Postleitzahlengebiet 1234* beinhaltet die 10 Kreise mit dem Radius 1 für die Gebiete 12340 - 12349.

Daran scheitert es ja schon. Postleitzahlen sind eben gerade NICHT fortlaufend numeriert, es gibt beliebig große Lücken mit (noch) nicht vergebenen Zahlen. Es ist daher äußerst unwahrscheinlich, dass tatsächlich alle Zahlen 12340-9 existieren.

Nun ja, dadurch würde ja nur die Anzahl der Regionen sinken, hätte man eben nicht mehr 10 Kreise in dem Superkreis, sondern eben nur 5 oder 3.

Schlimmer ist aber, dass dieses Schema sowohl im Detail, als auch im Groben, eben nicht paßt.

Schau dir einfach mal eine Landkarte mit den PLZ-Leitregionen an. Die Post definiert die erste Ziffer der PLZ als Leitzone, die ersten beiden Ziffern als Leitregion.

Zwei Dinge fallen auf, wenn man so eine Landkarte (z.B. im PLZ-Buch, keine Ahnung, ob das auch online abrufbar ist) betrachtet:

1. Im Osten der Republik sind die Leitregionen viel größer, als z.B. im Ruhrpott.

2. Insbesondere an den Grenzen zu anderen Leitzonen unterscheiden sich die Postleitzahlen drastisch.

Nur ein Beispiel: Leitregion 99 ist der Raum um Erfurt. An diese Leitregion grenzt:
Region 98 um Suhl - das ist die einzige Region aus der Zone 9, die eine Grenze mit Leitregion 99 hat.

Region 36 um Fulda.
Region 37 um Göttingen.
Region 38 um Braunschweig.

Region 06 um Halle.
Region 07 um Gera.

Gemäß deiner Definition, dass identische Präfixe in der PLZ auch örtliche Nähe bedeuten soll, wäre also Region 94 um Passau "dichter dran", als jede dieser direkten Nachbarregionen aus den ganz anderen Leitzonen.

Oder als anderes Beispiel: Leitregion 65 um Wiesbaden hat als Zahlennachbar die 66 (um Saarbrücken). Zwischen diesen beiden Regionen, die nicht direkt aneinander grenzen, liegt aber Leitregion 55 (Mainz), d.h. alle Orte in Region 55 sind näher an Leitregion 65, als irgendein Ort der Region 66.

Und was auf dieser hohen Ebene gilt, gilt auch auf niedrigerer Ebene. Nur eben nicht mehr mit so dramatischen Entfernungen, aber dennoch ausreichend störend.

Wie groß man die Radien der Kreise wählen sollte kann man vielleicht nach Augenmaß auf der Deutschlandkarte ablesen.

Kann man nicht wirklich. Im dünn besiedelten Osten sind die PLZ-Gebiete groß, im Ruhrpott klein. Durchschnittswerte zu bilden ist wenig sinnvoll.

Ich betone auch nochmal, dass der Algorithmus keine Distanz zwischen zwei Postleitzahlen berechnet, sondern lediglich Artikel aus der Datenbank heraussucht, die sich _wahrscheinlich_ innerhalb eines vorgegebenen Umkreises befindet, wobei selbst die Größe der Umkreise in Abhängigkeit der gewählten Kreisradien vorgegeben ist und nicht frei wählbar ist.

Wenn man basierend auf PLZ-Ähnlichkeit sucht, dann sollte man das dem Benutzer auch sagen. Und nicht das falsche Label "Umkreissuche" draufkleben. Denn ein Einwohner wird schon wissen, welche Postleitzahlen er in seiner Umgebung hat, und die Suchergebnisse entsprechend bewerten.

Dieser Ansatz ist in 10 Minuten gecodet und kommt völlig ohne zusätzliche Daten aus und dürfte für die Benutzer von kleineren Onlineflohmärkten ein ausreichendes Gefühl von "nah dran" oder "weit weg" vermitteln.

Kleine Onlineflohmärkte benörigen vermutlich keine Umkreissuche. Und wenn man "PLZ-Suche" draufschreibt und erklärt, dass man nach ähnlichen PLZ sucht, ist ja auch jeder zufrieden, weil er die Ergebnisse einordnen kann.

Zur weiteren Ergänzung möchte ich nochmal aufgreifen, dass der OP auch tatsächlich an einer Annäherung interessiert war, denn seine Vermutug war es dass die Distanzschätzung, die er gesehen hat, ohne Geodaten arbeitet und seiner Einschätzung nach etwa zu 25% fehlerhaft ist.

Was er genau gemessen oder gesehen hat, wissen wir nicht. 25% Abweichung halte ich bei einer Umkreissuche basierend auf den Geodaten der Mittelpunkte von PLZ-Gebieten für durchaus denkbar.

Postleitzahlen sind nicht passend zum "Umkreis" einer anderen Postleitzahl definiert.

Das ist aber nun mal die Annahme die wir reingesteckt haben, um uns Arbeit und Daten zu ersparen. Die wirklichke Verteilung der Postleitzahlen ist wenigstens grob annähernd so gegeben.

Nein, absolut nicht! Siehe Beispiel oben.

Auf die Idee, PLZ-Nummern wären in irgendeiner Form für Geosuchen nutzbar, kommt man nur, wenn man noch nie eine PLZ-Landkarte angeschaut hat. Solltest du mal tun, ist echt erhellend.

Was die Ortsdaten und deren Kosten angeht: Die OpenGeoDB liefert für jede PLZ oder für jeden Ort in Deutschland, Österreich und der Schweiz Ortskoordinaten kostenlos. Diese in einem simplen Algorithmus in eine Umkreissuche zu verfrachten ist keinerlei Hexerei, sondern liefert relativ gute Ergebnisse.

Ja, dieser Vorschlag würde sicherlich eine deutliche Verbesserung der Approximation ermöglichen. [...]
Allerdings muss man auch etwas mehr Arbeit, Speicherplatz und Rechenleistung investieren. Der Algorithmus lässt sich wahrscheinlich in 30 Minuten implementieren, benötigt etwa 100.000 Datensätze, die man von OpenGeoDB abgreifen und "einverleiben" muss. Bei 100.000 Gebieten würde ich mir aber um die Performance keine Sorgen machen.

Ich habe in VBScript/ASP mal einen Algorithmus geschrieben, der die gesamte OpenGeoDB als Textdatei durchliest, die Zeilen mit passender PLZ (des Suchers) ermittelt und (weil mehrere Koordinaten zur PLZ gespeichert sind) einen gewichteten Mittelwert errechnet. Und das innerhalb von einer Sekunde erledigt hat.

Wenn das Verfahren mit rudimentärsten Mitteln, unindiziert und vielen vorausberechenbaren Ergebnissen nur eine Sekunde benötigt, dann ist es keinesfalls zu aufwendig, auch für kleine Anwendungen nicht. Die Website der OpenGeoDB liefert ja diverse Anwendungsbeispiele und Funktionen zur Koordinatenermittlung mit.

- Sven Rautenberg