Jase wrote:
The linestring graph generator does not take internal intersections of
lines into account when building the graph. What you will need to do as
a preprocessing step is run all of your line strings through a routine
that calculates when they intersect, and then splits them accordingly
(creating a node when the graph is built). The pathing algorithms should
then have the desired affect. If you are an FME user, this is trivial.
If not, writing the splitting routine shouldn't be too hard. You could
essentially write a n^2 algorithm to do a double pass over the dataset,
searching for internal intersections, when one is found, do the split,
and then replace the two original lines with the 4 (or 3 as a special
case) new lines. Using a spatial index can bring it down to nlog(n).
Please let me know if you have any more questions.
Justin
I did some reading on JTS after Jody pointed me to the right direction.
Here is what I would like to do...
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]
<mailto:[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]> <mailto:
[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]
<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
<http://sourceforge.net/geronimo.php>
> _______________________________________________
> Geotools-gt2-users mailing list
> [email protected]
<mailto:[email protected]>
> https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
>
--
Justin Deoliveira
The Open Planning Project
http://topp.openplans.org
--
Justin Deoliveira
The Open Planning Project
http://topp.openplans.org
-------------------------------------------------------
This SF.Net email is sponsored by the JBoss Inc. Get Certified Today
Register for a JBoss Training Course. Free Certification Exam
for All Training Attendees Through End of 2005. For more info visit:
http://ads.osdn.com/?ad_id=7628&alloc_id=16845&op=click
_______________________________________________
Geotools-gt2-users mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
