Soo, etwas verspätet, hatte garnicht mitbekommen, dass das der Contest online war... danke an Matthias dafür nochmal... Und auch für die Google-Geocode-Funktion, die ich im Prinzip übernommen habe...
Meine Berechnung der Route läuft im Wesentlichen so:
Wenn ich das richtig sehe haben damit fast alle, die abgegeben haben, einen anderen Lösungsansatz gewählt...
Komplettes Python Script:
Meine Berechnung der Route läuft im Wesentlichen so:
Python:
def route( start, end, steps = 50 ):
# Punkte auf der Erd-Kugel bestimmen
v_start = Vector.from_location( start )
v_end = Vector.from_location( end )
# Direkten Verbindungsvektor 'durch' die Erde finden
v_dir = v_end - v_start
# Stückweise den Verbindungsvektor abgehen
points = []
for step in xrange( steps + 1 ):
frac = step / float(steps)
# Einen Vector vom Mittelpunkt der Erde finden,
# der durch den direkten Verbindungsvektor geht
# und diesen bis zur Erdoberfläche verlängern.
v_current = (v_start + (v_dir * frac)).normalize()
# Nun haben wir einen Punkt, den wir in
# unsere Zeichnung einfügen können.
points.append( (v_current.lo, v_current.la) )
# Ferdisch!
return pointsWenn ich das richtig sehe haben damit fast alle, die abgegeben haben, einen anderen Lösungsansatz gewählt...
Komplettes Python Script:
Python:
# -*- encoding: utf8 -*-
import re
import sys
import math
import urllib
def __main__():
# Alle Zeilen von der Standard-Eingabe lesen
lines = sys.stdin.readlines()
if not lines:
return
# Alle Zeilen parsen
entries = [parse_location_line(line) for line in lines if line.strip()]
# SVG erzeugen
svg = [ svg_start() ]
svg_layer = []
last_loc, last_name = None, None
for loc, name in entries:
# Kreuz und Name zeichnen
svg_layer.append( svg_cross( *loc ) )
svg_layer.append( svg_text( loc.lo - 5, loc.la + 5, name ) )
# Wenn wir schon eine Position hatten, zeichne
# die Route ein
if last_loc:
for points in route( last_loc, loc ):
svg.append( svg_polyline( points ) )
# setzte "letzte" Position
last_loc, last_name = loc, name
# SVG ausgeben
svg.append( "".join( svg_layer ) )
svg.append( svg_end() )
print "".join( svg )
#
# Berechnet eine Route zwischen 'start' und 'end'
#
def route( start, end, steps = 50 ):
# Punkte auf der Erd-Kugel bestimmen
v_start = Vector.from_location( start )
v_end = Vector.from_location( end )
# Direkter Verbindungsvektor 'durch' die Erde finden
v_dir = v_end - v_start
# Stückweise die Route abgehen
points = []
parts = []
last_sgn = 0
for step in xrange( steps + 1 ):
frac = step / float(steps)
# Einen Vector vom Mittelpunkt der Erde finden,
# der durch den direkten Verbindungsvektor geht
# und diesen bis zur Erdoberfläche verlängern.
v_current = (v_start + (v_dir * frac)).normalize()
# Schauen ob wir über einen Rand übertreten haben. Nämlich genau
# dann, wenn sich das Vorzeichen der Länge geändert hat,
# und der Betrag der länge > 90° ist
sgn = -1 if v_current.lo < 0 else 1
if last_sgn and abs( v_current.lo ) > 90 and sgn != last_sgn:
points.append( Location(v_current.lo - 360 * sgn, v_current.la) )
parts.append( points )
# Neue Punktmenge beginnen
points = []
points.append( Location(v_current.lo + 360 * sgn, v_current.la) )
# last_sgn updaten
last_sgn = sgn
# Nun haben wir einen Punkt, den wir in
# unsere Zeichnung einfügen können.
points.append( (v_current.lo, v_current.la) )
# Ferdisch!
parts.append( points )
return parts
#
# Zerlegt eine Zeile der Form "lat lon name" und gibt ein tuple
# mit (Location, Name) zurück
#
def parse_location_line( line ):
line = line.strip()
if line.startswith( "!" ):
name = line[1:].strip()
return (ask_mother_google( name ), name)
parts = filter( None, line.split( " " ) )
if len( parts ) < 3:
raise Exception( "Ungültige Zeile: " + line )
return (Location( parts[1], parts[0] ), " ".join( parts[2:] ))
#
# Fragt Google nach den Koordinaten für einen gegeben Ort
#
def ask_mother_google( what ):
if what in ask_mother_google.cache:
return ask_mother_google.cache[what]
# URL zusammensetzten
url = "http://maps.google.com/maps/geo?" + urllib.urlencode({
"output": "csv",
"q": what
})
# Google fragen
parts = urllib.urlopen( url ).read().split(",")
# Fehlerhaftes Ergebnis?
if len( parts ) != 4 or parts[0] != "200":
raise IOError( "Der Ort '%s' wurde nicht gefunden!" % what )
# Breitengrad invertieren... Google ist da anderer Meinung als ich ;)
result = Location( float(parts[3]), -float(parts[2]) )
ask_mother_google.cache[what] = result
return result
# Mehrfache Anfragen cachen
ask_mother_google.cache = {}
#
# Wandelt eine Angabe in Grad, Minuten und Sekunden in einen Winkel in
# Grad um.
#
def parse_degree( input ):
# Mit regulärem Ausdruck aufteilen
match = re.findall( r'([0-9]+)°(?:([0-9]+)\')?(?:([0-9]+)")?([NOSWE])', input )
if not match:
raise Exception( "Ungültige Gradangabe: " + input )
g, m, s, cardinal = match[0]
# Gradwert berechnen
deg = float( g )
if m: deg += float(m) / 60
if s: deg += float(s) / 3600
# Norden oder Westen invertieren
if cardinal in 'NW': deg *= -1
return deg
#
# Ein Tupel welches das erste und zweite Element mittels .lo und .la
# zurück gibt
#
class Location( tuple ):
def __new__( cls, lo, la ):
if isinstance( lo, str): lo = parse_degree( lo )
if isinstance( la, str): la = parse_degree( la )
return tuple.__new__( cls, (lo, la) )
@property
def lo( self ):
return self[0]
@property
def la( self ):
return self[1]
#
# Eine kleine Vektor Klasse, zum einfachen Rechnen mit Vektoren
#
class Vector( tuple ):
def __new__( cls, x, y, z ):
return tuple.__new__( cls, (x, y, z) )
def __add__( self, other ):
return Vector( *map( lambda a, b: a + b, self, other ) )
def __sub__( self, other ):
return Vector( *map( lambda a, b: a - b, self, other ) )
def __mul__( self, scale ):
return Vector( *[a * scale for a in self] )
def normalize( self ):
return self * (1 / self.length)
@property
def length( self ):
return math.sqrt( sum( [a * a for a in self] ) )
@property
def la( self ):
return math.degrees( math.asin( self.y ) )
@property
def lo( self ):
return math.degrees( math.atan2( self.x, self.z ) )
@property
def x( self ): return self[0]
@property
def y( self ): return self[1]
@property
def z( self ): return self[2]
@staticmethod
def from_location( loc ):
lo = math.radians( loc.lo )
la = math.radians( loc.la )
return Vector(
math.sin( lo ) * math.cos( la ),
math.sin( la ),
math.cos( lo ) * math.cos( la ) )
def svg_start():
return '''<?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" /> -->
<image x="-180" y="-90" width="360" height="180" xlink:href="world.jpg" />
'''
def svg_cross( x, y ):
return "<use xlink:href='#Kreuz' transform='translate(%f %f)' />" % (x, y)
def svg_polyline( points ):
return "<polyline points='%s' />" % " ".join( [str(c) for p in points for c in p] )
def svg_text( x, y, text ):
return "<text x='%f' y='%f' fill='#ff0' stroke='none' font-size='5'>%s</text>" % (x, y, text)
def svg_end():
return "</svg>"
if __name__ == '__main__':
__main__()
Danke jedenfalls dass du noch abgegeben hast!