Archiv für ‘Analyse’

Oktober 28th, 2016

Solving the Shortest Path Problem (5) – Benchmarks

This article of 2012 at http://stegua.github.io/ shows, that the type of the priority queue of a shortest path solver is crucial for the solving time.
You have to agree with that, but there is another point to mention: the choice of the graph representation.
I wanted to spend some more time on the comparison of the graph libraries LEMON and BGL and so I modified some of the code and ran the following tests on it.

The code was compiled using GCC 4.8.4 with the the following switches: -O2 -m64 -std=c++11. My test machine is a laptop with an Intel 4-Core i3@2,4 Ghz. You can download the graph instances from the DIMACS site.

BGL’s Dijkstra d-ary Heap (d=4)
Boost’s Graph Library offers two variants of a Dijkstra shortest path solver implementation. A regular one dijkstra_shortest_path and a variant that does not use an internal color map of nodes (dijkstra_shortest_path_no_color_map). Both of them use by default a d-ary Heap with d=4 which is actually a quad heap queue. Unfortunately there is no easy way to change the heap in the dijkstra implementation.

There is no significant difference comparing the solving time of each of them, if you do not change the graph structure.
Using the BGL with street networks you have two flavours of a graph: the widely known adjacency_list and a representation that you should look at if you’re dealing with sparse graphs as street networks are: the compressed_sparse_row_graph.

Here are the results.

weiterlesen »

Be the first to like.

Oktober 28th, 2016

Solving the Shortest Path Problem (4) – Comparison of LEMON and BGL

In the previous articles I explained the usage of the APIs of LEMON and Boost Graph Library (BGL). Now I want to sum up the differences of them. Of course this is very opinion-based.

1. Simplicity

LEMON has despite its template mechanism a clean and realtively simple interface. A few algorithms have predefined default template parameters which cover standard use cases. For example the Dijkstra Shortest Path solver uses a binary heap as priority queue.  The map concept of storing additional data on graphs is not very friendly regarding usability but is a guarantee for performance, because the core component only has to look after its internal IDs and not after some additional graph data.

By contrast you cannot say that the Boost BGL looks simple at first glance. I found it harder to understand, but it has flexibility to adapt changes. Especially the property map concept may be familiar to regular Boost users, but if you are new to this it’s not really clear.

2. Flexibility

The API of LEMON is flexible enough to change the many parameters of graphs, algorithms or internal structures like the heap type. Unfortunately there is little documentation on these advanced operations.

What I liked working with the BGL was the bundled property mechanism where you can „inject“ your custom class and convert that to some node or arc property. I missed in BGL the ability to change the heap type for the shortest path dijkstra. A big plus in my opinion is the so called visitor concept in the BGL. You are able to specify a visitor that allows custom functions in a standard algorithm, e.g. stopping the execution of the dijkstra algorithm at a certain total distance. But again implementing this is not an easy task.

So this time it’s a draw.

3. Algorithms

Both of the two libraries offer a huge list of graph algorithms if you are not only interested in shortest path algorithms.

Again the score is even in my opinion.

So to sum these things up, I enjoy using LEMON more. But what about the performance? I will write an extra article about this.

 

1 andere Person mag diesen Artikel.

September 13th, 2011

Gekachelte Erstellung von Höhenlinien aus einem DGM10

Ausgangslage

Aus einem Digitalen Geländemodell (DGM) lassen sich relativ einfach Höhenlinien berechnen. In ArcGIS gibt es dazu das Tool Contour, was als Input ein DGM und einige wenige Parameter benötigt. Für kleinere Datenmengen – also entweder ein DGM, das ein großes Gebiet abdeckt und dabei eine grobe Auflösung besitzt, oder aber ein DGM eines kleinen Gebietsausschnitts mit hoher Auflösung funktioniert das Werkzeug auch einwandfrei und die Ableitung zackig. Die Berechnung der Höhenlinien im Abstand von 25m mit dem DGM25 (50m Auflösung, ca. 200MB) für ganz Bayern benötigt ungefähr 40 Sekunden. Dabei ist die entstehende Shapedatei 300MB groß.

