Umkreissuche

[Toeb]

Hallo zusammen,

ich habe mir neulich Gedanken gemacht, wie so eine Umkreissuche, die mittlerweile auf etlichen Websites zu finden ist, funktioniert.

Hatte mir auch überlegt, so etwas mit PHP zu realisieren... aber wie?

Als erstes mal ein Beispiel, wie das ganze aussieht ->
Auf einer Website eines sehr bekannten Internet-Auktionshauses, ist es möglich nach Artikeln zu suchen, im Umkreis von z.B. 50km, oder 200km...
Dazu muss man natürlich seine PLZ eingeben... und man erhält alle entsprechenden Artikel dazu.

Was mir hierbei aufgefallen ist:
Suche ich einen Artikel im Umkreis von 20km, kann ich mir ja die Ortschaften der Ergebnismenge anschauen und gerade bei solchen Suchen im näheren Umkreis liegt eine Fehlberechnung von teilweise 25%.

Wie funktioniert diese Suche?
Aufgrund der Fehlerquote kann ich mir nicht vorstellen, dass eine geographische Karte mit allen Straßen und Städten, wie bei einem Routenplaner zu Berechnung herangezogen wird.
Vielleicht irre ich mich aber auch ;-)

Gibt es dafür vorgefertigte Scripte? Falls ja, in welcher "Sprache", oder in welchen "Sprachen"?

Würde mich freuen, wenn mir jemand schildern könnte wie dies nun genau funktioniert und vielleicht sogar ein geläufiges Script oder dergleichen (falls existiert) nennen könnte.

Ansonsten wünsche ich ein schönes und erholsamen Wochenende,
Toeb

PS: Verzeiht mir, aber ich konnte mich nicht genau entscheiden in welchen Themenbereich dies gehört ;-)

[Cruz]

Hallo Toeb,

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.

Man weiss zwar nie genau wie die das machen, aber hier ist mal ein Ansatz, der in etwa das von dir geschilderte Suchverhalten approximieren dürfte:

Zu allen Artikeln ist eine Portleitzahl hinterlegt. Sei unsere Postleitzahl 12345. Sucht man im Umkreis von ca. 1 km, dann sucht man nur nach Artikeln mit der selben Postleizahl, also 12345. Sucht man nach Artikeln im Umkreis von ca. 10 km, dann sucht man nach Artikeln mit Postleitzahlen, die mit 1234 anfangen. Für 50 km wären es dann Artikel mit Postleitzahl 123** usw.

Das Verfahren diskriminiert die Benutzer, die sich genau am Rand von Postleitzahlbereichen befinden und die Größen der Gebiete kann man sicherlich noch etwas besser zurechttunen, wenn man über die Verteilung der Postleitzahlen besser informiert ist. Aber es ist billig und hinreichend gut. :)

Gruß,
Cruz

[Sven Rautenberg]

Moin!

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?

Man weiss zwar nie genau wie die das machen, aber hier ist mal ein Ansatz, der in etwa das von dir geschilderte Suchverhalten approximieren dürfte:

Nein, dein Ansatz ist etwas komplett anderes.

Zu allen Artikeln ist eine Portleitzahl hinterlegt. Sei unsere Postleitzahl 12345. Sucht man im Umkreis von ca. 1 km, dann sucht man nur nach Artikeln mit der selben Postleizahl, also 12345. Sucht man nach Artikeln im Umkreis von ca. 10 km, dann sucht man nach Artikeln mit Postleitzahlen, die mit 1234 anfangen. Für 50 km wären es dann Artikel mit Postleitzahl 123** usw.

Postleitzahlen sind nicht passend zum "Umkreis" einer anderen Postleitzahl definiert. Derartige Suchen sind also grob fehlerhaft.

Das Verfahren diskriminiert die Benutzer, die sich genau am Rand von Postleitzahlbereichen befinden und die Größen der Gebiete kann man sicherlich noch etwas besser zurechttunen, wenn man über die Verteilung der Postleitzahlen besser informiert ist. Aber es ist billig und hinreichend gut. :)

Es ist sicherlich billig - aber grausam falsch. Insbesondere bei ungünstiger Verteilung der realen Daten.

Nur mal angenommen, ein PLZ-Bezirk mit der Nummer 1xxxx hätte eine nahezu kreisförmige Gestalt und etwas wie einen "Durchmesser" von vielleicht 20 Kilometern. Der Suchende wohnt aber am Rand dieses Bezirks - direkt neben dem PLZ-Bezirk beginnend mit 2xxxx. Dann ist es problemlos möglich, dass im Nachbarbezirk, nur wenige Kilometer vom Suchenden entfernt, ein Angebot existiert, während deine "Umkreissuche auf PLZ-Basis" als "direkt nebenan" den Anbieter aufzeigt, der im gleichen PLZ-Bezirk, aber eben 20 km entfernt ganz auf der anderen Seite existiert.

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.

- Sven Rautenberg

[Cruz]

Hallo Sven,

wieso haben die Leute die Angewohnheit immer etwas gleich als komplett falsch zu bezeichnen? Wenn man auf sachlicher Ebene über ein Thema diskutiert und dabei einen wirklichen Fehler im Gedankengang eines anderen entdeckt, dann ist es völlig in Ordnung dies aufzuzeigen und der Diskussionspartner sollte dafür auch dankbar sein. 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. Dieses Verhalten fällt mir hier im Forum an vielen Stellen auf und es hat mir wirklich den Spass genommen hier Postings zu schreiben und anderen Leuten zu helfen, daher möchte ich es an dieser Stelle deutlich kritisieren.

So und nun zum Thema.

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.

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 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.

Nein, dein Ansatz ist etwas komplett anderes.

Nein es ist nicht etwas komplett anderes, es ist eine sehr einfache Approximation. Unter der Annahme, dass wir uns alle Postleitzahlengebiete kreisförmig mit gleichem Radius vorstellen und unter der Bedingung, dass ein Gebiet genau 10 Gebiete der um 1 kleineren Dimension beinhaltet, 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. Wie groß man die Radien der Kreise wählen sollte kann man vielleicht nach Augenmaß auf der Deutschlandkarte ablesen. 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.

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.

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.

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.

Nur mal angenommen, ein PLZ-Bezirk mit der Nummer 1xxxx hätte eine nahezu kreisförmige Gestalt und etwas wie einen "Durchmesser" von vielleicht 20 Kilometern. Der Suchende wohnt aber am Rand dieses Bezirks - direkt neben dem PLZ-Bezirk beginnend mit 2xxxx.

Ja das wäre ein Extremfall für einen worst-case, das hast du richtig erkannt. 20 km ist da noch weit untertrieben. Wenn ich mir die größten einstelligen Postleitzahlengebiete anschaue und es befindet sich ein Artikel in der nördlichsten Spitze vom Gebiet 9xxxx und ein anderer gerade 1 km jenseits der Grenze zu Gebiet 3xxxx, dann würde mein vorgeschlagenes Verfahren die Distanz zwischen diesen beiden Artikel als größer einschätzen, als die Distanz zu einem Artikel in der südöstlichen Spitze von Gebiet 9xxxx, die sicherlich gute 500 km weiter weg liegt.

Derartige Suchen sind also grob fehlerhaft.

Das ist eine zu pauschale Aussage. Es gibt Extremfälle wie oben, in denen die Suche einen Fehler von mehreren hundert Kilometern macht. Es gibt aber auch Fälle, wo sie auf weniger als 1 km genau ist. Nur aus der Verteilung dieser Fälle kann man ein Mittelmaß für die Qualität der Distanzbewertung ableiten.

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. Wenn wir für jede Postleitzahl eine Koordinate besitzen, dann können wir erstens von der schwachen Annahme loskommen, dass alles Postleitzahlengebiete gleich große Kreise sind UND viel wichtiger: wir können dann Distanzen direkt zwischen 2 Artikeln schätzen. Dies ermöglicht folgendes verbessertes Suchverhalten. Der User spezifiziert einen nun frei wählbaren Radius, in denen sich der von ihm gesuchte Artikel befinden muss. Ausgehend von der Postleitzahl des Users können wir nun aus den 100.000 möglichen 5-stelligen Postleitzahlgebieten anhand den Geokoordinaten alle Gebiete heraussuchen, deren Koordinate sich innerhalb eines Kreises um die Postleitzahlkoordinate des Benutzers mit dem angegebenen Radius befinden. Nun selektieren wir alle Artikel, die diesen gefundenen Postleitzahlen zugeordnet sind. (Es werden evtl. weitere Suchkriterien angewendet, die nichts mit der entfernung zu tun haben.) Wenn sich Artikel an Rändern von Postleitzahlengebieten befinden, macht dieser Algorithmus die selbe Art von Schätzfehler, der aber wahrschenlich im Bereich < 10 km liegt. Die Genauigkeit wird also durch dein Vorschlag um Größenordnungen verbessert.

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.

Gruß,
Cruz

[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

[Cruz]

Sven,

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

Du hättest auch mit einer passenderen Reaktion in meinen Augen dein Gesicht wahren können, aber wenn du lieber nach so einem dünnen Halm greifst, soll es mir recht sein.

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

Nein die Anforderungen und die Algorithmen sind die selben, die Frage ist einzig und allein die _Genauigkeit_.

Nein, dein Ansatz ist etwas komplett anderes.

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

Die falsch ist.

Eine Approximation kann nicht falsch sein. Sie hat als Eigenschaft ein Grad an Ungenauigkeit, den man messen bzw. von unten und oben beschränken kann.

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

Was der Realität entspricht ist, dass wir es mit kontinuierlichen Distanzen zu tun haben, die wir mit einer Maschine mit endlichem Speicher niemals exakt darstellen können. Wir haben gar keine andere Möglichkeit, als zu approximieren. So langsam müsste dir dieses Konzept der Abstraktion klar werden. Man kann z.b. auch ein Polynom noch so hochen grades mit einer lineren Funktion approximieren. Ein "geht nicht" und ein "falsch" gibt es nicht, man tut es einfach und bewertet bzw. minimiert den Fehler, den man dabei macht.

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.

Diese Aussage lässt vermuten, dass du das Verfahren noch nicht 100% verstanden hast. Auch wenn ich es unter den Annahmen aufgeschrieben habe, ist es nicht notwendig, dass alle 10 Gebiete in einem nächstgrößerem Gebiet wirklich vorhanden sind.

Nur ein Beispiel: Leitregion 99 ist der Raum um Erfurt.

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.

Ja das hast du sehr schön beobachtet. Das sind zwei viese Fälle, die bei der Abstraktion auf die Gebiete 9**** und 6**** besonders schlecht behandelt werden. Wir haben doch schon ein Posting vorher die Randfälle betrachtet, diese sind weitere 2 davon.

Egal was du für einen Sonderfall ausgräbst, auch in deinem Verfahren lässt sich immer ein entsprechendes Beispiel finden, wo der Algorithmus die räumliche Nähe falsch bewertet. Dein Verfahren ist nämlich auch nur eine Approximation. Die Fehlerfälle sind in beiden Verfahren von der selben Art, dies ist auch optisch gut zu erkennen, nur bei dir ist der Fehler nicht so groß.

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.

Ja ich glaube es ja gut und gerne, ich habe ja keine Befürchtungen wegen der Performance geäußert.

Und damit wir uns nicht missverstehen, ich finde dein Verfahren ja sehr attraktiv. Ich habe es denke ich ausdrücklich genug unterstützt und sogar eine kleine technische Ausführung dazu geschrieben. Mir geht es auch nicht darum wessen Verfahren der bessere ist. Dein Verfahren macht viel kleinere Fehler, mein Verfahren braucht keine Daten. Was für einen wichtiger mag jeder selbst entscheiden. Was mir gegen den Strich geht ist diese Pauschalisierung, dass mein Verfahren "etwas komplett anderes" rechnet. Es war sehr unüberlegt und entspricht nicht der Wahrheit.

Gruß,
Cruz

[Stefano Albrecht]

Servus Cruz,

Du hättest auch mit einer passenderen Reaktion in meinen Augen dein Gesicht wahren können, aber wenn du lieber nach so einem dünnen Halm greifst, soll es mir recht sein.

ich glaube Du beurteilst das ein wenig zu hart.

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).

So wie ich das gelesen habe, war es durchaus humorvoll gemeint. Wer kennt nicht den Korinthenkacker? Vielleicht hätte ein Smiley die Aussage verstärkt. Jedenfalls ist dies mein Eindruck, ohne irgendetwas vorweg zu nehmen.

Was mir gegen den Strich geht ist diese Pauschalisierung, dass mein Verfahren "etwas komplett anderes" rechnet.

Dafür habe ich großes Verständnis. Auch ich kann ein solches Verhalten nicht ausstehen. Trotz allem könnte das, was der "Böse" sagt, völlig richtig sein. Für die Verträglichkeit ist jedoch allein die Verpackung verantwortlich, wie Du schon sagtest.

Freundliche Grüße
Stefano Albrecht

[Tillmann]

Hallo Toeb,

um mal wieder auf Deine Frage zu kommen: Ich würde dir empfehlen, dich mal ein bißchen mit dem Kapitel "Raumbezogene Erweiterungen in MySQL" in der Doku zu MySQL 5 auseinanderzusetzen. Dies dürfte der einfachste Weg sein, um eine solche Entfernungsberechnung durchzuführen.

Angenommen, Du hast von OpenGeoDB eine DB-Tabelle, die jeder PLZ eine (Mittelpunkts-)Koordinate zuweist. Dann überführst Du die "nackten Zahlen" per SQL-Befehl(en) in eine Geometry (POINT). Nun kannst Du ganz einfach die (räumliche) Entfernung zweier Punkt berechnen mit Distance(g1,g2). Das ganze programmiert als Funktion mit den PLZ als Inputparametern wäre doch schon eine feine Sache ... Einen Umkreis kannst Du dann z.B. durch "Buffer" erzeugen -> und dann alle Punkte heraussuchen, die "Within" liegen.

Buffer gehen in MySQL 5.1 allerdings noch nicht ... ;) Es lebe Oracle!

Hilft Dir das weiter?

Grüße,
Tillmann