Michael Sheldon's Stuff

Michael Sheldon (mike at mikeasoft dot com)

September 24, 2010

Local map rendering and route finding with libchamplain, Spatialite and Open Street Map
Mike @ 3:07 pm

This tutorial takes you through the steps necessary to build a simple application which is capable of displaying data from OpenStreetMap and find driving routes between two locations without the need for any network services.

The final application will look something like this:

Final application demonstrating local render and routing

And can even be used on the Nokia N900 mobile phone (running Maemo):

Local map rendering and routing on the Nokia n900 mobile phone

Preparation

The libraries you’ll need to install for this are:

  • Memphis – A map renderer. Version 0.2.1 or later.
  • libchamplain – Provides clutter based mapping widgets. You’ll need version 0.7.1 or later for memphis support, when compiling add –enable-memphis to the ./configure parameters.
  • Spatialite – Provides OpenGIS compatible routing (and more) on top of SQLite. This needs to be version 2.4rc3 or later. You’ll also need the spatialite-tools package for importing OSM data

Next we’ll need to acquire some OSM data to work with, for this example we’ll be using a small area around Nantwich in the UK, which can be download here. Data for entire countries can be downloaded from CloudMade, or data from a smaller specific area can be obtained from the OpenStreetMap API.

Displaying the map

#include <gtk/gtk.h>
#include <champlain/champlain.h>
#include <champlain/champlain-memphis-renderer.h>
#include <champlain-gtk/champlain-gtk.h>
#include <clutter-gtk/clutter-gtk.h>

#define MAP "nantwich.osm"
#define RULES "default-rules.xml"

static GtkWidget *window;
static ChamplainMapSource *tile_source = NULL;
static ChamplainMemoryCache *memory_cache = NULL;
static ChamplainView *champlain_view;


static void on_destroy(GtkWidget *widget, gpointer data) {
        gtk_main_quit();
}


static void zoom_to_map_data(ChamplainView *view) {
        ChamplainMemphisRenderer *renderer;
        ChamplainBoundingBox *bbox;
        gdouble lat, lon;

        /* Fetch a reference to the memphis renderer */
        renderer = CHAMPLAIN_MEMPHIS_RENDERER(
                       champlain_map_source_get_renderer(CHAMPLAIN_MAP_SOURCE(tile_source)));
        /* Find what section of the world it covers */
        g_object_get(G_OBJECT(renderer), "bounding-box", &bbox, NULL);
        /* Find the centre of that region */
        champlain_bounding_box_get_center(bbox, &lat, &lon);

        /* Zoom in on that position */
        champlain_view_center_on(CHAMPLAIN_VIEW(view), lat, lon);
        champlain_view_set_zoom_level(CHAMPLAIN_VIEW(view), 14);
}


