I have a postgis database of roads which are in Linestrings. When building the road network , I would like to node all road intersections rather than having just the end points as nodes. Like you said, the routing algorithm would be affected if the roads are not properly noded. Which classes should I look into when implementing this?
My idea is to implement a system like this. Say there are several cabs in a given vicinity with the exact coordinates given say by GPS. A service call comes and I would like to disptach the closest taxi to the location. Another question is also how do I find the closest road to a point that is not located on the linestring as this person might be located in a building or perhaps waiting in an intersection for the cab.
Jase
On 11/15/05, Justin Deoliveira <[EMAIL PROTECTED]> wrote:
Yes, the relationship among features is customizable. For linestrings,
the relationship is sharing an endpoint. This is a natural relationship
as the nodes in your graph will correspond to the nodes in your road
network. The downfall with this approach is that if your roadnetwork is
not properly noded, then their will be no relationship in the graph.
As for routing, you are correct, the structure of the graph will dictate
the routing. However, it is mostly dependent on how you define "weights"
on edges in the graph. The graph package contains a number of pathing
algorithms, the most populate being dijkstra. For linestrings the weight
defaults to the length of the line, however this could be easily
extended to use an attribute on the feature (speed limit perhaps).
Hope this helps, if you supply me with more information about your
problem I can better direct you on how to implement it.
Justin
jgarnett wrote:
> The graphing package is not specific to roads. Indeed the "relationship"
> is up to you to define. You could define it as "touches" with JTS, or
> simply compare linestring endpoints, if you need it to inspect the
> intersections (and if they are built or not) you can do that as well.
>
> Justin is the developer on this one (for both JUMP and GeoTools) - and
> should be able to answer with the exact classes you need to implement.
>
> JOdy
>
> Jase wrote:
>
>> Hi Satya,
>>
>> Thanks for the heads on. I did more reading on graphing and have a
>> better understanding now on some of the concepts.My intention is to
>> load the graph once into memory and route from there. It has
>> approximately 15000 features.
>>
>> Before I dwell further, I've got a question. I looked through the
>> LineStringGraphGenerator class on how the graph network is built and
>> have some questions.
>>
>> I would like to know if the graph network takes into consideration
>> road intersections during built? I'm asking this as I'm thinking it
>> would affect routing as the shortest path might be taking a turn into
>> another road before the road ends rather than travesing the entire
>> road. Correct me if I'm wrong.
>>
>> Thanks
>>
>> On 9 Nov 2005 07:49:56 -0000, *Satyanarayana Murty Pindiproli*
>> <[EMAIL PROTECTED] <mailto: [EMAIL PROTECTED]>>
>> wrote:
>>
>> Hi jason,
>> Considering your Queries I think you have just begun the Work.
>> here is Somehting that i can Help you out with.
>> Do U want to Load the Graph Network at all times and Create a
>> route for
>> Points A and B ?
>>
>> This is the most Optimum way of Doing that cause ur Data Change
>> would be minimum and Loading the graph in memory( provided its not
>> so huge ) would remove the overhead of Data reading and Graph
>> Creating Everythime for every request for a Route.
>>
>> Go through the Pathgenerators class which Allow you to find a Path
>> based on Constraints.Constrains can be Distance or Customized on
>> Various Parameters based on an interface. I think u will get
>> better idea of this when you look at the API's provided.
>> This Shoudl Solve your problem.Implementation of Routing
>> Algorithms is also there in geo-tools like Dijkstra's et all
>> ..making your job more simpler.
>>
>>
>> Am Providing a Sample Code for ur Understanding :
>> Graph g = lsg.getGraph(); // ge tthe Graph from the Data. or from
>> ur global variable.
>>
>> MEdgeWeighterImpl mwi = new MEdgeWeighterImpl(); //Cost based
>> Implementaion that u need to refer to from the API depending on
>> your needs ..Someitmes if Trafic data present then even that is to
>> be Consiered ..et all..
>> mwi.setEdgeCostMap(hmEdgeCost);
>> DijkstraShortestPathFinder dspf = new
>> DijkstraShortestPathFinder(g, srcNode, mwi);
>> dspf.calculate ();
>> Path p = dspf.getPath(destNode);
>> if (p != null) {
>> return p.getEdges();
>> // actual Rooute Edges .
>> } else
>> {
>> return null;
>> //No Route found Case .
>> }
>>
>>
>>
>>
>> Good Luck Dude ..happy Routing .
>>
>> Bye.
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> On Tue, 08 Nov 2005 Jase wrote :
>>
>>
>> >My current research involves using open source libraries to create
>> an online
>> >vehicle routing system for taxis or any vehicles as a matter of
>> fact. I have
>> >done some research and identified Geotools & Geoserver as the best
>> libraries
>> >for building such a system. After going through the mailing list,
>> it seems
>> >that the question I am going to ask is quite a common one afterall
>> but there
>> >is a lack of solution.
>> >
>> >I have a PostGIS database of roads in LineStrings. After
>> following the
>> >tutorials on graphing, I have managed to create the graph network
>> using the
>> >LineStringGraphGenerator. What I did was to load the entire
>> PostGIS database
>> >into the linestringgraphgenerator the and the output that I have
>> obtained
>> >using getGraph() is as follows:-
>> >
>> >V = [14042, 3162, 2002, 12968 … ]
>> >E = [20301 (6097, 20300) … ]
>> >Is it right to build the entire line network first before
>> traversing even
>> >though I do not know the points I would like to use?
>> >
>> >I understand I should traverse the graph but I am a bit stuck as
>> to how I
>> >should proceed. Say, if I would like to route from Point A to
>> Point B, how
>> >would I do that? As a matter of fact, I would like to locate the
>> closest
>> >vehicle in a particular area and find the quickest route to that
>> point. I
>> >see that there are many classes that are in the org.geotools.graph
>> package
>> >but I'm unsure on how to proceed.
>> >
>> >I appreciate if anyone can offer an insight to this.
>> >
>> >Thanks
>> >
>> >Jason
>>
>>
>>
>> <http://adworks.rediff.com/cgi-bin/AdWorks/sigclick.cgi/www.rediff.com/signature-home.htm/[EMAIL PROTECTED] >
>>
>>
>>
>
>
>
>
> -------------------------------------------------------
> SF.Net email is sponsored by:
> Tame your development challenges with Apache's Geronimo App Server.
> Download
> it for free - -and be entered to win a 42" plasma tv or your very own
> Sony(tm)PSP. Click here to play: http://sourceforge.net/geronimo.php
> _______________________________________________
> Geotools-gt2-users mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
>
--
Justin Deoliveira
The Open Planning Project
http://topp.openplans.org
