alaCarte

Renderer für Kartendaten

PSE-Projekt am Institut für Theoretische Informatik,
Lehrstuhl für Algorithmik II, Prof. Dr. Peter Sanders
Betreuer: Veit Batz, Dennis Luxen

Simon Dreher, Florian Jacob, Tobias Kahlert,
Patrick Niklaus, Bernhard Scheirle, Lisa Winter

Erklärung - Ein Kartenrenderer

Kartendaten


<?xml version="1.0" encoding="UTF-8"?>
<osm version="0.6" generator="OpenStreetMap server">
  <node id="412356" lat="49.0109168" lon="8.3745865"
      changeset="434241" user="amai" uid="16922">
    <tag k="highway" v="traffic_signals"/>
  </node>
  <way id="3060700"
      changeset="1584316" user="klausis" uid="85761">
    <nd ref="14482679"/>
    <nd ref="14581147"/>
    <tag k="name" v="Gutschstraße"/>
    <tag k="highway" v="residential"/>
  </way>
</osm>
                    

Stylesheet


line|z14- [highway=motorway] {
    width: 2;
    color: #556270;
    casing-width: 1;
    casing-color: #3b4249;
}
                    

Kartenkachel

alaCarte

OpenStreetMap

- die Wikipedia für Kartendaten

  • Sammelt frei nutzbare Kartendaten
  • Wiki-ähnliches Projekt
  • 2004 in London gegründet
  • heute:
    • >1 Million Benutzer
    • >1,8 Milliarden Knoten
    • >170 Millionen Wege

OpenStreetMap

- die Kartendaten im Detail

  • Punkte (Nodes) mit Geo-Koordinaten
  • Verbindungen (Ways) aus Punkten
  • Aggregationen aus Punkten und Wegen (Relations)
    • z.B. Straßenbahnlinien
  • Schlüssel-Wert-Paare (Tags) mit Name, Art und Zusatzinformationen

<?xml version="1.0" encoding="UTF-8"?>
<osm version="0.6" generator="OpenStreetMap server">
  <node id="412356" lat="49.0109168" lon="8.3745865"
      changeset="434241" user="amai" uid="16922">
    <tag k="highway" v="traffic_signals"/>
  </node>
  <way id="3060700"
      changeset="1584316" user="klausis" uid="85761">
    <nd ref="14482679"/>
    <nd ref="14581147"/>
    <tag k="name" v="Gutschstraße"/>
    <tag k="highway" v="residential"/>
  </way>
</osm>
                    

MapCSS-Stylesheets

  • Kontextfreie Beschreibungssprache
  • Liste von Regeln aus:
    • Selektorenkette
    • Attributsliste
  • Attribute können auf Tag-Werte zugreifen
  • Integrierter „Taschenrechner“

node|z6-14 [place=city]
{
    text: name;
    font-size: eval("tag('population')/'100000.0' * '2.0' + '18.0'");
    text-halo-color: rgba(1.0, 1.0, 1.0, 0.6);
    text-halo-radius: 2.0;
    text-color: rgba(0.0, 0.0, 0.0, 1.0);
    text-position: center;
}
				

MapCSS-Stylesheets

  • Unterstütze Attribute:
    • Linien und Umrandungen in jeder Farbe und Breite
    • Text-Halos, Text-Ausrichtung am Weg
    • Füllfarben, Füllmuster, Füllbilder
    • Highway-Shields, Icons
    • ...
  • Alles außer:
    • Ausgefallenere text-Attribute: Unterstrichen, Kapitälchen, ..
    • extrude-Attribute (3D-Gebäude)

line[highway=motorway],
line[highway=motorway_link],
{
    z-index: 2;
    color: #556270;
    casing-color: #3b4249;
    shield-color: #556270;
    shield-frame-color: #ffffff;
    shield-casing-color: #3b4249;
    shield-shape: round;
}
				

Algorithmen - 2D-Baum

  • Ausgangsbasis: 1GB XML-Daten (Regierungsbezirk Karlsruhe)
  • Sublineare Range Queries für die Daten in einer Kachel?
  • Lösung: 2D-Bäume
    • Mercator-Projektion der Kugelkoordinaten auf eine Ebene
    • Aufbau eines 2D-Baums
    • 2D-Baum beantwortet Range Queries in O(n½ + m)