int main(int argc, char *argv[]) {
        GtkWidget *widget, *vbox, *bbox, *button, *viewport, *label;
        ChamplainMapSource *source;
        ChamplainRenderer *renderer;
        ChamplainMapSourceChain *source_chain;
        ChamplainMapSource *src;
        ChamplainRenderer *image_renderer;
        guint tile_size;

        /* Initialize libraries */
        g_thread_init(NULL);
        gtk_clutter_init(&argc, &argv);

        /* Create a GTK window */
        window = gtk_window_new(GTK_WINDOW_TOPLEVEL);
        gtk_window_set_title(GTK_WINDOW(window), "Local rendering and routing tutorial");
        g_signal_connect(G_OBJECT(window), "destroy", G_CALLBACK(on_destroy), NULL);

        /* Create an embedded champlain GTK widget */
        widget = gtk_champlain_embed_new();
        /* Get the ChamplainView contained within the GTK widget */
        champlain_view = gtk_champlain_embed_get_view(GTK_CHAMPLAIN_EMBED(widget));

        /* Setup memphis as our tile source. Normally champlain would download tile images
         * from one of a number of online services, by using memphis we can render all
         * the tiles locally without the need for a network connection. */
        ChamplainMapSourceFactory *factory = champlain_map_source_factory_dup_default();
        source = champlain_map_source_factory_create(factory, "memphis-local");
        renderer = champlain_map_source_get_renderer(CHAMPLAIN_MAP_SOURCE(source));
        champlain_memphis_renderer_load_rules(CHAMPLAIN_MEMPHIS_RENDERER(renderer), RULES);
        champlain_file_tile_source_load_map_data(CHAMPLAIN_FILE_TILE_SOURCE(source), MAP);
        tile_source = CHAMPLAIN_MAP_SOURCE(source);
        source_chain = champlain_map_source_chain_new();
        tile_size = champlain_map_source_get_tile_size(tile_source);
        src = champlain_map_source_factory_create_error_source(factory, tile_size);
        champlain_map_source_chain_push(source_chain, src);
        champlain_map_source_chain_push(source_chain, tile_source);

        /* Use a memory cache so that tiles don't have to be re-rendered everytime they're
         * displayed. Another option would be to use a file cache allowing the tiles to be
         * saved across multiple runs of the program (but at the expense of disk space). */
        image_renderer = CHAMPLAIN_RENDERER(champlain_image_renderer_new());
        /* We store up to 200 tiles in the cache */
        memory_cache = champlain_memory_cache_new_full(200, image_renderer); 
        champlain_map_source_chain_push(source_chain, CHAMPLAIN_MAP_SOURCE(memory_cache));
        g_object_set(G_OBJECT(champlain_view), "map-source", source_chain, NULL);

        /* Request a minimum size of 400x300 */
        gtk_widget_set_size_request(widget, 400, 300);

        /* Add our embedded champlain widget to the window */
        gtk_container_add(GTK_CONTAINER(window), widget);

        /* Display the window */
        gtk_widget_show_all(window);

        /* Find our OSM data on the map and show it */
        zoom_to_map_data(champlain_view);

        /* Start the GTK main loop */
        gtk_main();

        return 0;
}

To compile this example (assuming you’ve saved it to ‘champlain-routing.c’) run:

gcc `pkg-config --cflags --libs spatialite champlain-0.8 champlain-gtk-0.8 champlain-memphis-0.8` champlain-routing.c -o champlain-routing

This is a fairly standard champlain program except it uses the memphis renderer to create tile images locally instead of fetching them from an online tile server. In addition to nantwich.osm you’ll also need default-rules.xml, which defines the appearance of the map.

The resulting program will give us a small window that displays our map data without the need for an internet connection:

Displaying the map via libchamplain

Creating routing data

Before we can performing any routing tasks we first need to import our OSM data into spatialite and create a routing network from it.

Importing OSM data into spatialite

spatialite_osm -o nantwich.osm -d nantwich.sqlite -T roads -m

Generating a routing table

spatialite_network -d nantwich.sqlite -T roads -g geometry -c cost -t node_to -f node_from -n name --oneway-fromto oneway_fromto --oneway-tofrom oneway_tofrom -o roads_net_data

spatialite nantwich.sqlite 'CREATE VIRTUAL TABLE "roads_net" USING VirtualNetwork("roads_net_data")'.

Automatic import

I’ve joined these stages together into a small script, available here: populate_spatialite.sh. It takes two parameters, the first being the OSM data to import and the second is the spatialite database to be created:

./populate_spatialite.sh nantwich.osm nantwich.sqlite

Finding and drawing a route

First we define a couple of new global variables for storing references to our route’s polygon, our Spatialite database, and our database’s filename:

#define SPATIAL "nantwich.sqlite"

ChamplainPolygon *route_polygon;
sqlite3 *handle;

Then we initialize Spatialite within our main setup:

int main(int argc, char *argv[]) {
        ...
        g_thread_init(NULL);
        gtk_clutter_init(&argc, &argv);
        spatialite_init(0);
        sqlite3_open_v2(SPATIAL, &handle, SQLITE_OPEN_READONLY, NULL);
        ...
}

Finally we can create a function for drawing the routes between two OSM nodes:

/* Takes two OSM node IDs representing the desired
 * start and end locations and draws the route between
 * them on the map. */
