[QUIZ#10] Matthias Reitinger (Ruby)

Hallo zusammen,

hier meine Lösung in Ruby. Neben der Erweiterung 1 habe ich auch noch die automatische Ermittlung der geographischen Lage anhand eines Ortsnamens implementiert. Die Dokumentation findet ihr nebenan, den Quellcode hier:
Ruby:
#!/usr/bin/env ruby

# Dieses Programm ist eine Lösung zur
# {10. Runde}[http://www.tutorials.de/forum/diskussion/348207-quiz-10-einmal-ueber-den-atlantik-und-zurueck.html]
# des {Coding Quiz}[http://www.tutorials.de/forum/coding-quiz/] auf
# tutorials.de[http://www.tutorials.de/].
#
# Erwartet auf der Standardeingabe eine Reihe von Stationen für die Route.
# Jede Station steht in einer eigenen Zeile. Für eine Station sind zwei
# verschiedene Formate zulässig:
# <tt>ggg°mm'ss"N/S ggg°mm'ss"W/O Name</tt>::
#   Angabe der Lage durch gegraphische Breite und Länge. Beispiel:
#   <tt>48°8'0"N 11°34'0"O München</tt>
# <tt>!Name</tt>::
#   Angabe des Ortsnamens. Es wird versucht, automatisch über einen Webdienst
#   die geographische Lage zu ermitteln. Beispiel: <tt>!Sydney</tt>
# Zeilen, die nicht diesem Format entsprechen, werden ignoriert. Die Formate
# können in einer Eingabe beliebig gemischt werden. Wichtig ist allerdings,
# dass die Eingabecodierung ISO-8859-1 ist.
#
# Das Programm errechnet eine Flugroute durch die einzelnen Stationen und gibt
# diese im SVG-Format auf der Standardausgabe aus.
#
# Beispielaufruf:
#   ~> cat muc-txl.route
#   48°8'N 11°34'O München
#   !Berlin
#   
#   ~> ./quiz010.rb <muc-txl.route
#   <?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="land_ocean_ice_2048.jpg" />
#   
#     <use xlink:href="#Kreuz" transform="translate(11.57 -48.13)" />
#   <use xlink:href="#Kreuz" transform="translate(13.41 -52.52)" />
#   <polyline points="11.57 -48.13, 11.78 -48.68, 12.00 -49.23, 12.22 -49.78, 12.45 -50.33, 12.68 -50.88, 12.92 -51.43, 13.16 -51.98, 13.41 -52.52" />
#   
#   </svg>
#   
#   ~>
#
# Author::  Matthias Reitinger
# License:: Beerware

require 'enumerator'
require 'net/http'

# Koordinate auf einer Kugel, definiert durch geographische Länge und Breite.
class Coordinate
  attr_reader :lat, :lng

  # +lat+ (Breite) und +lng+ (Länge) müssen in Grad angegeben werden.
  def initialize(lat, lng)
    @lat = lat
    @lng = lng
  end

  # Geographische Breite im Bogenmaß.
  def lat_rad
    @lat * Math::PI / 180.0
  end

  # Geographische Länge im Bogenmaß.
  def lng_rad
    @lng * Math::PI / 180.0
  end

  # Berechnet die Distanz zu +other+ in km. Dabei wird davon ausgegangen, dass
  # die Erde näherungsweise eine Kugel mit dem Radius 6.371km ist. Andere Radien
  # können über den Parameter +radius+ verwendet werden.
  def distance_to(other, radius=6371.0)
    # Siehe http://www.movable-type.co.uk/scripts/latlong.html (Distance)
    dlat = other.lat_rad - self.lat_rad
    dlng = other.lng_rad - self.lng_rad
    a = Math.sin(dlat*0.5) ** 2 +
        Math.cos(self.lat_rad) * Math.cos(other.lat_rad) *
        Math.sin(dlng*0.5) ** 2
    c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a))
    radius * c
  end

  # Berechnet den Mittelpunkt der kürzesten Strecke zwischen +self+ und +other+.
  # Das Ergebnis wird als neue Instanz von Coordinate zurückgegeben.
  def midpoint(other)
    # Siehe http://www.movable-type.co.uk/scripts/latlong.html (Midpoint)
    dlng = other.lng_rad - self.lng_rad
    bx = Math.cos(other.lat_rad) * Math.cos(dlng)
    by = Math.cos(other.lat_rad) * Math.sin(dlng)
    lat3 = Math.atan2(Math.sin(self.lat_rad) + Math.sin(other.lat_rad),
                      Math.sqrt((Math.cos(self.lat_rad) + bx) *
                                (Math.cos(self.lat_rad) + bx) + by*by))
    lng3 = self.lng_rad + Math.atan2(by, Math.cos(self.lat_rad) + bx)
    Coordinate.new(lat3 * 180.0 / Math::PI,
                   lng3 * 180.0 / Math::PI)
  end

  # Berechnet die kürzeste Route zwischen +self+ und +destination+.
  # Zurückgegeben wird ein Array von auf der Route liegenden Koordinaten,
  # aufsteigend sortiert nach dem Abstand von +self+. Der Parameter +max_dist+
  # bestimmt die größte erlaubte Entfernung in km zwischen zwei aufeinander
  # folgenden Koordinaten.
  def route_to(destination, max_dist=100.0)
    if self.distance_to(destination) <= max_dist
      [self, destination]
    else
      mid = self.midpoint(destination)
      self.route_to(mid, max_dist) + mid.route_to(destination, max_dist)[1..-1]
    end
  end

  # Gibt eine Stringdarstellung für die SVG-Ausgabe zurück.
  def to_svg_coord
    x, y = @lng, -@lat
    "%.2f %.2f" % [x, y]
  end

  # Gibt die Koordinaten in kanonischer Darstellung zurück. D.h. die Breite
  # wird auf den Bereich -90..90 eingeschränkt, die Höhe in den Bereich
  # -180..180 gebracht.
  def canonical
    if (-180.0..180.0).include?(@lng) && (-90.0..90.0).include?(@lat)
      self
    else
      lat, lng = @lat, @lng
      lat = -90.0 if lat < -90.0
      lat =  90.0 if lat > 90.0
      lng += 360.0 while lng < -180.0
      lng -= 360.0 while lng >  180.0
      Coordinate.new(lat, lng)
    end
  end
