Re: Re: [Geotools-gt2-users] LineString Graph Traversal

Tue, 15 Nov 2005 01:04:01 -0800

  Hi ,

  I have implemented a part of this.
  First in your Scenario I would Like to know if u have more than One 
  Layer on which U want to perform Routing ?
  If yes then u need to merge the layers and Make edges based on the 
  Constraints.Once u have done this ..Identify the source Point.
  ( Its possible the Source Point May not match with that on the Line 
  layer. You Now need to make a Query on the Line Layer to get u the
  point that lies on the Line and is within a Specified Distance.(this
  distance can be based on the densitity of the Route Network you
  have.)) The Same thing applies for your destination Point as well.
  Once u have got these Points u can continue as I have given the Code.
  I will look for nearest point Code also and will send it ..I dont 
  remem the exact fiels where i had done that.
  Anyways ..One problem u have here :
  Once u find the Point nearest to the RouteLine Layer and make the Route ..the  Entire feature turns up in the route.Thus U can see a lag in the Point that was given and the route being shown.

To overcome this I used to split the feature at source and destination in 2 and make edges of them ..thus only that part is selected which falls in the Route.

I hope am making sense to you.

Bye.







 
 





On Tue, 15 Nov 2005 Jase wrote :
>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]> 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
> >



Reply via email to