static void draw_route(int from, int to) { 
        ClutterColor color = { 0x00, 0x11, 0x33, 0x99 };
        int ret, n_rows, n_columns, i, points;
        float lat, lon;
        char sql[256];
        char **results;
        char *err_msg = NULL;

        /* Remove any previously displayed route */
        if(route_polygon != NULL) {
                champlain_view_remove_polygon(champlain_view, route_polygon);
        }

        /* Find out how many points there are in the route */
        sprintf(sql, "SELECT NumPoints(Geometry) FROM Roads_net "
           "WHERE nodeFrom = %d AND nodeTo = %d LIMIT 1", from, to);
        ret = sqlite3_get_table(handle, sql, &results, &n_rows, &n_columns, &err_msg);
        if(ret != SQLITE_OK) {
                printf("SQL error: %s\n", err_msg);
                sqlite3_free(err_msg);
                return;
        }

        /* Check to see if we could find a route */
        if (n_rows == 0 || results[1] == 0) {
                printf("No route for %d -> %d\n", from, to);
                return;
        }

        points = atoi(results[1]);

        /* Create a new champlain polygon */
        route_polygon = champlain_polygon_new();

        /* Add each point in the route to the polygon */
        for (i = 1; i < = points; i++) {
                sprintf(sql, "SELECT X(PointN(Geometry, %d)), Y(PointN(Geometry, %d)) "
                   "FROM Roads_net WHERE nodeFrom = %d and nodeTo = %d LIMIT 1", i, i, from, to);
                ret = sqlite3_get_table(handle, sql, &results, &n_rows, &n_columns, &err_msg);                  
                if(ret != SQLITE_OK) {                                          
                        printf("SQL error: %s\n", err_msg);
                        sqlite3_free(err_msg);                                                                          
                        return;                                                                                 
                }
                sscanf(results[2], "%f", &lon);
                sscanf(results[3], "%f", &lat);
                champlain_polygon_append_point(route_polygon, lat, lon);
        }

        /* Set the polygon's display properties */
        champlain_polygon_set_stroke_color(route_polygon, &color);
        champlain_polygon_set_stroke_width(route_polygon, 12.0);

        /* Show the polygon on the map */
        champlain_view_add_polygon(champlain_view, route_polygon);
}

To see what this does we can then try calling draw_route towards the end of our main function:

int main(int argc, char *argv[]) {
        ...
        /* Find our OSM data on the map and show it */
        zoom_to_map_data(champlain_view);

        /* Draw an example route */
        draw_route(291898931, 263396519);

        /* Start the GTK main loop */
        gtk_main();
        ...
}

The main part of this likely to need further explanation are the SQL queries being used. To find a route between locations a query can be performed on the Roads_Net virtual table, to see the sort of results this generates we can load the database into spatialite directly and try some queries.

spatialite nantwich.sqlite

This starts an sqlite session with the spatialite extensions already loaded, so we can just type out our query directly and see the results:

spatialite> SELECT * FROM Roads_Net WHERE NodeFrom = 291898931 AND NodeTo = 263694833;

Algorithm ArcRowid NodeFrom NodeTo Cost Geometry Name
Dijkstra 291898931 263694833 44.5477589762393
Dijkstra 625 291898931 30091396 9.26106988426742 Hawksey Drive
Dijkstra 863 30091396 291797647 8.05233487984465 Peter Destapleigh Way
Dijkstra 864 291797647 30091398 2.10526089940676 Peter Destapleigh Way
Dijkstra 865 30091398 30091397 2.57141142336182 Peter Destapleigh Way
Dijkstra 1100 30091397 30091385 10.1017580189628 Audlem Road
Dijkstra 1101 30091385 291797619 1.21093075722029 Audlem Road
Dijkstra 1102 291797619 30091384 2.78122691192808 Audlem Road
Dijkstra 1994 30091384 263694833 8.46376620124748 Wellington Road

The first row gives us details about the entire route, each following row is a single step along that route including the name of the road we’re travelling on at the time. You’ll notice that the Geometry column appears to be empty, this column is actually accessed through a number of different functions, to get a plain text representation of the geometry for our route we can do:

spatialite> SELECT AsText(Geometry) FROM Roads_Net WHERE NodeFrom = 291898931 AND NodeTo = 263694833 LIMIT 1;
LINESTRING(-2.509696 53.058716, -2.509586 53.058025, -2.512386 53.057934, -2.512593 53.05792, -2.513372 53.057853, -2.514185 53.057543, -2.514511 53.057525, -2.515953 53.057457, -2.51673 53.057505, -2.517495 53.058079, -2.517746 53.058306, -2.518433 53.058776, -2.519147 53.059387, -2.519725 53.06049)

Or to get the X, Y position for a single point along that line we can use the X(), Y() and PointN() functions as we do in our draw_route function. So to find the position of the 4th point we could do:

spatialite> SELECT X(PointN(Geometry, 4)), Y(PointN(Geometry, 4)) FROM Roads_Net WHERE NodeFrom = 291898931 AND NodeTo = 263694833 LIMIT 1;
-2.5125926|53.0579196

From here the program could be easily extended to look up OSM IDs based on their street names (stored in the roads table), to find the nearest OSM ID to a GPS position or to display text based driving instructions, all with just a few SQL queries.

Complete listings

The full source code and data for this tutorial can be downloaded here: champlain-routing.tar.gz. The complete program includes some additional enhancements such as the ability to request routes based on street names (in a simple, but non-robust manner) and zoom level controls.

If you create anything based on this tutorial I’d be very interested to hear about it :).


23 Comments »

  1. This is awesome. It would be great to make this a package that could run with an interface on a local port so all the mapping solutions could work with it if it’s installed. Most of the navigation apps for the N900 right now are coordinated enough to share their map caches and tile sets, so if you get tiles for one, they can all use them. Having this output a format they can all understand (like gpx) would allow them to all use the local device for routing, even if it’s as a backup for when a network is unavailable.

    Thank you for detailing how you go this working and for all the effort that went into not only getting it running, but documenting how others can do it too!

    Comment by Woody — September 24, 2010 @ 8:21 pm

  2. How fast/slow is this, especially on the N900? E.g. how many milliseconds to render a single tile from vector data? How many seconds from application startup until the whole map is presented to the user?

    Just curious.

    Comment by Marius Gedminas — September 24, 2010 @ 11:27 pm

  3. The speed of rendering depends somewhat on the zoom level and complexity of the area that’s being rendered (i.e. a patch of sea will render faster than a city centre). The delay is probably slightly less than fetching the images from a network server over a typical 3G connection but there’s not much in it.

    It’s all fast enough to be usable on the N900. libchamplain isn’t quite as smooth or responsive as it could be, but it’s still okay to use (you can see an example of what libchamplain on the N900 is like by trying MapBuddy).

    Comment by Mike — September 25, 2010 @ 9:36 am

  4. Hi! Can you make a deb package to install on the N900?

    Comment by Gianka — October 3, 2010 @ 2:32 pm

  5. Hi, great work done and thanks for sharing. i want to develop a same sort of windows application. would these libraries work for me as well?

    Comment by hamad — October 4, 2010 @ 5:44 am

  6. I tryed on a ubuntu machine and it works. i want to use it on a N900, what are the libraries needed?

    Comment by ganz — October 5, 2010 @ 11:08 am

  7. what if i want to use it for NYC map? will the routing works with such a big map?

    Comment by eric — October 5, 2010 @ 3:58 pm

  8. Gianka – Sorry but I have no plans to make a Debian package for this, it would require that a number of other packages on the n900 be updated first and a package for memphis to be created. This isn’t designed as an application for people to actually make use of, just as a tutorial to help anyone interested in writing such an application, as such it would be of little use to anyone who isn’t capable of compiling the relevant libraries for themselves.

    Ganz – Same libraries as for Ubuntu, all listed at the top of the article plus whatever dependencies those applications have (e.g. clutter, clutter-gtk, etc.). The only thing specific to the n900 is the need for the nokia-binaries repository to use clutter with opengl|es support.

    Eric – I expect it would cope with NYC fine, currently the memphis renderer can’t handle very large data sets (e.g. it can’t make use of a data file for a country like the UK), but even a fairly large city should be fine.

    Comment by Mike — October 5, 2010 @ 6:13 pm

  9. Hamad – Sorry, I missed you out in my last round of answers, as far as I’m aware it should be possible to compile all those libraries for Windows using mingw32.

    Comment by Mike — October 11, 2010 @ 7:09 pm

  10. I’m trying to use the libspatialite to calculate routes, but a having a trouble here. When i try to run the query to get the route i receive this error message:

    [VirtualNetwork module] cannot build a valid network (I googled this and nothing….)

    I don’t know whats going on, i using this piece of code to run my tests here.

    spatialite_init(0);
    sqlite3 * handle;
    sqlite3_open_v2(“/home/luiz/Dados/haiti.sqlite”, &handle, SQLITE_OPEN_READONLY, NULL);
    int ret, n_rows, n_columns;
    char** results;
    char *err_msg = NULL;

    ret = sqlite3_get_table(handle,”SELECT Geometry FROM roads_net WHERE NodeFrom = 616722988 AND NodeTo = 616456115 LIMIT 1″,&results, &n_rows, &n_columns, &err_msg);

    if(ret != SQLITE_OK)
    {
    qDebug(“Problem code: %s”, err_msg);
    }

    My sqlite file works fine with the spatialite-gui, but in the code don’t. Can you help me? I’ll really apreciate your help here. Bye….

    Comment by Luiz Claudio — October 25, 2010 @ 5:16 pm

  11. Luiz: If you upload your spatialite file somewhere (haiti.sqlite), I’ll be happy to take a quick look at it.

    Comment by Mike — October 28, 2010 @ 6:14 pm

  12. FYI, I’ve put together a small web server which uses Memphis to render tiles locally from OSM data. You can use it with any program which normally downloads tiles from a.tile.openstreetmap.org. See http://webpages.charter.net/brianj4/tile-server.c_0_1
    That provides another avenue for local map rendering besides libchamplin (thanks, Mike, for the excellent tutorial!)

    No packaging yet… just build the single C source file the usual way, and link it with libmemphis and its dependencies (cairo, expat, etc.) I hope someone finds this code useful as a jumping-off point for a more complete implementation.

    Enjoy!

    Comment by Brian — February 23, 2011 @ 5:49 pm

  13. which language is this coded to ?

    Comment by Clifford — February 24, 2011 @ 11:31 am

  14. Clifford: you mean the tile-server program? It’s written in C, as is Memphis. The _0_1 suffix is a version number, so I can upload future versions (if I get around to doing any…) without file name conflicts.

    Comment by Brian — February 28, 2011 @ 7:58 pm

  15. Ya learn something new evderyay. It’s true I guess!

    Comment by Jady — July 2, 2011 @ 10:42 pm

  16. I like to see a Meego / Harmattan port on Spatialite, OSM and QML for Nokia N9 / 950.

    Comment by nsicad — August 8, 2011 @ 5:36 am

  17. Would it be awfully difficult toimplement on Windows?

    Comment by Ruben — July 16, 2013 @ 2:46 pm

  18. Ruben – I believe both libchamplain and spatialite can be compiled for Windows, and GTK certainly can, so it shouldn’t be too difficult to compile using the MinGW toolchain or similar.

    Comment by Mike — July 16, 2013 @ 11:40 pm

  19. Thanks. The libmemphis site has been offline for at least 2 weeks now. Is there another way I can get libmemphis?

    Comment by Ruben — July 25, 2013 @ 12:58 am

  20. Ruben – You can get either the pre-compiled Debian packages or the source files from http://packages.debian.org/wheezy/libmemphis-0.2-0

    Comment by Mike — July 25, 2013 @ 1:47 am

  21. wow!
    it’s unbelivable!
    it is very useful for what i am willing to do!

    Comment by phu — October 18, 2013 @ 2:21 pm

  22. Hi bro jus saw you great post. thanks for the great stuff. Am having a problem in compiling with champlain-memphis coz its not being seen / is not know by pkg-config and also champlain-memphis-renderer.h is missing in the champlain include file. also how do i compile the demo code in champlain doc file.
    am using fedora 19 plus champlain and memphis libs are installed

    Comment by Me — April 29, 2014 @ 6:00 pm

  23. Here are some tips you can try tonight to help you sleep better: 

Make sure that your room isn’t too hot or
    cold; keep your room between 55 and 75 degrees Fahrenheit.
    1 hour or more) can disrupt restorative nighttime sleep.
    But why is sleep apnea and the dentist the title of this
    blog.

    Comment by center for sleep disorders — August 30, 2014 @ 7:34 am

RSS feed for comments on this post. TrackBack URL

Leave a comment

Powered by WordPress