Hallo,

in meiner Anwendung habe ich die Möglichkeit, mir in Abhängigkeit von meinem eigenen Standort die nächsten Standorte von Organisationen/Filialen anzuzeigen. Dabei muss der Benutzer seinen eigenen Standort per GPS-Koordinaten angeben und über eine 'einfache' SQL-Abfragen werden die nächstliegenden Standorte bestimmt (ca. 700 Standorte über Deutschland verteilt, GPS-Koordinaten liegen vor).

Jetzt würde ich mir aber gerne eine entsprechende Karte errechnen lasse, d.h. um jeden Standort wird dessen 'Einzugsfläche' markiert ... aber irgendwie ist das ein nicht triviales Problem. Habe schon viel im www gesucht aber nichts gefunden ... wahrscheinlich fehlt mir ein passendes Stichwort. Auch meine 'menschliche Vorgehensweis' habe ich bisher nicht in eine Prog.-Sprache übersetzten können.

Das ganze ist doch eigentlich ein 'simples' mathematisches Problem. Hat vielleicht irgendwer ein passendes Stichwort, Quelle oder einen Tipp für mich?

Was genau ist denn das Problem? Den Radius des Einzugsbereiches zu finden? Oder Markierungen in einer Karte?

Hagen+2008-05-13 23:13:12--

Das ganze ist doch eigentlich ein 'simples' mathematisches Problem. Hat vielleicht irgendwer ein passendes Stichwort, Quelle oder einen Tipp für mich?

Suchvorschläge:
Abstand, Norm, Geokoordinaten, GPS, Sphärische Trigonometrie

Ich würde es so versuchen:

Schau mal nach wie viel Bogenminuten durchschnittlich ein Kilometer sind.

Als erstes ermittle die möglichen Kandidaten indem du ein Rechteck von c° Länge, c°Breite aufspannst in dessen Mitte die GPS Koordinate sitzt. Ermittle welche möglichen Ziele sich in diesem Rechteck sitzen. Danach berechnest du den Abstand der Gefundenen Orte zur GPS Position. Ist der Abstand geringer als x km kann er genommen werden.

Nachteil dabei ist, dass es zu einer Verzerrung kommt, je nach dem wo du die Koordinaten anlegst und wie groß die Strecke ist. Ab hier wird es richtig kompliziert, wenn du diese Verzerrungen Ausgleichen willst.

Könnte dir helfen:
http://home.mathematik.uni-freiburg.de/didaktik/material/brandt.html
http://www.new-media-engineering.com/entfernung/berechnung.php
http://www.koordinaten.de/informationen/formel.shtml
http://www.php-resource.de/forum/printthread.php?s=315dd7b0200b79ee870ad6ca84e953da&threadid=5180
http://kanadier.gps-info.de/d-koordinaten.htm

topeg+2008-05-14 07:09:42--

[...]
Nachteil dabei ist, dass es zu einer Verzerrung kommt, je nach dem wo du die Koordinaten anlegst und wie groß die Strecke ist. Ab hier wird es richtig kompliziert, wenn du diese Verzerrungen Ausgleichen willst.
[...]

Wenn man's genau haben möchte, würde ich die Vincenty-Formeln [1] zur Berechnung von Distanzen auf einer ellipsoidalen Oberfläche empfehlen -- die Genauigkeit ist für alle gängigen geodätischen Zwecke ausreichend und die Formel ist einfache sphärische Trigonometrie...


[1] Beschreibung zum Beispiel hier: http://www.movable-type.co.uk/scripts/latlong-vincenty.html

Danke schon mal, aber die Hilfen gehen ein bischen in die falsche Richtung.



Die X sind 4 Filialen. Diesen sollen in diesem Beispiel das Quadrat unter sich gleichmäßig aufteilen.

Der Mensch sieht sofort: das Quadrat vierteln. Wie mache ich das aber per Algorithmus? In der Realität habe ich ein paar mehr Punkte und diese sind leider nicht so schön angeordnet.

Hagen+2008-05-14 21:55:16--

Danke schon mal, aber die Hilfen gehen ein bischen in die falsche Richtung.

herrlich wie man sich immer anstrengt, aber in die falsche Richtung orakelt ... :-)

Schritt 1: Hilfe die Frage im Dialog verständlich zu formulieren.
a) Hyphotesen zur Fragestellung bilden:

Du hast eine Ebene mit n Stationen und du möchtest diese in Bereiche aufteilen, sodass die Punkte eines Bereiches B_x am nächsten zur Station x liegen. Wie ermittelt man diese Bereiche?

b) Ist das deine Frage?

c) Bitte keine Thesen äußern bis Fragestellung klar formuliert...


EDIT: hoffentlich ist das jetzt die richtige Frage, ich hab ne Idee ...:-)

KurtZ+2008-05-14 22:08:16--

EDIT: hoffentlich ist das jetzt die richtige Frage, ich hab ne Idee ...:-)

naja da "meine" Idee sogar bei Wikipedia beschrieben ist, riskiere ich nichts wenn ich einfach jetzt den Link poste zuVoronoi-Diagramme.

Das erspart mir jetzt auch länger über Dreiecksnetze (Delaunay-Triangulation [*]) und [url=http://de.wikipedia.org/wiki/Mittelsenkrechte]Mittelsenkrechte[/url] zu theoretisieren. Nachtrag: [*] die wirklich nicht trivial zu proggen ist, so einfach die Idee auch ist.

Hagen+2008-05-14 21:55:16--

Der Mensch sieht sofort: das Quadrat vierteln. Wie mache ich das aber per Algorithmus? In der Realität habe ich ein paar mehr Punkte und diese sind leider nicht so schön angeordnet.

"Ganz einfach": Du legst zwischen zwei Filialen eine (unsichtbare) Linie, und die Mittelsenkrechte dieser Linie ist die Trennlinie zwischen den beiden Gebieten.

Das machst du für alle Paare von benachbarten Filialen, und hast damit ein Polygon um jede Filiale definiert.

Das ist nicht 100% trivial, aber wenn du dir ein bisschen was zu geometrischen Algorithmen durchliest (Schnitte und Polygone berechnen, Sortieren in Bereiche) wirst du das schon hinkriegen.

moritz+2008-05-15 00:20:20--

"Ganz einfach": Du legst zwischen zwei Filialen eine (unsichtbare) Linie, und die Mittelsenkrechte dieser Linie ist die Trennlinie zwischen den beiden Gebieten.

Das machst du für alle Paare von benachbarten Filialen, und hast damit ein Polygon um jede Filiale definiert.

Das ist nicht 100% trivial, aber wenn du dir ein bisschen was zu geometrischen Algorithmen durchliest (Schnitte und Polygone berechnen, Sortieren in Bereiche) wirst du das schon hinkriegen.

Das entspricht schon mehr dem, was ich gesucht habe. So in etwas waren auch meine Gedanken. Ich befürchte nur, das wird nicht ganz einfach. Mal sehen, was ich noch (er-) finde.