Algorithmen - 2D-Baum

  • Raumdekomposition: Daten werden am Median geteilt
  • Abwechselnd in beide Dimensionen
  • Wiederhole bis Menge der Knoten pro Bereich klein
  • Stelle Bereichsanfragen:
    • Absteigen bis in Blätter, die Bereich überschneiden
    • Daraus die Daten auswählen, die im Bereich sind

Algorithmen - Label-Placement

  • Wie platziere ich die Namen von Orten, Straßen und Städten
    • möglichst überschneidungsfrei?
    • ohne abgeschnittene Labels an Kachelgrenzen?
    • so, dass „unwichtige“ Labels „wichtige“ nicht verdrängen?
    • so, dass Highway-Shields einen Mindestabstand haben?
    • und das alles deterministisch?
  • Label-Placement ist NP-hard, also Heuristik nötig

Algorithmen - Label-Placement

  • Greedy-Algorithmus
  • Zuerst Labels am Rand platzieren
  • Label der „Wichtigkeit“ nach absteigend platzieren
  • Konfliktbehandlung:
    • ½ × Größe in alle Richtungen verschieben
    • Position mit wenigster Überschneidung
    • Platzieren, falls Überschneidung kleiner als Schwellenwert
    • Nicht platzieren, falls zu weit in Nachbarkachel

Algorithmen - Label-Placement

Ergebnisse in der Praxis sehr gut:

Features unserer Software

alaCarte

  • Einfach zu benutzende Standalone-Lösung
  • Kacheln über Webserver in OSM-Verzeichnisstruktur
  • Stylesheets zur Laufzeit änderbar
  • Fast vollständige MapCSS-Unterstützung
  • Vergleichbare Performance mit dem Kachelserver auf osm.org

Features

Standalone-Lösung

Bisher mit Mapnik:


sudo apt-get install postgresql-9.1-postgis postgresql-contrib-9.1

sudo -u postgres -i -H
createuser -SdR gisuser
createdb -E UTF8 -O gisuser gis
createlang plpgsql gis
psql -d gis -f /usr/share/postgresql/9.1/contrib/postgis-1.5/postgis.sql
psql -d gis -f /usr/share/postgresql/9.1/contrib/postgis-1.5/spatial_ref.sql

psql gis -c "ALTER TABLE geometry_columns OWNER TO gisuser"
psql gis -c "ALTER TABLE spatial_ref_sys OWNER TO gisuser"
exit

sudo vim /etc/postgresql/9.1/main/pg_hba.conf
sudo -u postgres -i


...


./generate_xml.py --host localhost --port 5432 --dbname gis -.-user 'gisuser'
./customize-mapnik-map > $MAPNIK_MAP_FILE
liteserv.py ../mapnik/osm.xml
                

Features

Standalone-Lösung

Mit alaCarte:


./alacarte-importer -i karlsruhe-regbez-latest.osm -g ala.carte

./alacarte-server -g ala.carte -s <stylesheet-directory>
				

Features

Webserver

  • HTTP-Schnittstelle
  • Kompatibel zur OSM-Verzeichnisstruktur
  • Leicht in bestehende Projekte integrierbar

Features

Verschiedene Stylesheets

  • Ein Server für mehrere Stylesheets gleichzeitig
  • Stylesheets zur Laufzeit:
    • hinzufügen
    • editieren
    • löschen
  • Kachel-Cache wird bei Änderungen neu aufgebaut

Features

breite MapCSS-Unterstützung

Icons

Marktplatz, 49.009°N, 8.405°E

Features

breite MapCSS-Unterstützung

Straßenbahngleise

VBK-Betriebshof Ost, 49.0067°N, 8.4324°E

Features

breite MapCSS-Unterstützung

Tunnel & Brücken

Südtangente, Edeltrudtunnel, 48.9902°N, 8.3888°E

Features

breite MapCSS-Unterstützung

Bahngleise

Rheinhafen, 49.0145°N, 8.3419°E

Features

breite MapCSS-Unterstützung

Highway-Shields

Karlsruhe und Umgebung, 48.950°N, 8.440°E

Features

Performance vergleichbar mit osm.org

Entwicklung über die Zeit

Erster Screenshot nach Komponentenintegration

Entwicklung über die Zeit

Erstes MapCSS-Stylesheet

Entwicklung über die Zeit

MapCSS-Unterstützung wächst

Entwicklung über die Zeit

Gebäude und Flussgebiete

Entwicklung über die Zeit

Highway-Shields und Eisenbahn

alaCarte heute

Ende des Vortrags