MARiO: Multi Attribute Routing in Open Street Map

Yeah, I got a new Publication accepted at Symposium on Spatial and Temporal Databases (SSTD) 2011 that is dealing with OpenStreetMap Data (using the JXMapKit and JXMapViewer).

MARiO: Multi Attribute Routing in Open Street Map

Franz Graf, Hans-Peter Kriegel, Matthias Schubert, Matthias Renz

Published at Symposium on Spatial and Temporal Databases (SSTD) 2011
Conference Date: August 24th – 26th, 2011
Conference Location: Minneapolis, MN, USA.

Abstract:

In recent years, the Open Street Map (OSM) project collected a large repository of spatial network data containing a rich variety of information about traffic lights, road types, points of interest etc.. Formally, this network can be described as a multi-attribute graph, i.e. a graph considering multiple attributes when describing the traversal of an edge. In this demo, we present our framework for Multi Attribute Routing in Open Street Map (MARiO). MARiO includes methods for preprocessing OSM data by deriving attribute information and integrating additional data from external sources. There are several routing algorithms already available and additional methods can be easily added by using a plugin mechanism. Since routing in a multi-attribute environment often results in large sets of potentially interesting routes, our graphical fronted allows various views to interactively explore query results.

Documents:

Bibtex

@INPROCEEDINGS{GraKriRenSch11,
  AUTHOR      = {F. Graf and H.-P. Kriegel and M. Renz and M. Schubert},
  TITLE       = {{MARiO}: Multi Attribute Routing in Open Street Map},
  BOOKTITLE   = {Proceedings of the 12th International Symposium on Spatial and Temporal Databases (SSTD), Minneapolis, MN, USA},
  YEAR        = {2011}
}

Selektionsfenster in SwingX-WS / JXMapKit

Um in der Mapkomponente von JXMapKit eine Selektion (Rechteck mit Rahmen und leicht transparenter Füllung) zu zeichnen, wird lediglich ein entsprechender Painter und ein Mouseadapter benötigt. Der Code dazu sieht folgendermaßen aus:

Der Painter & MouseListener:

public class SelectionPainter extends MouseAdapter implements Painter<JXMapViewer> {

    private Rectangle rect, start, end;
    private Color borderColor = new Color(0, 0, 200);
    private Color regionColor = new Color(0, 0, 200, 75);

    public SelectionPainter() {
    }

    @Override
    public void mousePressed(MouseEvent e) {
        if (e.getButton() != MouseEvent.BUTTON1) {
            rect = null;
            start = null;
        } else {
            start = new Rectangle(e.getPoint());
            ((JXMapViewer) e.getSource()).setPanEnabled(false);
        }
    }

    @Override
    public void mouseDragged(MouseEvent e) {
        if (start != null) {
            end = new Rectangle(e.getPoint());
            rect = start.union(end);
        }
        ((JXMapViewer) e.getSource()).repaint();
    }

    @Override
    public void mouseReleased(MouseEvent e) {
        if (start == null) {
            return;
        }
        end = new Rectangle(e.getPoint());
        rect = start.union(end);
        ((JXMapViewer) e.getSource()).setPanEnabled(true);
        ((JXMapViewer) e.getSource()).repaint();
    }

    @Override
    public void paint(Graphics2D gd, JXMapViewer t, int i, int i1) {
        if (rect != null) {
            gd.setColor(regionColor);
            gd.fillRect(rect.x, rect.y, rect.width, rect.height);
            gd.setColor(borderColor);
            gd.drawRect(rect.x, rect.y, rect.width, rect.height);
        }
    }
}

Verbindung zur Map-Komponente:

 SelectionPainter sp = new SelectionPainter();
mapKit.getMainMap().addMouseListener(sp);
mapKit.getMainMap().addMouseMotionListener(sp);
mapKit.getMainMap().setOverlayPainter(sp);

mapKit ist dabei eine Instanz von org.jdesktop.swingx.JXMapKit.

Artikel mit gepatchtem SwingX-WS

PAROS download!

Das Ziel war nobel: Code aufräumen, schöner machen, refactoren und dokumentieren und dann online stellen.

Die Realität war derart, dass es leider wichtigeres zu tun gibt. Daher stelle ich das PAROS-Projekt, das dieses Jahr auf der SIGMOD war so online wie es ist: lauffähig, und vom Softwareengineeringaspekt ziemlich hässlich. Aber vielleicht kann ja jemand etwas damit anfangen – zumindest die kleinen hacks um größere Graphen auch annehmbar schnell zeichnen zu können.

