Hallo,
ich habe eine Liste von 2000 Orten in Deutschland bei denen bei vielen der Längen- und der Breitengrad bekannt ist. Von allen Orten ist der Abstand zwischen den Orten bekannt. Gibt es schon einen Algorithmus, der anhand der Länge und den bekannten Koordinaten der Orte auf die Koordinaten der unbekannten Orte schließen kann? Als Grundlage mit für mich der euklidische Abstand d=sqrt((x2-x1)^2+(y2-y1)^2). Blöderweise gibt es wenn ich einen Ort weiß und den anderen Ort nicht immer zwei unbekannte. Ist jemand schonmal über so eine Fragestellung gstolpert?
Längen-/Breitengrade ermitteln
Du musst triangulieren. Ein Ort ohne Koordinaten kann nur durch zwei Abstände zu welchen mit bestimmt werden. Der Algorithmus muss sukzessive alle Orte mit Koordinaten ausstatten, bei denen das möglich ist. Und dadurch dann hoffentlich selbst wieder weitere Orte “freischalten”, bis alle bestimmt sind. Es ist aber allgemein nicht garantiert, dass das klappt. Aber wenn es aufgeht, erreicht das Vorgehen das Ziel.
Das geht und ist eine typische Navigationsaufgabe (der "unbekannte Ort" ist in diesem Fall das Schiff):
Wenn du die Koordinaten von einem Ort (O1) kennst, sowie die Entfernung von diesem zu einem anderen Ort (Ou), dessen Koordinaten du nicht kennst, dann kannst du um O1 einen Kreis mit dem Radius der Entfernung zu Ou ziehen. Ou liegt dann irgendwo auf dem Kreis.
Nun brauchst du einen zweiten Ort (O2) mit bekannten Koordinaten und bekannter Entfernung zu Ou. Auch um diesen ziehst du einen Kreis. Die Kreise um O1 und O2 haben nun zwei Schnittpunkte. Auf einem von diesen liegt Ou. Sofern sich eine vernünftige Annahme über die erwarteten Koordinaten von Ou machen lässt, genügt das üblicherweise bereits.
Andernfalls nimmst du noch einen dritten Kreis um O3 hinzu. Dann gibt es nur noch einen gemeinsamen Schnittpunkt aller drei Kreise. Die Koordinaten dieses Schnittpunktes sind dann die von Ou.
Mit Bleistift und Zirkel ist die Lösung trivial. Algorithmisch könntest du um O1 und O2 z.B. je 360 (je nach gewünschter Auflösung auch mehr oder weniger) Koordinaten berechnen und die zwei Punktepaare bestimmen, bei denen der Abstand am geringsten ausfällt. Von diesen nimmst du den Mittelpunkt der Verbindungsgeraden als Koordinaten. Dann nimmst du einen dritten Ort O3 und schaust, welche der beiden zuvor ermittelten Koordinaten zu der von O3 bekannten Entfernung passt. Dann hast du zwar noch nicht die exakten Koordinaten, bist aber schon nah dran.
Wenn du zwei Orte O1 und O2 wählst, deren Abstand voneinander größer als der zu Ou ist, dann lässt sich die Berechnung noch beschleunigen, denn dann brauchst du nur noch Kreissegmente zu betrachten.
Wenn du die Koordinaten von einem Ort (O1) kennst, sowie die Entfernung von diesem zu einem anderen Ort (Ou), dessen Koordinaten du nicht kennst, dann kannst du um O1 einen Kreis mit dem Radius der Entfernung zu Ou ziehen. Ou liegt dann irgendwo auf dem Kreis.
Nun brauchst du einen zweiten Ort (O2) mit bekannten Koordinaten und bekannter Entfernung zu Ou. Auch um diesen ziehst du einen Kreis. Die Kreise um O1 und O2 haben nun zwei Schnittpunkte. Auf einem von diesen liegt Ou. Sofern sich eine vernünftige Annahme über die erwarteten Koordinaten von Ou machen lässt, genügt das üblicherweise bereits.
Andernfalls nimmst du noch einen dritten Kreis um O3 hinzu. Dann gibt es nur noch einen gemeinsamen Schnittpunkt aller drei Kreise. Die Koordinaten dieses Schnittpunktes sind dann die von Ou.
Mit Bleistift und Zirkel ist die Lösung trivial. Algorithmisch könntest du um O1 und O2 z.B. je 360 (je nach gewünschter Auflösung auch mehr oder weniger) Koordinaten berechnen und die zwei Punktepaare bestimmen, bei denen der Abstand am geringsten ausfällt. Von diesen nimmst du den Mittelpunkt der Verbindungsgeraden als Koordinaten. Dann nimmst du einen dritten Ort O3 und schaust, welche der beiden zuvor ermittelten Koordinaten zu der von O3 bekannten Entfernung passt. Dann hast du zwar noch nicht die exakten Koordinaten, bist aber schon nah dran.
Wenn du zwei Orte O1 und O2 wählst, deren Abstand voneinander größer als der zu Ou ist, dann lässt sich die Berechnung noch beschleunigen, denn dann brauchst du nur noch Kreissegmente zu betrachten.
-
noisefloor
- User
- Beiträge: 4195
- Registriert: Mittwoch 17. Oktober 2007, 21:40
- Wohnort: WW
- Kontaktdaten:
Hallo,
Gruß, noisefloor
Richitg. Wenn man richtiger Rechnen will braucht man die Haversine Formel. Wobei das a) am grundsätzlichen Vorgehen nichts ändert und b) die der Rechenfehler, der man sich einbaut, wenn man sich nur innerhalb von Deutschland bewegt, IMHO vernachlässigbar klein, mit man mit euklidischem Abstand statt Haversine rechnet.Und natürlich muss man noch beachten, dass die Erde nicht flach ist.
Gruß, noisefloor