Matthias Reitinger
ɐɯıǝɹ
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:
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
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>
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
Zuletzt bearbeitet: