Routing on SharpMap

Topics: Algorithms, General Topics
Editor
Aug 9, 2011 at 12:54 PM

I'm not sure if there is already routing in SharpMap, I just found this project. Using OSM I created a routing library:

http://sourceforge.net/projects/osmsharp/

It's a complete routing engine that can also optimize some logistics problem(s). More info on the OSM wiki (http://wiki.openstreetmap.org/wiki/OsmSharp) or my blog (http://www.14k.be).

If there is no routing implemented in SharpMap I would be happy to write some code to plug OsmSharp onto SharpMap and enable routing based on OSM or any other data source.

Coordinator
Aug 9, 2011 at 1:21 PM

Hello xivk,

There is currently no routing engine in SharpMap's core. If you are willing to contibute such functionality, I assume it will be greatly appreciated.

IIRC, there have been serveral inquiries for routing on this forum

If you have any questions, feel free to ask.

cheers FObermaier

Developer
Aug 9, 2011 at 3:23 PM

QuickGraph project http://quickgraph.codeplex.com/ contains some algorithms that can help you building a routing engine.

In the past I've create some trivial examples in the NetTopologySuite repository that can easily be used with SharpMap:

http://code.google.com/p/nettopologysuite/source/browse/trunk/NetTopologySuite.Samples.Console/Tests/Various/GraphBuilder2Test.cs

Editor
Aug 17, 2011 at 9:23 AM

Ok, thanks for the feedback!

I will first try and get to know SharpMap al little better and I'll see where it leads me. If possible I will contribute in any way I can!

Editor
Dec 8, 2011 at 2:08 PM

Sorry for  bumping this up, but i came across it while searching for something else.

A couple of years back I looked at doing this with D_Guidi for NTS. At the time we were quite limited because of a couple of issues (im not sure if Diego made any progress - apologies if i'm reposting things that have already been considered.

At the time Quckgraph was quite limited in terms of its Dijkstra implemention (they worked perfectly but didnt implement any kind of heap structure so on real world graphs they were slow because of the number of arc/node ratio on a road network or any other type of network). In the mean time quick graph has been improved so it now uses more advanced structures that would speed up the routing process. I've also come up  with a idea for reducing the size of  the graph being routed across:

Basilly, on most real world examples you can achieve a massive reduction in the number of nodes/edges on a graph by only using the first and last )but applying the actual length to the SP algortihm. Keep a record of the id of the line segment that they relate to, say a dictionary. The reason is that most real world graphs contain lots of nodes that dont realy do anything ther than link into the next and previous - ie you only apply the nodes that actualy connect in with others. 

Then after the SP run you reconstruct the actual path from the dictionary structure when you created the graph. This should speed up the process of carring out the SP analysis and perhaps more importantly remove the step needing to construct a pre-created graph (it takeing a shape file and turning into a graph for quick graph to be able  to process).

 

Anyway,  looking back over this is something i plan to do over the summer.

 

 

 

Developer
Dec 9, 2011 at 9:24 AM

My sample was more a proof of concept that a "real world" example, if you made any progress using NTS/SharpMap and QuickGraph, please share your experience :)

Developer
Dec 16, 2011 at 7:13 AM

you can find some sample usages of QuickGraph also in the "0.9.5-DeltaShell" branch

http://sharpmap.codeplex.com/SourceControl/changeset/view/94795

Developer
Dec 16, 2011 at 7:15 AM
Edited Dec 16, 2011 at 7:28 AM
I succeeded to find the shortest path algorithm in the PostGIS database using pgrouting.  
As I see it most important that we should be  create  a graph, we can use NTS to create vertices and edges of the graph from the streets layer , and then use disktra algorithm to find shortest paths in that graph

TrieuVy
Editor
Dec 16, 2011 at 9:16 AM

Apologies for not responding sooner. Been a bit busy here.

D. Apologies, nothing negitive was meant in my comments. Only that if you remember (I'm A Olden by the way), when we tried to apply what was the graph builder class to a real world shape file we had problems because it was so slow - we needed to 'pre-process' a shape file to get the graph.

Trievy. Thats more or less what we tried to do. The Dijkstra algortihm came from Quickgraph which a few years back didnt apply any of the data structures (priotity queue or fibbonaci heap etc) to the Dijsktra so it was quite slow on a graph of any size. When i get chance i  plan on revisitng it, but doing a couple of operations that would speed up the route finding. It basiclly goes something like this:

Dictionary<int,Linestring> = new Dictionary <int,Linestring>

For each (line in the layer)

{

    Take the line, put in the dictionary (INDEX OF THE GEOMETRY IN DataSource,line);

   Take the first and last points in the line and add them to the graph, assocaiting the distance as being the full length of the linestring, along with the index of the list (so you can retrieve it from the dictionary later

}

Then when you run the Dijsktara on the graph it will return shortest path based, from which you'll  be able to get all the ids of the linestring making up the shortest path, so you then get them from the dictionary, so you can reform that for visulatzation.

There would need to be an extra step in that the solution above is a little basic, you would need to handle cases where the user wants get the shortest path from a mid point on a line. But thats just an extension of the above using NTS (i think!).

The idea of this is that most real world shape files (or whatever format  include a lot of data that is empty and serves no purpose for SP analysis except for visuisation (as long as you have the actual length, which the above takes care of.

 

 

 

 

 

 

 

 

Editor
Dec 16, 2011 at 10:49 AM

I did something similar already in OsmSharp by creating a SparseGraph that runs on top of the regular Graph object but 'removes' all nodes that have only two neighbours adding the length of the removed edges to one 'super-edge'. This is not that hard to implement and drastically improves performance, especially when calculating multiple routes in the same general area, which is exactly what I needed myself.

You should also try to upgrade Dykstra to A* and if possible bi-directional A* using some distance heuristic. Something I also implemented but don't use at the moment because it's only good for one-to-one calculations and cannot be used when doing one-to-many calculations. A* will increase search speed and reduce memory usage.

Developer
Dec 19, 2011 at 3:36 AM
Edited Dec 19, 2011 at 3:51 AM

Hi Edmund0Dantes,

- If road database were divided into segments that each intersection of this road and other road is a vertex of the graph, we can store them into the graph and save to the file structure or database structure and accessing them is very fast.

- Most of the storage road data is not divided into segments intersect at the intersection, so we need to rebuild a function to generate the vertices of the graph at the intersection  by NTS.

Hi xivk,

A * algorithm can be applied completely to find the shortest path that weight is the length of the road to improve speed
If you want to search through many points, we consider algorithms TSP (Traveling Sales Person)

TrieuVy

Editor
Dec 19, 2011 at 6:42 AM
Morning,

Your first suggestion is the (more or less) what I was suggesting. When I was thinking about it originally I didn't consider very large graphs.in which case you would probably have to store them in a file Or database. Has anybody else looked at how google transfer the results of SP analysis between computers. That's a very concise format for storing paths of lots of nodes in a database.

The second point can get very complicated depending on how the network was generating. But generally all the shape files I have seen only have intersecting points at the either end line section (a road can be made up of more than one line section). So the graph would be made up of the points (as xivk) suggests at the end of the road. It gets complicated because for instance road networks in the UK split a road into different sections for lots of reasons, such as when the maximum speed changes, or just because the person digitising the line feels it should be split.


I'm getting excited now and plan to coding a example over the Xmas break (between this Wednesday and the 3rd January).





________________________________________
From: trieuvy [email removed]
Sent: 19 December 2011 04:36
To: Olden A C (AT/FBS)
Subject: Re: Routing on SharpMap [SharpMap:268366]

From: trieuvy

Hi Edmund0Dantes<http://www.codeplex.com/site/users/view/Edmund0Dantes>,

- If road database were divided into segments that each intersection of this road and other road is a vertex of the graph, we can store them into the graph from the file structure or database structure and accessing them is very fast.

- Most of the storage road data is not divided into segments intersect at the intersection, so we need to rebuild a function to generate the vertices of the graph at the intersection by NTS.

Hi xivk,

A * algorithm can be applied completely to find the shortest path that weight is the length of the road to improve speed
If you want to search through many points, we consider algorithms TSP (Traveling Sales Person)

TrieuVy

Read the full discussion online<http://sharpmap.codeplex.com/discussions/268366#post714024>.

To add a post to this discussion, reply to this email ([email removed]<mailto:[email removed]?subject=[SharpMap:268366]>)

To start a new discussion for this project, email [email removed]<mailto:[email removed]>

You are receiving this email because you subscribed to this discussion on CodePlex. You can unsubscribe<https://sharpmap.codeplex.com/discussions/268366/unsubscribe/> on CodePlex.com.

Please note: Images and attachments will be removed from emails. Any posts to this discussion will also be available online at CodePlex.com
Developer
Dec 19, 2011 at 6:58 AM
Edited Dec 19, 2011 at 7:24 AM

PS: Some tools for building the Graph, you can see here: http://www.pgrouting.org/docs/howto/topology.html

We should consider creating a new tool to build a topology of the graphs with NTS
or assume the Topology generated from the available tools, we only add shortest path algorithms on memory to support all data sources

TrieuVy

Editor
Dec 19, 2011 at 7:59 AM

@TrieuVy: With one-to-many I mean routes from A - {B,C,D,E} means calculating routes A->B, A->C, A->D and A->E. TSP is something different.

I think if you want fast point-to-point routing you should look at other more advanced techniques like contraction hierachies. The performances of this is very impressive! Relative short distance calculations can be done using A*.

http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf


http://www.google.be/url?sa=t&rct=j&q=contraction%20hierarchies&source=web&cd=1&ved=0CB4QFjAA&url=http%3A%2F%2Falgo2.iti.kit.edu%2Fdocuments%2Frouteplanning%2Fgeisberger_dipl.pdf&ei=Q_zuTuD9Ioaj-gbg1cGJAg&usg=AFQjCNGIufychAWJ9CP5fmwLnElYs7eJBg&cad=rja
Developer
Dec 19, 2011 at 9:07 AM
Edited Dec 19, 2011 at 9:09 AM

Hi Edmund0Dantes,

To save time, you should create a graph from the data are relatively good that you already have: the beginning and end of the road are two vertices of the graph, the length of road is edge of the graph.  If you use shp, you can build a network by ArcInfo. See: http://www.pgrouting.org/docs/howto/topology.html.

After that you use Dictionary( can use QuickGraph or not ) and add vertices and edges of the graph to memory. Add shortest path algorithms on memory ( if do not use QuickGraph )


Merry Christmas! :)

TrieuVy

Editor
Jan 11, 2012 at 2:38 PM

I've implemented this, using quick graph.

 

I appears to work. Still need to do some refactoring and bug testing.

Developer
Jan 12, 2012 at 5:19 AM

Good work!

TrieuVy

Coordinator
Jan 12, 2012 at 6:18 AM

Yes, curious what you have come up with. Do you mind sharing it via patch or issue?

Thanks

FObermaier

Developer
Jan 12, 2012 at 6:21 AM

I'm interested too :)

Editor
Jan 12, 2012 at 6:39 AM

Of course,

 

always happy so share. I just need to perform some more debugging and clean it up a bit. In fact theres one or two aspects related to NTS that you all may be able  to answer.

 

I'll post a patch in a few days.

Mar 22, 2012 at 11:10 AM

Hi, Edmund0Dantes!

Where can I find your patch?

Thanks!

Editor
Mar 22, 2012 at 11:14 AM

Ah. I completely forgot about this. :ooops:

 

I'll upoload it over the weekend.

 

 

 

Mar 22, 2012 at 11:15 AM

OK )

Editor
Mar 25, 2012 at 4:01 PM
Edited Mar 25, 2012 at 4:04 PM

I've just uploaded a patch (or at least i think i did - never done it  before :-)) that contains a example project and the code to perform a shortest path analysis, and get back a Linestring representing the shortestpath.

 

The main class is the RoutingEngine, so to perform a analysis you do this ( or  something simalair)

 

RoutingEngine Engine = new RoutingEngine();

Engine.AnalysisLayer = mapbox1.map.layers[0];

Engine.UserSource = apointclosetothelineforthesource;

Engine.UserDestination = apointclosetothelineforthedestination;

LineString LS = Engine.PerformShortestPathAnalysis(false) // true doesnt work propertly yet.

if (LS == null)

    // There was no shortest path

else

   DrawLineOnMap

 

It works on the (UK) based datasets i've tried it on. A couple of this about that, all my data seems to have linestrings only,  i've put in some functionaluty to handle multilinestrings but havent been able to test it.

 

As i said in an ealriar post (before i forgot about this :-)) theres a couple of NTS/Sharpmap class that really need to be imrpved, they work but perhaps there is proably a much better way of doing them, but i dont know about.

I've trying to get my Phd written up over the next 5-6 weeks, so not really able to do much with this until then. But it does provide a starting point. Im not sure if Xivk is still around but his methodology for handling 'super edges' might be usefull (i've started that but havent had chance to finsih it. As is his use of OSM data. part of the problem with all these datasets is coming up with actually correct routing information (one way streets etc, no left turns  etc). Most of that information is in OSM (from what i can tell), so it could be usefull to have that functionality.

Coordinator
Mar 26, 2012 at 5:49 AM

Thanks for your effort, I'll take a look asap.

FObermaier

Developer
Jul 10, 2012 at 11:43 AM

Hi Edmund0Dantes,

I tried this patch with the lastest version of sharpmap. I change some code for NTS and GOAPI . Now everything builded ok, but the test data miss some file in patch:

Cardiff250.dbf

Cardiff250.shp

Can you add this demo data to patch again.?

Editor
Jul 10, 2012 at 11:58 AM

Will do that later this evening/tomorrow morning.

 

Im sumbitting my phd thesis next Monday (OMG OMG OMG, lol). Plan on revisiting this then.

Developer
Jul 11, 2012 at 1:51 AM
Edited Jul 11, 2012 at 1:53 AM

wow, good luck !, edmund0dantes. I am looking forward you. Have a good essay.

Developer
Jul 11, 2012 at 3:18 AM

Hi edmund0dantes,

I tested on my demo data. Shortest path return ok and look faster when demo on memory. However i have to add in to somewhere of code to check point null or not.

Thanks you again.

Coordinator
Jul 11, 2012 at 6:28 AM
edmund0dantes wrote:

Im sumbitting my phd thesis next Monday (OMG OMG OMG, lol). Plan on revisiting this then.

All the best

Editor
Oct 11, 2012 at 7:46 AM

Quick Update on this.

 

Over the past of couple of weeks i;ve gone over my own implementation of Dijsktra shortest path algortihm (with fibonnaci heaps). It appears to be faster than the quick graph implementation (althougth obviously not as generalised - mine doesnt use generics).Toying with the idea of plugging that into the patch i produced to see what happens. Have to make some changes to the thesis over the next couple of months, but im getting there. :-)

 

Xivk has done as crazy stuff (in the good way) with routing over on the Opensharpmap project.

 

 

 

 

 

 

 

Jan 19, 2015 at 3:14 PM
has routing been integrated in SharpMap? Xivk or edmund0dantes?

i tried to integrate the patch edmund0dantes from Mar 25, 2012. i didn't succeed. objects (among others) like SharpMap.Geometries do not exist (now to be found as GeoAPI.Geometries?).

any plans for SharpMap.Routing?
Coordinator
Jan 20, 2015 at 8:15 AM
EdmundODantes patch has been applied in the Examples\RoutingDemo project. It is not part of the solution and may need some tweaking, but the SharpMap.Geometries problem is solved.
Jan 21, 2015 at 1:39 PM
Thanx, you only need to know where to find the information;-) with a little this-and-that under VS 2013 i got it running.

Loading 80MB-shapefile took half an hour. Outputs distance and this linestring but no time. ok, it's a route.