Ausserdem ist es ein schönes Beispiel, wie man JXMapKit und OpenStreetMap (OSM) zu Forschungszwecken im Bereich Datamining, GIS (GeoInformationssysteme) und auch SpatialIndexing  verwenden kann. Auf der Konferenz kannten viele OSM nämlich erstaunlicherweise gar nicht, obwohl sie auf dem Bereich tätig waren.

Und zur nächsten Version muss ich nochmal nachsehen, ob es nach den Google Maps Terms of Services  immernoch verboten ist, Maps in Nicht-Browser-Anwendungen zu integrieren. Wäre natürlich auch sehr nett, oder weiß jemand Bescheid? (Update Jan. 2011: das ist nicht mehr verboten!)

Relevante Links:

SwingX-WS mit JXMapKit auf der SIGMOD 2010 / PAROS: Pareto Optimal Route Selection

Zusammen mit meinen Kollegen haben wir eine Demo auf einer der wichtigsten Datenbank Konferenzen eingereicht, die ich letzte Woche in Indianapolis auf der SIGMOD (ACM Special Interest Group on Management of Data) zeigen durfte. Die Demo firmiert übrigens unter dem Titel PAROS: Pareto Optimal Route Selection.

Im Wesentlichen ging es dabei darum, einen von meinen Kollegen entwickelten Skyline-Algorithmus auf Straßennetzen anzuwenden um damit Wege unter mehreren Einschränkungen zu finden. Die klassische, einfache Wegsuche ist ja zum Beispiel “finde den kürzesten oder schnellsten Weg”. Bei der Skyline-Abfrage, geht es dabei darum, alle die Wege zu finden, die unter mehreren Attributen optimal sind. Also zum Beispiel alle kürzesten und schnellsten Wege, die gleichzeitig möglichst wenig Ampeln enthalten. Es müssen also mehrere Attribute gleichzeitig optimiert werden.

Da Datenmasse in der Wissenschaft oft Mangelware ist, habe ich zusammen mit etwas studentischer Hilfe einen Konverter für OpenStreetMap-Daten geschrieben um beliebig viele Daten erhalten zu können. Visualisiert wurde das Ganze mit Hilfe der JXMapKit-Komponente aus SwingX-WS! Die Gui-Entwicklung ging dank dem NetBeans Gui-Builder wie erwartet erfreulich einfach, so dass ich mich in der knappen Zeit auf die Integration des Algorithmus und auf die Architektur konzentrieren konnte. Die Architektur sollte es ermöglichen, Model und View  möglichst so zu kapseln, dass die Entwicklung und Integration neuer Algorithmen so einfach wie möglich und möglichst Unabhängig von jeglicher GUI-Programmierung ist, so dass auch Studenten schnell und einfach neue Algorithmen entwickeln und testen können.

Ich habe zwar (wie erwartet) nicht den Best-Demo-Preis bekommen, allerdings waren wirklich viele interessierte Leute auf den Demo-Sessions. Überrascht hat mich, dass ich sehr oft gefragt wurde, ob wir die Demo online stellen würden, bzw. ob die Demo OpenSource ist. Nach Rücksprache mit den Kollegen, kamen wir zu dem Schluss, dass das eine gute Idee sei und ich das machen werde. Ich werde in den nächsten Wochen also noch etwas den Code aufräumen, dokumentieren, online stellen und hoffen, dass jemand die Demo interessant und nützlich findet – vielleicht sogar so, dass es die Basis für ein oder mehre Zitationen bringt (ist immer wichtig bei Veröffentlichungen).

UPDATE: endlich ist der – äh – unschöne Code online. Da ich auch in absehbarer Zeit nicht die Zeit habe, ihn schön sauber und dokumentiert zu machen, kann ich ihn auch gleich online stellen. zum Download gehts hier lang.

Relevante Links:

Wegpunkte mit JXMapKit zeichnen

Im Artikel “Erste Schritte mit JavaX JXMapKit” habe ich schon kurz beschrieben, wie man mit NetBeans und SwingX-WS schnell und einfach eine Kartendarestllung á la GoogleMaps in Java bauen kann.

Wenn man nicht nur eine Karte anzeigen sondern auch Punkte einzeichnen will, hat man die Möglichkeiten, per jXMapKit.setAddressLocation(new GeoPosition(lat, lon)); die Koordinaten setzen, zeichnen und die Karte dorthin zentrieren. Allerdings wird die Karte damit auch immer gleich zentriert und vor allem kann man nur einen einzelnen Punkt setzen.

