1. Openlayers gets a nice plug on the popular ajaxian blog. Unfortunately its not exactly well written and it left even me questioning the point of the post. Ah well, publicity is publicity i guess
2. UMN Mapserver 4.10 was released with a few new goodies such as curved labelling, improved mapscript service support and various other bug fixes. Surprised no one else picked up on this … i’m sure ms4w builds will be updated in the coming week.
3. For those not attending FOSS4G and missed out on the PgRouting sessions, Lorenzo has pleaded with me to give the project a plug. A bit late i know, but check out the awesome prototype whipped up with Kamap here. Select the tool that looks like a pin to define the start/end points on the map, and then wait for the route to be updated.
4. Geoserver is at 1.4M2 … and even though its beta, it now has KML reprojection support (yay!). The guys can’t make it much easier for the average joe to serve their data into GE now, winner.
5. What_nick has been working on the improved WorldWind WMS/WFS plugins and has assured me it will make it into the next release (1.4?). Other good news is the smaller footprint that Bull mentioned in his post because of the move to using WFS for placenames rather than bundling the data with the download.

Related posts:

1. WALIS wrapup
2. Google half bakes WMS support
3. Google Earth WMS still undercooked

Disclaimer: This should only aid in you decision making. I definately would not consider using pgdjikstra to replace emergency vehicles routing and travelling salesmen type problems. Considerable work would need to be added to flesh out commonly requested features such as turn by turn navigation

Alright, lets see how we went …

Sample dataset: 57k vertices, 44k nodes

Machine specs: P4 Celeron M 2.6ghz Laptop, 512mb RAM, PostgreSQL 8.1

Sample queries are using the following function,

SELECT astext(the_geom) FROM shortest_path_as_geometry(‘roadstable’, startnode, endnode)

Click to enlarge!

Considering my laptop is definately not the best benchmark machine, I can only assume that deployment on a proper server environment would result in a significant performance increase across the board.

Interesting stuff! Head over to cartoweb.org to give Sylvain and his crew any feedback or bugs. I havent checked lately but i’m sure the CVS version have had some improvements.

Related posts:

1. Opensource routing tools
2. Build your own routing solution
3. Adding routing overlays to kamap

I feel sorry for the zoomin guys as no doubt their target audience has all but dissappeared over night (until of course businesses read googles licencing arrangements ).

Has anyone been able to get routing working? Seems as though its not accepting any kind of local address i throw at it.

Overall i’m not too impressed, but maybe thats because i have access to this sort of data all the time. It certainly will be interesting to see what sort of local “mashups” (god i hate that word) are created.

via geblog

Related posts:

1. Google Maps to extend development into Aus
2. Google Earth’s Issue logging …
3. Adding WMS overlays to Google Earth

1. Kamap install.

Grab the latest stable (or CVS if you’re feeling lucky) release and follow the instructions to get it up an running. Paul and the rest of the crew have made this possibly the easiest frontend to get up and running in a flash, but if you do run into problems please contact the list.

Ignore my setup / mess, this was an existing mapfile used for benchmarks. This is possibly what you shouldn’t have setup, but its got the road centrelines so it’ll do for our purposes.

2. Create a database handler

Since we would like the users to be able to interface with our db, we need to create a little interface to query the roads and execute the shortest_path_as_geometry call. For the sake of simplicity, the following should give you somewhere to start. (Source: querydb.php, if the output below gets munged)

Dont worry if the output format doesnt really make much sense at the moment, we’ll touch on this in the next step.

< ?php
//SQL query
$query = "SELECT astext(the_geom) FROM shortest_path_as_geometry('roads', ".$start.", ".$end.");";
$result = pg_query($query) or die('Query failed: ' . pg_last_error()); // output
echo "n";
echo "n";
echo "	Startn";
echo "  ";
while ($line = pg_fetch_array($result, null, PGSQL_ASSOC)) {
      foreach ($line as $col_value) {
               $col_value = str_replace("MULTILINESTRING((", " ", "$col_value");
               $col_value = str_replace("))", ", ", "$col_value");
               echo "$col_value";
      }
}
echo "n";
echo "n";
echo "n";  // Free resultset
pg_free_result($result);  // Closing connection
pg_close($dbconn);
} ?>