Mit einem DGM10 (10m Auflösung) über ganz Bayern hinweg siehts dann aber schon anders aus. ArcGIS 9.3.1 sp2 machte bei diesen Datenmengen (DGM: 2,0 GB als Rasterdataset in File Geodatabase) schlapp. Denn der temporäre Output des Werkzeugs Contour ist ausschließlich im Shapefile-Format. Und dieses Format hat leider die etwas unangenehme Eigenschaft, höchstens 2,1 GB an Daten aufnehmen zu können (siehe hier). Wenn man mit dieser Auflösung des DGM10 über ganz Bayern hinweg Höhenlinien ableiten möchte, werden aber einiges mehr als 2,0 GB erzeugt. Was also tun?

Die Lösung heisst hier: Gekachelte Verarbeitung (Tiled Processing). Man teilt also das DGM in ein paar Kacheln auf (Create Fishnet des DGM-Extents, Polygonisieren der Linien, Clippen des DGM mit dem Polygon-Raster) und leitet aus diesen die Höhenlinien ab. Gedacht getan – aber halt: zu kurz gedacht! Denn die Ableitung der Höhenlinien basiert auf einer Interpolation einer Linie zwischen den Höhenpunkten. Was passiert also an den Rändern der Kacheln? Genau: es entstehen Lücken. Und zwar genau in dem Ausmaß der Auflösung des DGMs. In unserem Fall entspricht dies also einem 10m-Streifen.

Tja nun – und jetzt? Keine Panik. Denn auch dafür gibts eine Lösung.

 

 

Lösung

Der Trick bei der gekachelten Ableitung der Höhenlinien besteht darin, gepufferte Kacheln des DGM zu prozessieren. Dabei muss der Puffer um die Kacheln mindestens das zweifache der Auflösung des DGMs betragen. Es werden also aus überlappenden Kacheln des DGM die Höhenlinien pro Kachel berechnet. Anschließend liegen die Höhenlinien aus den Überlappungsbereichen exakt übereinander.

An dieser Stelle räumt ein Clip auf den Höhenlinien mit den ursprünglichen Extents der Kacheln wieder auf. Diese tolle Idee stammt aus einem ESRI-Forum und ist hier nachzulesen.

Und tatsächlich, beim Test von drei Kacheln lagen die berechneten Höhenlinien aus den gepufferten Kacheln im Überlappungsbereich exakt übereinander. Jetzt muss nur noch ein Clip mit den Extents der ungepufferten Kacheln die beiden Höhenlinien-Shapes trennen und siehe da: die Höhenlinien passen an den Rändern der Kacheln wunderbar zueinander.


Be the first to like.

Tags: , ,
Dezember 23rd, 2010

Uphill/Downhill-Berechnung mit SAGA GIS

Zielsetzung

In diesem Artikel möchte ich zeigen, wie man ausgehend von einem Weg und einem Digitalen Geländemodell jeweils die Bergseite und die Talseite des Weges mit Hilfe von GIS bestimmt. Dies bezeichnet man als Uphill/Downhill-Berechnung. In der Forstwirtschaft ist es beispielsweise interessant, ob das geschlagene Holz eines Bestandes bergauf oder bergab auf den Weg gerückt (transportiert) wird. Bergab wird die Reichweite der Rückung bei relativ gleichbleibenden Rückekosten und somit auch die Erschließungswirkung eines Weges mit ca. 300m angenommen. Bergauf jedoch kann man für vergleichbare Rückekosten nur bis maximal 150m kalkulieren. Daher ist es interessant, die Berg – und Talseite eines Weges zu bestimmen. Die Methoden wurden dem Dokument „Predicting wood skidding direction on Steep Terrain by DEM and Forest Road Network Extension“ entnommen und auf die Software  SAGA GIS in der Version 2.0.6 übertragen.

