Umkreissuche programmieren

7 Beiträge27.08.2007Archiviert
Bonsai27.08.2007 · Beitrag #14587
Avatar
Mitglied seit: 02.06.2006
Forenbeiträge: 395
Besuche: 2691
Hallo,

hat jemand schon mal eine Umkreissuche (a la 1km,10km,20km,etc.) für ein Internetprojekt realisiert?? Wie funktioniert das, was wird berechnet und was benötigt man?
Disenchant27.08.2007 · Beitrag #14589
Avatar
Mitglied seit: 25.02.2005
Forenbeiträge: 519
Besuche: 5204
Hi,
habe so etwas zwar noch nie gemacht, weil ich's nie benötigt habe doch denke ich geht das wohl am besten, wenn du entweder alle verwendeten Punkte in ein Koordinatensystem einträgst, was sehr schnell sehr Rechenintensiv wird oder du machst es ein wenig gröber und machst ein Koordinatensystem in dem aber viele ähnliche Orte einem Bereich zugeordnet werden und so hast du sehr schnell die umliegenden Orte, die im gleichen Bereich sind sowie kannst du schneller als mit der genaueren Methode umliegende Orte finden.

Grüsse,
Disenchant
KingVik27.08.2007 · Beitrag #14592
Avatar
Mitglied seit: 31.10.2006
Forenbeiträge: 91
Besuche: 418
ist ein interessantes thema. hab bisschen gegoogled und hab das hier gefunden:
codebeispiel
und ein projekt welches sich damit schon beschäftigt hat:
opengeodb
jeipack28.08.2007 · Beitrag #14597
Avatar
Mitglied seit: 07.03.2007
Forenbeiträge: 448
Besuche: 1258
Hey Bonsai
Wo genau liegt den der Schwerpunkt? Performance? Genauigkeit? Sind es sehr viele Punkte, oder sind es sogar Flächen? Geht es um eine 2D oder 3D Karte? Muss also eine Erdkrümmung mitberechnet werden? etc pp.. Wir brauchen mehr Infos :)

Es gibt z.B: die folgende relativ einfach realisierbare Möglichkeit:
Zuerst nimmst du ein Quadrat mit dem Suchradius (1km, 10km, 20km) als Seitenlänge. Und nun must du noch via Pythagoras alle Punkte in diesem Quadrat auf ihre Entfernung zum Ausgangspunkt prüfen.
Dies ist nicht die performanteste Methode, dafür aber relativ einfach. Für keinere Mengen von Daten reicht es also völlig aus.
Ahja.. man kann diese natürlich noch erweitern, indem man weitere Quadrate nimmt um damit noch mehr Punkte auszuschliesen oder als gecheckt zu markieren.

@KingVik: Das erste berechnet die Distanz zweier Punkte und ist so nicht ideal. Es kann zwar umgebaut werden, doch würde ich unbedingt das mit dem Quadrat einbauen, da sonst viel zu viele Punkte gecheckt werden.
Und der zweite Link.. ein echt cooles Projekt.. wenn man da ein bisschen rumsurft findet man folgendes Projekt, welches sich wirklich mit einer Umkreissuche bescheftigt:
http://www.mprobst.de/OpenGeoNearestNeighbours/website/index.html
Allerdings auf den Daten von OpenGeoDB, muss also noch an deine Datenstruktur angepasst werden.

Gruss
[ Bearbeitet Di, 28. Aug 2007, 09:17 ]
Bonsai28.08.2007 · Beitrag #14602
Avatar
Mitglied seit: 02.06.2006
Forenbeiträge: 395
Besuche: 2691
Hmm .. klingt teilweise sehr kompliziert. Ich kann mir eigentlich nicht vorstellen, dass die ganzen Umkreissuchen in Communitys solch komplizierte Bereichnungen anstellen. Kann man u.U. etwas mit der PLZ oder GeoDaten in Form von Latitude und Longitude machen?
jeipack28.08.2007 · Beitrag #14607
Avatar
Mitglied seit: 07.03.2007
Forenbeiträge: 448
Besuche: 1258
Nun, den Link den ich dir gegeben habe, habe ich nicht näher Untersucht (um erlich zu sein weiss ich nicht einmal ob man dort überhaupt Einblick in den Quellcode bekommt)
Aber zu meiner Variante.. was genau ist daran kompilizert?
Zudem hast du noch keine zusätzliche Information angegeben, deshalb denke ich die Erdkrümmung ist vernachlässigbar und wir gegen von einer reinen 2D Karte aus. Auch gehe ich jetzt einfach mal davon aus, dass dich die Genauigkeit im Milimeterbereich nicht interessiert. Also kannst du die Koordinaten direkt von der Datenbank in ganze Zahlen runden lassen und dein Code nur mit Integer betreiben.
Angenommen du hast Punkt A(0|0) und willst alle Punkte die maximal 50Einheiten weit weg sind.
Nun gehst du so vor:
1. Quadrat um Punkt A "zeichnen" mit Seitenlänge 100 (nicht Radius wie ich oben genannt habe sondern Durchmesser)
2. Das wären nun alle Punkte die folgendes Erfüllen: x>=-50 and x<=50 and y>=-50 and y<=50
3. All diese Punkte die du nun hast prüfst du nun mit dem Pythagoras-Satz auf ihre Entfernung
Dies geschiet folgendermasen:
3.1 Speichere das Quadrat des Suchradius in einer Int Variable (hier also 50^2= 2500) diese benenne ich einfach mal rQuad
3.2 Prüfe für jeden Punkt der aus 2. rausgekommen ist nun folgende Bedingung: rQuad <= (x2-x1)^2*(y2-y1)^2. Bei jedem Punkt bei dem diese Bedingung wahr ist, weisst du dass er im Suchradius liegt. x1 und y1 sind die Koordinaten des Ausgangspunktes (hier A) und x2 und y2 des Punktes der überprüft werden soll.

.. Ja das wäre schon der ganze Zauber. Wie du siehst ganz einfach.. Ich hoffe ich hab nichts vergessen ^^

Gruss und viel Spass
jeipack


/edit: Das ganze würde wunderbar in ein SQL Script, resp. StoredProcedure reinapssen :)

[ Bearbeitet Di, 28. Aug 2007, 13:42 ]
KingVik28.08.2007 · Beitrag #14608
Avatar
Mitglied seit: 31.10.2006
Forenbeiträge: 91
Besuche: 418
und wenn du es genauer berechnen willst und auch einen leistungsstarken rechner hast, dann würde ich den code von meinem link codebeispiel überarbeiten. zuerst lädst du dir die datenbank mit allen geodaten von opengeodb runter. danach machst du eine schleife die die entfernung zwischen dem ausgewählten punkt und den restlichen punkten ausrechnet. und alle entfernungen die kleiner als der angegebene umkreis ist soll er dir ausgeben.