[QUIZ#10] OnlyFoo (Python)

OnlyFoo

Erfahrenes Mitglied
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:
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 points

Wenn 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__()
 
Zurück