3. Integrating PG’s kaXmlOverlay code

PG has done some great work looking into how best to integrate vector overlays on kamap, much like google maps does. Technically, there are lots of different options, but PG’s latest code uses a mix of the wz_jsgraphics and the PHP GD library.

This option has arguably the best cross browser support in that the route is actually rendered and thus positioned, as a PNG/gif image. But more on that later.

PG has posted a demo of the capabilities at his site (http://sistel.dyndns.info/ka-map/indext.html).

You will need to download the kaXmlOverlay.js, drawGeom.php and the wz_jsgraphics library.

Edit your existing kamap index.html and add,

The code is pretty self explanatory, we simply define the path to the XML (querydb.php) and attach it to the map initialised handler. PG has a slightly alternative setup on his demo website, adding a refresh function to automatically refresh the XML doc at a set period. This is a real handy feature if you’re tracking a live GPS feed, but in our case it just adds extra overhead.

4. Time to test

Since the code contains a few point of failures its best to start at the beginning,

1. Chose a start and end edge id from your postgis table and try running http://your.host/kamap/querydb.php?ST=startid&EN=endid. You should get a well formatted text/xml response with the routing coordinates. If the edge ids dont exist or the geometry function did not work, you will get an error here.
2. Now you have determined that you have got the coords, time to try kamap. Load up the modified index from step #3 and tail the apache logs. Amongst all the js queries, there should be one eventual request for the querydb, and then for the drawgeom (something like drawgeom.php?gt=L&st=5&bp=5&sc=25&cl=15,1800,0..). If after 30 seconds or so you dont appear to see any overlays, strip out the exact request from your log and try to run it in isolation. eg. http://localhost/kamap/drawgeom.php?gt=L&st=5&bp=5&… if GD is configured properly you should get an image output like below (PNG)



3. If its still not working, there probably just a URL thats throwing a 404. Keep checking the logs for what its requesting just to make sure its not trying to find a file in / and not /kamap

5. The result

Apologies in advance as i just didnt have time to implement a more dynamic approach such as a user entering a start/end address. I hope someone else out there has the time and the inclination to extend this stuff. The possiblities are endless.

6. Problems and future additions?

1. Needs a better way of converting geo2pix. The existing js function has meant that potentially you could have 40 + coordinate pairs being converted (DB->XML->JS->Drawgeom->Image) to pixel space, and then passed via a URL parameter to drawgeom.php. Very inefficient, and can also go beyond the URL size limit … maybe short term the use of POST might be more suitable?
2. Line simplification. Further work needs to see how suitable the PostGIS simplify() function is. Conceptually, a function to guesstimate a suitable tolerance for the zoom level, and then retrieve the new coords would be suitable but how easy at guessing said tolerance would be interesting.
3. JS bloat. I’d prefer to move as much code as possible server side, especially for “calculations”. Being able to pass the current client params such as pixel/cell size, coords, scale etc. would mean much of the xmlOverlay.js code done by PG could be done server side, and potentially drawn in the same thread (eg. no need for a separate drawgeom.php … the initial query would pass the results direct)
4. An extension to the current querying abilities, where users can click on the map for their start and end points, and the click points would be translated into geo and then fed back into a postgis function to grab the closest road edge. This was what i wanted to do for this article, but alas theres never time.

Related posts:

1. Kamap WFS point overlays
2. Adding WMS overlays to Google Earth
3. Build your own routing solution

I have noticed a bit of interest especially on PostGIS‘ new implementation of a GiST spatial index to speed up its performance. What i think is lacking is that there is little to no documentation on how “much” faster spatial indexing (not to be confused with attribute indexes) performs.

So here we go, a simple benchmark in less than 15 mins

First up, my datasets. For the base data, i will use the roads dataset from my previous routing article.

The benchmark tests in this case will be a simple, arbitrary bbox on the following datasets interfacing with Mapserver 4.6 (win32).

Word of warning: Please dont take these results as gospel, its merely to highlight the performance differences across the board.

FYI:

• All data is in CRS 4326 (WGS84)
• The timings will be extracted using the debug output from mapserver
• Note the number of features in each query, the first obviously not being very realistic
• A WMS requests are for single layers only with the BBOX values below

1. 115.69402,-32.1273,116.09642,-31.86770 Features: 57564
2. 115.82508,-32.0358,115.93653,-31.97567 Features: 8408
3. 115.81400,-32.0493,115.86604,-32.02131 Features: 1389
4. 115.82171,-32.0405,115.84112,-32.03009 Features: 338

• ^ Created with the standard quadtree sizes determine by the shptree utility
• * Created with “CREATE INDEX roadsindex ON roadsindex USING GIST( the_geom GIST_GEOMETRY_OPS );” as per postgis documentation

I think the table speaks for itself, but im a little bit cautious about drawing too many conclusions. Most people are aware that PostGIS is slower than shapefiles, but thats a given. Most users who use PostGIS are using it for other reasons (such as for its geoprocessing functions).

The PostGIS guys have claimed about a 10% performance loss over shapefiles. In this little test it was indeed more than this, but i have no doubts that in the hands of a more experienced postGIS expert that they could certainly narrow down the gap further.
Fact of the matter is, spatial indexing is an important part of performance optimisation but should be considered with other methods such as view scale limiting, simplified symbolisation and feature generalisation. Unfortunately i dont have access to a mapserver hooked up with ArcSDE 9 or Oracle Spatial … could of made things interesting

Please, i make no attempts at claiming i am the master of all that is postgis and mapserver. If there is something glaringly obvious that i did not configure or did not include, please let me know and i will be happy to update the results.

Related posts:

1. New Orleans Satellite Imagery
2. WFS Feature paging … yes please
3. 10 utils to make opensource gis that little bit easier

The following guide is largely based on the tutorial found at the Cartoweb WIKI and its associated readme. Many thanks need to be directed at the cartoweb developers, in particular Paschain for compiling a working win32 dll and a system than can easily be built upon. Many thanks.

If you would like some background on the djikstra shortest path algorithm try the following resources.

General info
Various C/VB/PHP implementations
Step by step Animation

Lets get started.

1. Download PostgreSQL 8.1 or higher.

The win32 installer is recommended and makes installation easy. A stable PostGIS is included in the installation of PostgreSQL so no more downloads like previous releases I usually include all developer options in the install by habit, this shouldnt be neccessary but just make sure plpgsql language is checked when installing.

2. Download the pgdijkstra package from cartoweb

3. Extract pgdijkstra.dll into X:\..\PostgreSQL\8.1\lib

4. Lets create a new database to hold the routing data ..

createdb -U username dbname
Password:
CREATE DATABASE

5. Time to ensure plpgsql is initialised on our new db

createlang plpgsql -U chris roads

6. Last thing we need to do is insert the new routing functions ..

psql -U chris roads -f “D:\Program Files\PostgreSQL\pgdijkstra\dijkstra.sql”
Password for user chris:
CREATE FUNCTION
CREATE FUNCTION
CREATE FUNCTION
CREATE FUNCTION

psql -U chris roads -f “D:\Program Files\PostgreSQL\pgdijkstra\dijkstra_postgis.sql”
Password for user chris:
CREATE FUNCTION
CREATE FUNCTION
CREATE FUNCTION
CREATE FUNCTION
CREATE TYPE
CREATE FUNCTION
CREATE FUNCTION

Now assuming all the installation went A’ok then its time to start inserting our data and creating the graphs! Again, all credits go to the cartoweb guys, especially Paschain for their hard work. The following steps are reworked from the official readme

7. If you havent already converted your data into a postgis table, lets use shp2pgsql on my road dataset and create a “roads” table. Be prepared to wait a while if its a large dataset while each feature is inserted.

shp2pgsql D:\roads.shp roads > roads.sql

then run the SQL inserts into the db

psql -d roadsdb -f roads.sql

8. If you come from a background used to using web frontends such as phpMyAdmin, id highly suggest installing phpPgAdmin. While the diehards will scoff, it does tend to make handling the usual db functions a lot easier

9. Almost all road datasets wont have the necessary target_id and source_id for the graph creation. Luckily there is a assign_vertex_id function to automatically generate each id from the start and end node of the line string.

Add 3 new columns to your roads table source_id(integer) target_id(integer) if you dont already have similar from/to node columns that you can rename. If you dont, use the following function to generate source/target id’s based on the distance given.

For example, using the below will group all nodes within a distance of 0.1 to the same vertex id. Obviously, depending on your units and accuracy you may wish to drop the number down to something more suitable. The smaller the unit, the longer the procedure will take

SELECT assign_vertex_id(’graph2′, 0.1);

Luckily my road dataset already had such from/to nodes so all was needed was a simple column rename.

10. Now we are ready to begin generating the graph edges and vertices.

SELECT create_graph_tables(’roads’, ‘int4′);

This procedure will create 2 new tables, roads_vertices and roads_edges. If your source and target id’s are not using int4 as a type, you will need to modify the SQL procedure and remove the int4 dependancy. Otherwise, cross your fingers and wait for the tables to be populated.

11. As you can see we need to populating the cost weighting for each edge. There is a update_cost_from_distance function by default that simply calculates the length of the edge and uses this as the weight. Obviously if you would like to formulate a more complex algorithm for your weights such as using distance, road type, speed etc. then you will need to edit this function. Its easy to do so feel free to have a play.

Lets use plain distance for now,

SELECT update_cost_from_distance(’roads’);

12. We’re pretty much done. Time to generate a shortest path! Using shortest_path_as_geometry we can pass the start and end points for our route. The function expects the node target/source id’s from the original roads table. So lets manually select a couple and try running it.

SELECT gid, astext(the_geom) FROM shortest_path_as_geometry(’roads’, 179551, 179681);

You should now be looking at a list of MULTILINESTRING objects which make up the shortest path from your start to end vertex.

13. Visualising your shortest path is the next logical step. There are a number of ways doing this, such as passing the geometry to a vrml/javascript function or rendering it as an image. Luckily Paschain has included an easy way to insert the static path inside a Mapserver layer.

LAYER NAME "route" TYPE LINE STATUS DEFAULT CONNECTIONTYPE postgis CONNECTION "host=localhost dbname=roads user=chris password=pass " DATA "the_geom from (SELECT the_geom, gid from shortest_path_as_geometry('roads', 219102, 183552)) as route using unique gid using srid=-1" TEMPLATE "t" CLASS NAME "0" STYLE SYMBOL "circle" SIZE 7 COLOR 255 255 0 END END END

Please note that this method is very inefficient as each map refresh will recalculate the route and so putting a lot of unnecessary load on the database. Only use this a proof of concept for now

Lets compare the “shortest path” with a common driving directions site, whereis.com.au. As you can see, the route is different purely because of our simple algorithm to generate the weights.

I plan to release some at least two more articles that build on this introduction.The first will investigate how to tweak the weighting algorithm to more closely match the commercial routing option and the second will look at implementing a more dynamic, user friendly javascript option built into Ka-Map.

Stay tuned, hope i havent put too many of you to sleep

Related posts:

1. Adding routing overlays to kamap
2. PGdijkstra Routing performance
3. Note to self re: postgis

To save anyone else out there some time in finding this same info, i have attached the relevant info to the bottom of the post.

I am extremely interested in the work Paschain has done on the PGDijkstra module which he successfully uses in camp2camp’s GPL CartoWeb frontend (see this demo for an example). Unfortunately Paschain has only deployed it into a *nix environment and i am yet to have any luck building the module from source in win32. Any diehard PostGIS experts reading this, i implore you to have a read of the docs and let me know if you have had any success.

If there are any other solutions out there that i missed, please drop me a line.

Geotools routing module

I have not put a great deal of time investigating this module as it has a big limitation of having to maintain the graph in memory. I wanted it to run on a quite large road dataset and so storing the edges in memory wasn’t really an option.

If you’re just generally interested, check out the following thread where the author Yves describes how to enable the module for the demo.

Yves Bolognini wrote:
I’m the one who wrote the initial GeoTools routing module. This was
actually a test module as the idea was to implement routing in PostGIS.

If you still want to use GeoTools routing, you’ll first need to install
the PHP/Java Bridge and GeoTools 2.1.x:

http://www.php.net/manual/en/ref.java.php

http://www.geotools.org/Downloads

Then you can activate Routing plugin on test_project client:

/projects/test_project/client_conf/client.ini
loadPlugins = …, routing

…and on server:

/projects/test_project/server_conf/projectmap/projectmap.ini
mapInfo.loadPlugins = …, routing, projectRouting

Layers used for routing in this demo are more_points and more_lines.

I haven’t tried the steps mentioned above, so attempt at your own risk !

Related posts:

1. 10 utils to make opensource gis that little bit easier
2. DMSolutions done it again
3. Build your own routing solution

I have noticed a bit of interest especially on PostGIS‘ new implementation of a GiST spatial index to speed up its performance. What i think is lacking is that there is little to no documentation on how “much” faster spatial indexing (not to be confused with attribute indexes) performs.

So here we go, a simple benchmark in less than 15 mins

First up, my datasets. For the base data, i will use the roads dataset from my previous routing article.

The benchmark tests in this case will be a simple, arbitrary bbox on the following datasets interfacing with Mapserver 4.6 (win32).

Word of warning: Please dont take these results as gospel, its merely to highlight the performance differences across the board.

FYI:

• All data is in CRS 4326 (WGS84)
• The timings will be extracted using the debug output from mapserver
• Note the number of features in each query, the first obviously not being very realistic
• A WMS requests are for single layers only with the BBOX values below

1. 115.69402,-32.1273,116.09642,-31.86770 Features: 57564
2. 115.82508,-32.0358,115.93653,-31.97567 Features: 8408
3. 115.81400,-32.0493,115.86604,-32.02131 Features: 1389
4. 115.82171,-32.0405,115.84112,-32.03009 Features: 338

• ^ Created with the standard quadtree sizes determine by the shptree utility
• * Created with “CREATE INDEX roadsindex ON roadsindex USING GIST( the_geom GIST_GEOMETRY_OPS );” as per postgis documentation

I think the table speaks for itself, but im a little bit cautious about drawing too many conclusions. Most people are aware that PostGIS is slower than shapefiles, but thats a given. Most users who use PostGIS are using it for other reasons (such as for its geoprocessing functions).

The PostGIS guys have claimed about a 10% performance loss over shapefiles. In this little test it was indeed more than this, but i have no doubts that in the hands of a more experienced postGIS expert that they could certainly narrow down the gap further.
Fact of the matter is, spatial indexing is an important part of performance optimisation but should be considered with other methods such as view scale limiting, simplified symbolisation and feature generalisation. Unfortunately i dont have access to a mapserver hooked up with ArcSDE 9 or Oracle Spatial … could of made things interesting

Please, i make no attempts at claiming i am the master of all that is postgis and mapserver. If there is something glaringly obvious that i did not configure or did not include, please let me know and i will be happy to update the results.

Related posts:

1. Spatial indexing
2. WFS Feature paging … yes please
3. How to not setup an online imagery shop

I have been pondering this thought for quite a while and i think its really a direction GIS needs to look at moving should the situation suit the use of “non-live data”.

We have a tendancy to expect users will always need the most up to date data available, all the time. This of course suits particular situations but i think most will agree that more often than not, static data does the job just as well. Highlighting the needs and expectations of the users using the GIS is the key; assume nothing.

The best way to illustrate the differences in architecture between the new and the old, lets take the standard road map application. It has the standard functionality of zoom and pan, direction routing, search and geocoding.

In the existing GIS mindset, this application would be built using an application server referencing the spatial and attribute databases. Every map zoom, pan and search the users submit will need to be sent in the usual REQUEST <-> RESPONSE communication. It is this communication which effectively kills the responsiveness of any web application using this ‘click and wait’ method. Not only does the user need to send a sometimes detailed request, the server must then

• parse the request
• execute its procedures and queries
• reference the database(s)
• perform any spatial operations
• Retrieve the data
• Perform any reprojections
• Run cartographic formatting
• Create the image
• Send the response

Sound a bit too complex for someone just wanting to pan around the map? Thats because it is.

Fast forward to the past year and all the new players have ditched the old method in favour of visually appealing, quick and responsive interfaces. The one key difference? Architecture.

To give a bit of background, applications such as google maps buy their street data and imagery off a variety of suppliers. This data as soon as it is cut off to google is static. They then generate about 7tb of image tiles and then consume these inside their AJAX (Asynchronous Javascript and XML) frontend. The result? Asynchronous movement.

source:

AJAX applications can send requests to the web server to retrieve only the data that is needed, usually using SOAP or some other XML-based web services dialect, and using JavaScript in the client to process the web server response. The result is more responsive applications, since the amount of data interchanged between the web browser and web server is vastly reduced. Web server processing time is also saved, since a lot of this is done on the computer from which the request came.

In this new architecture, there is still REQUEST<->RESPONSE communication, but the request is made asynchronously (ie. no click and wait) and the request is a simple image retrieval. This simplifies the application in that it only needs to,

• Parse the request
• Retrieve the image
• Send the result

In Australian terms, this is just another way to “skin the cat” (doing the same thing two different ways). There are obvious positives and negatives for both implementations, but in the end its a battle between finding a balance between usability/responsiveness and the data driven applications themselves.

There is a real need out there to realise our shortcomings in the existing implementation and move forward in making these data driven apps more “user friendly”. Think about the following situation and the practicality of using an AJAX solution,

Manually performing a cadastral parcel selection,

• Current
• The user sends the active layer and the click coordinates
• The server parses the request and performs the spatial intersect on the layer
• It then highlights the parcel and draws the remaining 300 non-selected parcels as an image
• Server returns the image
• AJAX implementation
• The user sends the active layer and the click coordinates
• The server parses the request and performs the spatial intersect on the layer
• It then extracts either, the coordinates as GML, or an image with only the selected parcel
• Server returns the image or GML
• Client processes the response and overlays the new image/GML over the existing image

Sound familiar? This example can be modified to handle alot of other common situations. If someone was to calculate the statistics, im sure GIS systems on general would create 70% of redundant images due to poorly implemented cache systems, or situations where the whole map is regenerated just to add a single point (or even worse, regenerated when nothing has changed).

So what do we do? Well, unfortunately a lot of the implementation lies with the application developers (Arcims/Mapserver/Geomedia/Geoserver devs, id love to hear your thoughts). The ability to perform a select, for example, without actually retrieving an image of the entire extents is still unavailable on any application as far as i’m aware. If we all just took one step back and looked at our implementations it would be obvious that we do the simplest things (drawing map extents), very very poorly.

My final open question … Do we really need live cadastral layers? If yes, are we really talking about the spatial data, or just the attributes attached to it?

Ka-map is one such implementation of an asynchronous mapserver client. It is capable of generating mapserver tiled images on the fly or from its cache and can easily be scripted to perform “live” attribute retrieval for interrogating the “static” tiled layers.

Related posts:

1. Ka-Map makes it to xml.com
2. Securing your geometry in Arcims
3. Taking it to “the man”

Check out the demo site here. It is without a doubt the best demo i have seen showcasing Ka-Map and mapserver’s new WMS support for a time attribute. Excellent stuff … just make sure you press play !

ps. In a somewhat related line, anyone know of any projects working on an opensource routing solution? Let me know

Related posts:

1. Opensource routing tools
2. Creating 3d views from contours
3. GeoAr OpenLazlo WMS/WFS Client