[QUIZ#10] Einmal über den Atlantik und zurück

[Matthias Reitinger]

Quiz #10
Einmal über den Atlantik und zurück

Regeln
Die Regeln und der Ablauf der Quizrunde können in der entsprechenden Ankündigung eingesehen werden. Bitte lest sie euch aufmerksam durch, da sie alle wichtigen Informationen enthält. Lösungsansätze können und dürfen auch schon vorab untereinander ausgetauscht und diskutiert werden, allerdings nicht öffentlich im Forum. Verwendet stattdessen bitte private Nachrichten oder schaut im Chat vorbei.

Abgabe
Die Abgabe erfolgt wie immer im Abgabeforum. Abgabefrist ist voraussichtlich Samstag, der 10. Oktober 2009 um ca. 20 Uhr.

Das Problem
Charles Lindbergh möchte den Atlantik überqueren, doch fehlt ihm noch die korrekte Route. Schließlich weiß jeder, dass die gerade Linie auf einer Plattkarte meist nicht die kürzeste Route ist.

Die Aufgabe
Ziel ist es also, Lindbergh unter die Arme zu greifen. Es soll die kürzeste Flugroute zwischen zwei Orten berechnet werden, die jeweils durch ihre geographische Lage gegeben sind. Die Lage ist ein Koordinatentupel bestehend aus Breitengrad und Längengrad.

Eingabeformat

Breite 1 Länge 1 Ortsname 1
Breite 2 Länge 2 Ortsname 2

Breiten- und Längenangaben erfolgen jeweils in Grad (G), Minuten (M) und Sekunden (S) (in der sogenannten sexagesimalen Darstellung, siehe http://de.wikipedia.org/wiki/Grad_(Winkel)):

G°M'S"

G, M und S sind dabei nichtnegative Ganzzahlen. Einzelne Komponenten können von hinten her auch weggelassen werden. Gültige Formate sind also auch

G°M'

oder

G°

. Auf die Gradangabe folgt noch eine Richtungsangabe. Für die Breite ist das entweder N (Nord) oder S (Süd), für die Länge entsprechend W (West) oder O (Ost).

Beispiel
Route von New York nach Hamburg:

40°43'N 74°W New York
53°33'N 10°O Hamburg

Ausgabe
Die Ausgabe soll in Bildform erfolgen. Hierzu würde sich wieder das SVG-Format anbieten. Folgendes Template könnt ihr dazu verwenden:

<?xml version="1.0" ?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
    "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg version="1.1"
    xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
    width="1024" height="512" stroke="red" fill="none" 
    viewBox="-180 -90 360 180" stroke-width="0.3">
    
    <defs>
        <g id='Kreuz'>
            <line x1="-1" y1="-1" x2="1" y2="1" />
            <line x1="-1" y1="1" x2="1" y2="-1" />
        </g>
    </defs>
    
    <image x="-180" y="-90" width="360" height="180" xlink:href="http://veimages.gsfc.nasa.gov/2430/land_ocean_ice_2048.jpg" />
    
    [Inhalt]
</svg>

Koordinaten können nun in Gradeinheiten angegeben werden. Ein Kreuz für New York würde man z.B. so zeichnen:

<!-- New York, 40°43'N, 74°W -->
<use xlink:href="#Kreuz" transform="translate(-74.00 -40.71)" />

Strecken oder Streckenzüge könnt ihr mit den entsprechenden Tags zeichnen.

Beispiel
Die Route von New York nach Hamburg könnte damit so aussehen:


Erweiterung 1
Charles möchte nun, nachdem er den Atlantik überquert hat, gleich weiter nach Moskau (55°45'06"N, 37°37'04"O) und Sydney (33°51'35"S, 151°12'40"O) fliegen. Erweiter das Programm so, dass es eine Serie von Orten entgegen nimmt und die Route immer ergänzt.

Beispiel

40°43'N 74°W New York
53°33'N 10°O Hamburg
55°45'06"N 37°37'04"O Moskau
33°51'36"S 151°12'40"O Sydney

Ergebnis:


Erweiterung 2
Das Programm soll nun so erweitert werden, dass es Start und Zielort gefolgt von einer Leerzeile engegen nimmt. Danach sollen beliebig viele weitere Orte eingegeben werden können. Das Programm soll dann automatisch die kürzeste Route über alle Punkte vom Start zum Ziel finden.

Beispiel

40°43'N 74°W New York
53°33'N 10°O Hamburg

55°45'06"N 37°37'04"O Moskau
33°51'36"S 151°12'40"O Sydney
41°53'N 12°29'O Rom
30°3'N 31°14'O Kairo

Ausgabe ist vermutlich eine Route, die etwa New York -> Sydney -> Kairo -> Rom -> Moskau -> Hamburg lautet. Wer die richtige Antwort kennt, bitte melden

Ideen für zusätzliche Erweiterungen
Weitere Ideen wären z.B. die Ausgabe der Länge der Flugroute, oder ein automatisches Ermitteln der Koordinaten zu einem Ort (Datenbank, Webdienst, Wikipedia...).

Weitere Beispiele
Von Moskau nach Sydney:

55°45'06"N 37°37'04"O Moskau
33°51'36"S 151°12"40"O Sydney

Eine kleine Weltreise:

48°8'N     11°34'O     München
25°15'N    55°18'O     Dubai
39°54'50"N 116°23'30"O Peking
33°51'S    151°12'O    Sydney
26°12'S    28°4'O      Johannesburg
22°54'S    43°12'W     Rio de Janeiro
37°47'N    122°25'W    San Francisco
40°43'N    74°0'W      New York
51°31'N    0°7'W       London
48°8'N     11°34'O     München

Test für einen Sonderfall:

33°51'S    151°12'O    Sydney
37°47'N    122°25'W    San Francisco
39°54'50"N 116°23'30"O Peking

Und jetzt viel Spaß beim Implementieren!

Herzlichen Dank an OnlyFoo für die Einsendung dieser Aufgabe!

 

[zeja]

Hab ich das richtig verstanden, dass es im ersten Teil der Aufgabe nur ums parsen der Eingabe und schlichtes "einzeichnen" der Koordinaten auf der Karte geht?

 

[Matthias Reitinger]

Nein, die Aufgabe besteht schon darin, die Flugroute zu berechnen und einzuzeichnen. Sonst wäre es ja fast schon ein bisschen zu einfach

Grüße, Matthias

 

[Matthias Reitinger]

Hallo zusammen,

da die Aufgabe diesmal recht recherche-intensiv zu sein scheint, stell ich mal noch ein paar zusätzliche Links rein.

• Die kürzeste Verbindungsstrecke auf einer Kugel nennt man Orthodrome. (Es kann hier vereinfachend angenommen werden, dass die Erde eine Kugel ist.)
• Orthodrome liegen immer auf Großkreisen.
• Der Abstand zweier Punkte auf einer Kugel lässt sich mit der Haversine-Formel berechnen.
• Viele interessante Formeln findet man bei http://www.movable-type.co.uk/scripts/latlong.html
• Entfernungsberechnung
• Great Circle Mapper: praktisch für Plausibilitätschecks eurer Implementierung

Grüße, Matthias

 

[mAu]

Hört sich spannend an. Sollte ich Zeit finden, werd ich da auch mal was basteln

 

[zeja]

Hmm... allerdings ist es mit den Formeln doch recht einfach Hab vorher ganz schön gesucht. Leider hatten wir das auch nie in der Schule.

 

[Matthias Reitinger]

Hmm... allerdings ist es mit den Formeln doch recht einfach

Dann denk dir noch ein paar Erweiterungen aus, um das ganze für dich interessanter zu gestalten Die automatische Umwandlung von Ortsname zu geographischer Lage ist aber dank der Google Maps API auch erstaunlich einfach.

Ich hab im Ursprungspost mal noch ein weiteres Beispiel hinzugefügt (Weltreise). [edit]Und noch ein Beispiel, das einen Sonderfall aufzeigt.[/edit]

Grüße, Matthias

 

[Chumper]

Aber ein sehr interessantes Quiz diesmal, Danke dafür.
Wenn ich Zeit habe, reiche ich aus Kanada was nach

 

[dadom110]

Ich finde es ja nicht so einfach
Wie zeichnet ich denn die Strecke zwischen den Punkten, ohne einen ganzen Kreis ab zu bilden?

Darf man Hilfe auf den Aufgaben anfordern ?

Grüße
Dom

 

[Matthias Reitinger]

Ich finde es ja nicht so einfach
Wie zeichnet ich denn die Strecke zwischen den Punkten, ohne einen ganzen Kreis ab zu bilden?

Wenn man einen Großkreis auf einer Plattkarte einzeichnet, kommt im Allgemeinen kein Kreis raus. Das sieht man beispielsweise bei der Route von Moskau nach Sydney:
Anhang anzeigen 49231

Dein Ansatz ist also leider nicht ganz richtig. Aber schau dir mal die Formeln auf http://www.movable-type.co.uk/scripts/latlong.html an, damit solltest du denk ich weiterkommen

Grüße, Matthias