Mehrere Wegpunkte setzt man mithilfe des WaypointPainters:

Set set = new HashSet();
WaypointPainter waypointPainter = new WaypointPainter();
waypointPainter.setWaypoints(set);
set.add(new Waypoint(47.76098, 11.55932));
jXMapKit.getMainMap().setOverlayPainter(waypointPainter);
repaint();

Das repaint() am Ende sollte immer erfolgen, wenn neue Punkte in das Set gesetzt werden, damit die Änderung auch sofort sichtbar ist. Andernfalls muss man die Karte etwas verschieben um ein repaint zu erzwingen. Will man jetzt noch die Darstellung der Wegpunkte verändern, muss man sich noch mit dem WaypointRenderer beschäftigen.

Erste Schritte mit JavaX JXMapKit

Update 2014: Mittlerweile kann es durchaus schlauer sein JavaFX zu verwenden, so wie es hier beschrieben ist.


Nachdem ich festgestellt habe, dass Nasa WorldWind zum Anzeigen von Kartenpositionen vielleicht doch ein bisschen Overkill ist, habe ich mir JXMapKit des SwingLabs-Projekts angesehen.

Um das Beispiel überhaupt zum Laufen zu bekommen, benötigen wir natürlich die richtigen Libraries. Das wären dann SwingX und SwingX-ws. Derzeit wird man mit der Kombination nicht ganz glücklich, da in SwingX 1.0 (mindestens) eine Methode entfernt wurde, die in SwingX-ws benötigt wird. Der zugehörige Bug ist zwar reported, aber natürlich noch nicht in der aktuellsten Version eingebaut (Stand 30.7.2009). Eine gepatchte Version habe ich hier online gestellt: Jar / Quellen.

Wenn die Libraries erst einmal im Classpath liegen ist es im Prinzip ganz einfach (ich erkläre wie immer anhand von NetBeans aufgrund des besseren GUI-Editors):

  1. JFrame-Form erstellen
  2. JXMapKit in den Frame ziehen
  3. die JXMapKit Komponente anklicken und in den Properties den defaultProvider auf OpenStreetMap stellen, andernfalls bekommt man nur Exceptions.
  4. fertig!

Das ganze sollte dann so aussehen:

Screenshot von JXMapKit
Screenshot von JXMapKit

Der Code dazu sieht folgendermaßen aus:

public class MapViewer extends javax.swing.JFrame {
    public MapViewer() {
        initComponents();
    }

    private void initComponents() {
        jXMapKit1 = new org.jdesktop.swingx.JXMapKit();
        setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);
        jXMapKit1.setDefaultProvider(org.jdesktop.swingx.JXMapKit.DefaultProviders.OpenStreetMaps);
        getContentPane().add(jXMapKit1, java.awt.BorderLayout.CENTER);
        pack();
    }

    public static void main(String args[]) {
        java.awt.EventQueue.invokeLater(new Runnable() {
            public void run() {
                new MapViewer().setVisible(true);
            }
        });
    }
    private org.jdesktop.swingx.JXMapKit jXMapKit1;
}

OpenStreetMap ist ja ganz schön. Aber eine Karte wäre ja auch fein. Das erreicht man, indem eine neue TileFactory erstellt wird. Dazu wird schnell der Konstruktor geändert:

    public MapViewer() {
        initComponents();
        WMSService wms = new WMSService();
        wms.setLayer("BMNG");
        wms.setBaseUrl("http://wms.jpl.nasa.gov/wms.cgi?");
        TileFactory fact = new WMSTileFactory(wms);
        jXMapKit1.setTileFactory(fact);
    }
Screenshot von JXMapKit mit BlueMarble
Screenshot von JXMapKit mit BlueMarble der NASA

Und schon sieht’s so aus:

Beim Starten kann es sein, dass man erst mal nur ein blaues Fenster sieht. Ändert sich leicht, indem man ein paar mal auf den Minus-Button drückt und etwas abwartet, da das Laden der Bilder vom Nasa-Server etwas dauern kann. Bei genauem Hinsehen, wird man im obigen Screenshot auch bemerken, dass der markierte Ausschnitt im rechten unteren Teil nicht mit der tatsächlichen Darstellung übereinstimmt sondern (in dem Fall) einen Ausschnitt anzeigt, der deutlich südlicher liegt (im Fenster sieht man nämlich eigentlich die Nordspitze Schottlands.

Nützliche Links: