RIF: R: [postgis-users] routing and network analysis

Justin Deoliveira jdeolive at refractions.net
Thu Jan 20 11:04:38 PST 2005


Does the routing have to be done in real time? on-demand? etc.

If not you could calculate all paths, store them in postgis and then 
just publish them out with a mapserver layer.

If you do have such a requirement then you will need a middle layer of 
processing that will do the network analysis.

The ideal solution would be to have postgis do the network analysis. I 
have thought about how this could be accomlished, and at first glance it 
is not a trivial amount of work. It involves getting down and dirty with 
postgres and developing a new access method.

Justin


Paolo PP. Pulli wrote:
> Many thanks for your code. I'm going to try it.
>  
> Are you never develop a web gis with shorter path functionality? Have you any idea?
> I'm explain my self:
> Data in PostGis 
> Webserver Apache/Mapserver
> Language Php or other
>  
> Thanks
> Paolo
>  
> 
> 	-----Messaggio originale----- 
> 	Da: Justin Deoliveira [mailto:jdeolive at refractions.net] 
> 	Inviato: mer 19/01/2005 18.17 
> 	A: Paolo PP. Pulli 
> 	Cc: 
> 	Oggetto: Re: R: [postgis-users] routing and network analysis
> 	
> 	
> 
> 	Hi Paulo, Here is some sample code to solve the routing problem, as for
> 	data, just run it on any line string data that you have. As for thread
> 	safety, the frame work is not thread safe. If you have any more
> 	questions please let me know.
> 	
> 	Justin
> 	
> 	//read a feature collection of LineString geomtries
> 	FeatureCollection fc = ...
> 	
> 	//create a graph generator
> 	LineStringFeatureGraphGenerator g = new LineStringFeatureGraphGenerator();
> 	
> 	//add all the features to the graph
> 	for (Iterator itr = fc.iterator(); itr.hasNext();) g.add(itr.next());
> 	
> 	//get any node in the graph, we will choose the first
> 	Node source = (Node)g.getGraph().getNodes().iterator().next();
> 	
> 	//create a cost function for the edges of the graph
> 	DijkstraIterator.EdgeWeighter ew = new DijsktraIterator.EdgeWeighter() {
> 	
> 	        public double getWeight(Edge e) {
> 	                //just return the length of the line
> 	                Feature f = (Feature)e.getObject();
> 	                LineString l = (LineString)f.getGeometry();
> 	                return l.getLength();
> 	        }
> 	};
> 	
> 	
> 	//create a shortest path finder
> 	DijsktraShortestPathFinder p = new
> 	DijsktraShortestPathFinder(g.getGraph(),source,ew);
> 	
> 	//for each other node in the graph find the shortest path
> 	for (Iterator itr = g.getGraph().getNodes().iterator(); itr.hasNext();) {
> 	        Node n = (Node)itr.next();
> 	        if (n.equals(source)) continue;
> 	
> 	        Path p = p.getPath(n);
> 	}
> 	
> 	
> 	
> 	Paolo PP. Pulli wrote:
> 	> 
> 	>
> 	>>Hi Robin,
> 	>>
> 	>>I have built a network building/walking framework that is precisley
> 	>
> 	> for
> 	>
> 	>>solving problems like the one you describe. It is part of the geotools
> 	>>project, in a module called "graph". See http://www.geotools.org/
> 	>>
> 	>>The way it works is you pull all of the relevant geometries (in your
> 	>>case road linestrings) out of the database and build a graph. Then
> 	>
> 	> walk
> 	>
> 	>>the graph to answer questions like give me the shortest path from node
> 	>
> 	> 1
> 	>
> 	>>to node 2.
> 	>>
> 	>>The main drawback is that the entire graph has to be stored in main
> 	>>memory. So if you are working with mass amounts of data then you might
> 	>>need something a bit more elegant.
> 	>>
> 	>>Let me know if you are interested and I can send you some sample code.
> 	>
> 	>
> 	> I'm apologize.
> 	> I'm very interesting about routing and network analysis.
> 	> Could you send me your sample code (with data!?), please.
> 	>
> 	>
> 	>>>a) I have access to road network data.  I've heard the new GRASS can
> 	>>>be used to do network analysis.  anyone heard if it would be
> 	>
> 	> promising
> 	>
> 	>>>in combination with postGIS, or could suggest another package?
> 	>
> 	> Yes, Grass is powerful to do network analysis but, for my knowledge and
> 	> my needed, is not thread safe therefore it's not suitable for example in
> 	> webGis and it is to prefer(?) PostGIS sql-procedure (any idea on it?)
> 	>
> 	>
> 	>>>b) as an alternative, can anyone suggest or point to an efficient
> 	>>>approach for computing the shortest path between two points which
> 	>
> 	> does
> 	>
> 	>>>not go through, say, water polygons?
> 	>
> 	> Justin, your solution solve this question?
> 	>
> 	> Thanks
> 	> Paolo
> 	> ICQ: 254248one23
> 	>
> 	> PS.
> 	> I'm just download GeoTools and I'm going to study it!
> 	>
> 	> _______________________________________________
> 	> postgis-users mailing list
> 	> postgis-users at postgis.refractions.net
> 	> http://postgis.refractions.net/mailman/listinfo/postgis-users
> 	
> 	
> 	--
> 	Justin Deoliveira
> 	Refractions Research Inc.
> 	jdeolive at refractions.net
> 	(250) 885-4387
> 	
> 


-- 
Justin Deoliveira
Refractions Research Inc.
jdeolive at refractions.net
(250) 885-4387



More information about the postgis-users mailing list