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

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
Code:
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)):
Code:
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
Code:
G°M'
oder
Code:
. 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:
Code:
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:
<?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:
XML:
<!-- 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:
route-nwha.jpg

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
Code:
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:
quiz-ext1.jpg

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
Code:
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:
Code:
55°45'06"N 37°37'04"O Moskau
33°51'36"S 151°12"40"O Sydney
route-mosy.jpg

Eine kleine Weltreise:
Code:
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
weltreise.jpg

Test für einen Sonderfall:
Code:
33°51'S    151°12'O    Sydney
37°47'N    122°25'W    San Francisco
39°54'50"N 116°23'30"O Peking
wrap.jpg


Und jetzt viel Spaß beim Implementieren!

Herzlichen Dank an OnlyFoo für die Einsendung dieser Aufgabe!
 
Zuletzt bearbeitet von einem Moderator:

zeja

Erfahrenes Mitglied
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?
 
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
 
Hallo zusammen,

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


Grüße, Matthias
 

zeja

Erfahrenes Mitglied
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.
 
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
 
Zuletzt bearbeitet:

Chumper

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

dadom110

Erfahrenes Mitglied
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
 
Zuletzt bearbeitet:
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