end


# Eine Ortsangabe, bestehend aus Name und Koordinate.
class Location
  attr_reader :name, :coordinate

  def initialize(name, coord)
    @name = name
    @coordinate = coord
  end

  # Interpretiert einen String im Format <tt>48°8'0"N 11°34'0"O München</tt>
  # (Beispiel) und gibt eine entsprechendes Location Objekt zurück.
  def self.parse(str)
    lat_str, lng_str, name = str.split(/\s+/, 3)
    lat = parse_degrees(lat_str) or raise "Invalid format: #{lat_str}"
    lng = parse_degrees(lng_str) or raise "Invalid format: #{lng_str}"
    coord = Coordinate.new(lat, lng).canonical
    Location.new(name, coord)
  end

  # Versucht die geographische Lage des Ortes +name+ zu bestimmen und gibt bei
  # Erfolg eine entsprechende Instanz von +Location+ zurück. Verwendet die
  # Google Maps API und benötigt deshalb eine bestehende Internet-Verbindung.
  def self.from_name(name)
    # http://code.google.com/intl/de-DE/apis/maps/documentation/services.html#Geocoding_Direct
    uri = URI.parse("http://maps.google.com/maps/geo?output=csv&q=")
    uri.query += URI.encode(name)
    result = Net::HTTP.get(uri)
    status, accuracy, lat, lng = result.split(",")
    raise "Location named '#{name}' not found" if status != "200"
    coord = Coordinate.new(lat.to_f, lng.to_f).canonical
    Location.new(name, coord)
  end

  # Liefert die kürzeste Route zwischen +self+ und +destination+ zurück.
  # Siehe Coordinate#route_to.
  def route_to(destination, *args)
    @coordinate.route_to(destination.coordinate, *args)
  end

  def to_s
    "#{name} (#{coordinate.to_svg_coord})"
  end

 private
  def self.parse_degrees(str)
    if str =~ /
      \A          # Stringanfang
      (?:(\d+)°)  # Grad
      (?:(\d+)')? # Minuten (optional)
      (?:(\d+)")? # Sekunden (optional)
      ([NSWO])    # Richtung
      \Z          # Stringende
    /x
      degrees = $1.to_f + $2.to_f / 60.0 + $3.to_f / 3600.0
      if ['S', 'W'].include? $4
        degrees = -degrees
      end
      return degrees
    end
  end
end


# Nimmt mehrere Stationen entgegen und berechnet daraus eine Route, die in der
# angegebenen Reihenfolge die einzelnen Stationen abfliegt. Kann auch eine
# SVG-Ausgabe der Routen erstellen.
class RoutePlotter
  def initialize
    @stations = []
    @routes = []
  end

  # Fügt eine neue Station hinzu, die in Stringform vorliegt. Beginnt der
  # String mit einem <tt>!</tt> so wird der Rest des Strings als Ortsname
  # interpretiert. Andernfalls wird davon ausgegangen, dass es sich um eine
  # Koordinatenangabe handelt.
  def add_station(str)
    if str =~ /^!/
      @stations << Location::from_name(str[1..-1])
    else
      @stations << Location::parse(str)
    end
  end

  # Berechnet die Routen zwischen den einzelnen Stationen. Die Argumente werden
  # direkt an Location#route_to bzw. Coordinate#route_to weitergegeben.
  def calculate_routes(*args)
    @routes = []
    @stations.each_cons(2) do |source, destination|
      @routes << source.route_to(destination, *args)
    end
  end

  # Gibt die vorher mit calculate_routes berechneten Routen als Sequenz von
  # SVG <tt>polyline</tt>s zurück.
  def routes_svg
    svg = String.new
    @routes.each do |route|
      svg << route_svg(route)
    end
    svg
  end

  # Gibt ein SVG-Fragment zurück, in dem die Positionen der einzelnen Stationen
  # als Kreuze dargestellt sind.
  def stations_svg
    @stations.inject(String.new) do |svg, station|
      svg << "<use xlink:href=\"#Kreuz\" transform=\"translate("
      svg << station.coordinate.to_svg_coord
      svg << ")\" />\n"
    end
  end

 private
  # Berechnet die einzelnen SVG <tt>polyline</tt>s für eine Route.
  def route_svg(route)
    polylines = []
    coords = [route.first]
    route.each_cons(2) do |p1, p2|
      if (p1.lng >= -180.0 && p2.lng < -180.0) ||
         (p1.lng <=  180.0 && p2.lng >  180.0)
        # Verbindungsstrecke der beiden Punkte überquert Kartengrenze
        coords << p2
        polylines << coords
        if p2.lng < -180.0
          coords = [Coordinate.new(p1.lat, p1.lng + 360.0),
                    Coordinate.new(p2.lat, p2.lng + 360.0)]
        else
          coords = [Coordinate.new(p1.lat, p1.lng - 360.0),
                    Coordinate.new(p2.lat, p2.lng - 360.0)]
        end
      else
        coords << p2.canonical
      end
    end
    polylines << coords
    polylines.inject(String.new) do |svg, points|
      svg << "<polyline points=\""
      svg << points.map {|point| point.to_svg_coord}.join(", ")
      svg << "\" />\n"
    end
  end
end


#######################
# Main
#######################
if __FILE__ == $0
  plotter = RoutePlotter.new

  # Stationen einlesen und parsen
  while line = gets
    line.chomp!
    next if line.empty?
    begin
      plotter.add_station(line)
    rescue => e
      $stderr.puts "[WARN] Ignoring line in input: #{e}"
    end
  end

  # Routen berechnen
  plotter.calculate_routes

  # SVG-Fragmente erzeugen
  svg = String.new
  svg << plotter.stations_svg
  svg << plotter.routes_svg

  # Einsetzen in das Template und Ausgabe
  puts DATA.read.sub("[Inhalt]", svg)
end

# Es folgt das SVG-Template, auf das über +DATA.read+ zugegriffen wird.
__END__
<?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>
Da der Syntax-Highlighter anscheinend über den regulären Ausdruck stolpert, hier nochmal als Pastie: http://www.pastie.org/648414

Im Anhang befindet sich das „Komplettpaket“ mit dem Quellcode, Dokumentation im HTML-Format, einigen Routen und den entsprechenden SVG-Ausgaben. Die Inhalte sind auf unbestimmte Zeit auch unter http://home.in.tum.de/~reitinge/coding-quiz/10/ abrufbar.

Grüße, Matthias
 

Anhänge

  • 10.zip
    71,4 KB · Aufrufe: 19
Zuletzt bearbeitet:
Hallo,

nachdem ich jetzt die anderen Abgaben gesehen habe, sehe ich mich gezwungen, auch noch ein paar Worte zu meinem Ansatz zu verlieren ;)

Das Programm setzt sich aus drei Klassen zusammen. Coordinate kapselt eine geographische Lage (Breite und Höhe) und enthält auch den Algorithmus zur Ermittlung der kürzesten Route:
Ruby:
  # Berechnet die kürzeste Route zwischen +self+ und +destination+.
  # Zurückgegeben wird ein Array von auf der Route liegenden Koordinaten,
  # aufsteigend sortiert nach dem Abstand von +self+. Der Parameter +max_dist+
  # bestimmt die größte erlaubte Entfernung in km zwischen zwei aufeinander
  # folgenden Koordinaten.
  def route_to(destination, max_dist=100.0)
    if self.distance_to(destination) <= max_dist
      [self, destination]
    else
      mid = self.midpoint(destination)
      self.route_to(mid, max_dist) + mid.route_to(destination, max_dist)[1..-1]
    end
  end
Wie man sieht, habe ich hier einen rekursiv-adaptiven Ansatz gewählt. Die Wegpunkte auf der Route sollen höchstens eine bestimmte Distanz max_dist voneinander entfernt sein. Ist die Entfernung zwischen Start und Ziel bereits kleiner oder gleich der Maximaldistanz, kann einfach ein Array bestehend aus Start und Ziel zurückgegeben werden. Andernfalls wird der Mittelpunkt zwischen Start und Ziel berechnet. Dies geschieht mit der Midpoint-Formel, die ich einfach schamlos von http://www.movable-type.co.uk/scripts/latlong.html übernommen habe. Anschließend werden rekursiv die Route zwischen Start und Mittelpunkt sowie zwischen Mittelpunkt und Ziel berechnet. Die beiden Routen werden zur Gesamtroute zusammengefasst, wobei man beachten muss, dass der Mittelpunkt sowohl der Endpunkt der ersten als auch der Startpunkt der zweiten Route ist. Deshalb verwende ich bei der zweiten Route nur die Einträge ab Index 1.

Die zweite Klasse nennt sich Location und kapselt eine Koordinate und einen zugehörigen Ortsnamen. Sie enthält auch die Methoden für das Parsing der Eingabe (parse_degrees) sowie die Abfrage der geographischen Lage eines Ortsnamens (from_name).

Schließlich ist der RoutePlotter unter anderem für die SVG-Ausgabe der Routen verantwortlich. Eine Route wird durch eine oder mehrere polylines auf SVG abgebildet. Dazu werden die vorher berechneten Wegpunkte einer Route schrittweise abgelaufen und in einem neuen Array gesammelt. Wird dabei der 180. Längengrad überschritten, wird eine neue Polylinie begonnen (damit kein Stich quer über die Landkarte entsteht).

Das Hauptprogramm erstellt dann lediglich eine Instanz von RoutePlotter, übergibt die Eingabe und setzt die ausgegebenen SVG-Fragmente in das Template ein.

Der Rest sollte hoffentlich aus dem Quelltext und der Doku ersichtlich sein.

Grüße,
Matthias
 
Zurück