weiterlesen »

6 Leute mögen diesen Artikel.

März 25th, 2010

Regenwald in Google Earth (8) – Vektorisierung

Von Raster- zu Vektordaten

Bislang hatten wir es mit Rasterdaten zu tun. Die Klimadaten wurden entsprechend gefiltert, klassifiziert und verschnitten. Das Ergebnis könnten wir als Rasterdatensatz (bspw. GeoTIFF) exportieren und auf Google Earth als Bild-Overlay einfügen. Die Farbgebung ist dann allerdings festgelegt und auch mit der Transparenz von Bildern haperts nach meinen Erfahrungen noch bei Google Earth.

Deshalb werden wir unsere Ergebnisdaten vom Rasterformat ins Vektorformat konvertieren und anschließend ins KML-Format überführen.

weiterlesen »

1 andere Person mag diesen Artikel.

März 25th, 2010

Regenwald in Google Earth (7) – Analyse II


Globale Landbeckung

Jetzt können wir die Fläche mit den klimatischen Voraussetzungen für tropischen Regenwald mit der tatsächlichen Fläche des immergrünen Waldes abgleichen. Im ersten Teil dieses Artikels haben wir uns bereits Daten über die weltweite Landbedeckung des GLCF besorgt. Diese müssen nur noch in SAGA GIS importiert und weiterverarbeitet werden.

weiterlesen »

Be the first to like.

März 14th, 2010

Regenwald in Google Earth (6) – Analyse I

Verschneidung der Klimadaten

In diesem Schritt werden wir nun die Daten der weltweiten Jahresdurchschnittstemperatur und des weltweiten gemittelten Jahresniederschlags miteinander kombinieren, denn ein Parameter allein hat ja noch keine Aussagekraft bezüglich des potentiellen Wachstums tropischen Regenwaldes. Beispielsweise ist der Temperaturbereich in der Sahara prinzipiell im tropischen Bereich – die Feuchtigkeit fehlt hier jedoch. Analog dazu gibt es auch in Alaska genügend Niederschlag, nur ist es dort natürlich ein bisschen zu frisch für den tropischen Regenwald.

Also: Nur dort, wo sich beide Bereiche räumlich decken sind die klimatischen Voraussetzungen für tropischen Regenwald gegeben.

weiterlesen »

Be the first to like.

März 13th, 2010

Regenwald in Google Earth (5) – Klassifizierung

Klassifizierung von Temperatur und Niederschlag

Mit den Daten sind wir nun soweit fertig. Wir haben Temperatur und Niederschläge als Grids vorliegen. Was jetzt noch fehlt ist eine sinnvolle Klassifizierung der Daten. Die ursprüngliche Fragestellung war: Wo auf der Welt sind die klimatischen Voraussetzungen für tropischen Regenwald gegeben?

weiterlesen »

Be the first to like.

März 13th, 2010

Regenwald in Google Earth (4) – Niederschlag

Niederschlag

Die Jahresdurchschnittstemperatur haben wir bereits im vorhergehenden Teil berechnet. Nun soll es um den weltweiten kumulativen Jahresniederschlag gehen.

weiterlesen »

Be the first to like.

März 4th, 2010

Regenwald in Google Earth (3) – Temperatur

Jahresmitteltemperatur

Jetzt wollen wir nach und nach alle 12 Datensätze der Temperatur (tmeanX.bil) in SAGA GIS  (so geht’s) importieren.

Anschließend bedienen wir uns dem Grid Calculator von SAGA um die durchschnittliche Jahrestemperatur zu ermitteln. Dazu muss in diesem Werkzeug ein einzelnes oder mehrere Grids angegeben werden, die zusammengerechnet werden sollen.

weiterlesen »

Be the first to like.

Tags: , ,