DirectedDijkstra
|
|
iceDice
|
Hello,
These days i tried to play with GeoTools graph module and DijkstraShortestPathFinder in order to find the best route between two points on map. I used BasicLineGraphGenerator to create graph from line segments which are created from features. I also used DijkstraShortestPathFinder(graph, source, weighter) to find the best path between source and destination node. I also succeed to create shapefile which represents best path and display route on the map. Now i am trying to create graph which will take into consideration one way streets, but i can't see any way how to specify one way streets to Dijkstra algorithm. I searched forum and find out that i should use DijkstraShortestPathFinder(graph.getGraph(),Iterator) and define iterator as DirectedDijkstraIterator. However i have no idea how to do that, and i don't see how i can specify that some line segment(s) are one-way and others are not, and which street direction is banned. I tried to find something about this issue in user guide but there is nothing about it and because of that I am ready to put my final work as tutorial on wiki or something if i succeed to get results... I will be very grateful if someone can help me, Best regards. |
Jody Garnett-2
|
Some javascript/style in this post has been disabled (why?)
My understanding is you need to construct a graph of one way edges; and rather then one way streets being a special case - it is the two way streets that are special (you will need to add them to your graph twice; once in each direction).I would start by checking the test cases for examples of this ... I see one test for OptDirectedGraphBuilderTest that may be a good place to start? Jody On 12/08/2009, at 8:29 PM, iceDice wrote:
------------------------------------------------------------------------------ Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day trial. Simplify your report design, integration and deployment - and focus on what you do best, core application coding. Discover what's new with Crystal Reports now. http://p.sf.net/sfu/bobj-july _______________________________________________ Geotools-gt2-users mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users |
||||||||||||||||
|
iceDice
|
Hello,
If i understand you Jody i need to use OptDirectedGraphBuilder instead BasicLineGraphBuilder, and to add edges twice for two way streets and once for one way streets? For example for two way streets: OptDirectedGraphBuilder graph_builder = new OptDirectedGraphBuilder(); OptDirectedNode n1 = (OptDirectedNode) graph_builder.buildNode(); OptDirectedNode n2 = (OptDirectedNode) graph_builder.buildNode(); DirectedEdge e = (DirectedEdge) m_builder.buildEdge(n1, n2); m_builder.addEdge(e); e = (DirectedEdge) m_builder.buildEdge(n2, n1); m_builder.addEdge(e); However i am confused here because i have line segments as input data and there is no way to specify coordinates of start and end point to OptDirectedNode nodes. I suppose that start end end point of every line segment should be somehow mapped to OptDirectedNode n1 and n2? Best regards.
|
||||||||||||||||
|
Jody Garnett-2
|
Hi again:
The advice was to go through the test cases and look for an example; I just pointed out an example test case that seemed to have something to do with direction :-) Your data should have some information about the "direction" one way or two way; and if it is one way you will need to either: - check the data to see if it says which direction - assume that the start of your line string is the start; and the end of the line string is the end ... Jody On 12/08/2009, at 11:14 PM, iceDice wrote: > > Hello, > > If i understand you Jody i need to use OptDirectedGraphBuilder instead > BasicLineGraphBuilder, > and to add edges twice for two way streets and once for one way > streets? > For example for two way streets: > > OptDirectedGraphBuilder graph_builder = new > OptDirectedGraphBuilder(); > OptDirectedNode n1 = (OptDirectedNode) graph_builder.buildNode(); > OptDirectedNode n2 = (OptDirectedNode) graph_builder.buildNode(); > > DirectedEdge e = (DirectedEdge) m_builder.buildEdge(n1, n2); > m_builder.addEdge(e); > e = (DirectedEdge) m_builder.buildEdge(n2, n1); > m_builder.addEdge(e); > > However i am confused here because i have line segments as input > data and > there is no way to specify coordinates of start and end point to > OptDirectedNode nodes. > I suppose that start end end point of every line segment should be > somehow > mapped to > OptDirectedNode n1 and n2? > > Best regards. > > > Jody Garnett-2 wrote: >> >> My understanding is you need to construct a graph of one way edges; >> and rather then one way streets being a special case - it is the two >> way streets that are special (you will need to add them to your graph >> twice; once in each direction). >> >> I would start by checking the test cases for examples of this ... I >> see one test for OptDirectedGraphBuilderTest that may be a good place >> to start? >> >> Jody >> >> On 12/08/2009, at 8:29 PM, iceDice wrote: >> >>> >>> Hello, >>> >>> These days i tried to play with GeoTools graph module and >>> DijkstraShortestPathFinder in >>> order to find the best route between two points on map. >>> I used BasicLineGraphGenerator to create graph from line segments >>> which are >>> created from >>> features. I also used DijkstraShortestPathFinder(graph, source, >>> weighter) to >>> find the best path >>> between source and destination node. I also succeed to create >>> shapefile >>> which represents best >>> path and display route on the map. >>> >>> Now i am trying to create graph which will take into consideration >>> one way >>> streets, but i can't see >>> any way how to specify one way streets to Dijkstra algorithm. I >>> searched >>> forum and find out that i >>> should use DijkstraShortestPathFinder(graph.getGraph(),Iterator) and >>> define >>> iterator as >>> DirectedDijkstraIterator. However i have no idea how to do that, and >>> i don't >>> see how i >>> can specify that some line segment(s) are one-way and others are >>> not, and >>> which street direction is banned. >>> >>> I tried to find something about this issue in user guide but there >>> is >>> nothing about it and because of that I am >>> ready to put my final work as tutorial on wiki or something if i >>> succeed to >>> get results... >>> >>> I will be very grateful if someone can help me, >>> >>> Best regards. >>> -- >>> View this message in context: >>> http://n2.nabble.com/DirectedDijkstra-tp3429853p3429853.html >>> Sent from the geotools-gt2-users mailing list archive at Nabble.com. >>> >>> ------------------------------------------------------------------------------ >>> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 >>> 30-Day >>> trial. Simplify your report design, integration and deployment - and >>> focus on >>> what you do best, core application coding. Discover what's new with >>> Crystal Reports now. http://p.sf.net/sfu/bobj-july >>> _______________________________________________ >>> Geotools-gt2-users mailing list >>> [hidden email] >>> https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users >> >> >> ------------------------------------------------------------------------------ >> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 >> 30-Day >> trial. Simplify your report design, integration and deployment - >> and focus >> on >> what you do best, core application coding. Discover what's new with >> Crystal Reports now. http://p.sf.net/sfu/bobj-july >> _______________________________________________ >> Geotools-gt2-users mailing list >> [hidden email] >> https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users >> >> > > -- > View this message in context: http://n2.nabble.com/DirectedDijkstra-tp3429853p3430612.html > Sent from the geotools-gt2-users mailing list archive at Nabble.com. > > ------------------------------------------------------------------------------ > Let Crystal Reports handle the reporting - Free Crystal Reports 2008 > 30-Day > trial. Simplify your report design, integration and deployment - and > focus on > what you do best, core application coding. Discover what's new with > Crystal Reports now. http://p.sf.net/sfu/bobj-july > _______________________________________________ > Geotools-gt2-users mailing list > [hidden email] > https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users ------------------------------------------------------------------------------ Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day trial. Simplify your report design, integration and deployment - and focus on what you do best, core application coding. Discover what's new with Crystal Reports now. http://p.sf.net/sfu/bobj-july _______________________________________________ Geotools-gt2-users mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users |
||||||||||||||||
|
iceDice
|
Hi Jody,
Meantime i got some results using BasicDirectedLineGraphGenerator and DirectedDijkstraIterator and find way to tell graph if some edge is one or two way. I understand that i must have information about direction in my data, however i am curious how is it specified in GIS world? I mean what is common way to specify street direction in GIS world? Thank you for all your help! Best regards.
|
||||||||||||||||
Andy Turner
|
Hi,
This is perhaps worth looking into: http://wiki.openstreetmap.org/wiki/Traveling_salesman It is based on Open Street Map data, but I think with the companion libraries, it provides an example. I have just started using it, so am still learning about how mature it is, but I think it is a good development which may be of general interest... Best wishes, Andy http://www.geog.leeds.ac.uk/people/a.turner/ -----Original Message----- From: iceDice [mailto:[hidden email]] Sent: 12 August 2009 16:02 To: [hidden email] Subject: Re: [Geotools-gt2-users] DirectedDijkstra Hi Jody, Meantime i got some results using BasicDirectedLineGraphGenerator and DirectedDijkstraIterator and find way to tell graph if some edge is one or two way. I understand that i must have information about direction in my data, however i am curious how is it specified in GIS world? I mean what is common way to specify street direction in GIS world? Thank you for all your help! Best regards. Jody Garnett-2 wrote: > > Hi again: > > The advice was to go through the test cases and look for an example; I > just pointed out an example test case that seemed to have something > to do with direction :-) > > Your data should have some information about the "direction" one way > or two way; and if it is one way you will need to either: > - check the data to see if it says which direction > - assume that the start of your line string is the start; and the end > of the line string is the end ... > > Jody > > On 12/08/2009, at 11:14 PM, iceDice wrote: > >> >> Hello, >> >> If i understand you Jody i need to use OptDirectedGraphBuilder instead >> BasicLineGraphBuilder, >> and to add edges twice for two way streets and once for one way >> streets? >> For example for two way streets: >> >> OptDirectedGraphBuilder graph_builder = new >> OptDirectedGraphBuilder(); >> OptDirectedNode n1 = (OptDirectedNode) graph_builder.buildNode(); >> OptDirectedNode n2 = (OptDirectedNode) graph_builder.buildNode(); >> >> DirectedEdge e = (DirectedEdge) m_builder.buildEdge(n1, n2); >> m_builder.addEdge(e); >> e = (DirectedEdge) m_builder.buildEdge(n2, n1); >> m_builder.addEdge(e); >> >> However i am confused here because i have line segments as input >> data and >> there is no way to specify coordinates of start and end point to >> OptDirectedNode nodes. >> I suppose that start end end point of every line segment should be >> somehow >> mapped to >> OptDirectedNode n1 and n2? >> >> Best regards. >> >> >> Jody Garnett-2 wrote: >>> >>> My understanding is you need to construct a graph of one way edges; >>> and rather then one way streets being a special case - it is the two >>> way streets that are special (you will need to add them to your graph >>> twice; once in each direction). >>> >>> I would start by checking the test cases for examples of this ... I >>> see one test for OptDirectedGraphBuilderTest that may be a good place >>> to start? >>> >>> Jody >>> >>> On 12/08/2009, at 8:29 PM, iceDice wrote: >>> >>>> >>>> Hello, >>>> >>>> These days i tried to play with GeoTools graph module and >>>> DijkstraShortestPathFinder in >>>> order to find the best route between two points on map. >>>> I used BasicLineGraphGenerator to create graph from line segments >>>> which are >>>> created from >>>> features. I also used DijkstraShortestPathFinder(graph, source, >>>> weighter) to >>>> find the best path >>>> between source and destination node. I also succeed to create >>>> shapefile >>>> which represents best >>>> path and display route on the map. >>>> >>>> Now i am trying to create graph which will take into consideration >>>> one way >>>> streets, but i can't see >>>> any way how to specify one way streets to Dijkstra algorithm. I >>>> searched >>>> forum and find out that i >>>> should use DijkstraShortestPathFinder(graph.getGraph(),Iterator) and >>>> define >>>> iterator as >>>> DirectedDijkstraIterator. However i have no idea how to do that, and >>>> i don't >>>> see how i >>>> can specify that some line segment(s) are one-way and others are >>>> not, and >>>> which street direction is banned. >>>> >>>> I tried to find something about this issue in user guide but there >>>> is >>>> nothing about it and because of that I am >>>> ready to put my final work as tutorial on wiki or something if i >>>> succeed to >>>> get results... >>>> >>>> I will be very grateful if someone can help me, >>>> >>>> Best regards. >>>> -- >>>> View this message in context: >>>> http://n2.nabble.com/DirectedDijkstra-tp3429853p3429853.html >>>> Sent from the geotools-gt2-users mailing list archive at Nabble.com. >>>> >>>> ------------------------------------------------------------------------------ >>>> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 >>>> 30-Day >>>> trial. Simplify your report design, integration and deployment - and >>>> focus on >>>> what you do best, core application coding. Discover what's new with >>>> Crystal Reports now. http://p.sf.net/sfu/bobj-july >>>> _______________________________________________ >>>> Geotools-gt2-users mailing list >>>> [hidden email] >>>> https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users >>> >>> >>> ------------------------------------------------------------------------------ >>> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 >>> 30-Day >>> trial. Simplify your report design, integration and deployment - >>> and focus >>> on >>> what you do best, core application coding. Discover what's new with >>> Crystal Reports now. http://p.sf.net/sfu/bobj-july >>> _______________________________________________ >>> Geotools-gt2-users mailing list >>> [hidden email] >>> https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users >>> >>> >> >> -- >> View this message in context: >> http://n2.nabble.com/DirectedDijkstra-tp3429853p3430612.html >> Sent from the geotools-gt2-users mailing list archive at Nabble.com. >> >> ------------------------------------------------------------------------------ >> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 >> 30-Day >> trial. Simplify your report design, integration and deployment - and >> focus on >> what you do best, core application coding. Discover what's new with >> Crystal Reports now. http://p.sf.net/sfu/bobj-july >> _______________________________________________ >> Geotools-gt2-users mailing list >> [hidden email] >> https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users > > > ------------------------------------------------------------------------------ > Let Crystal Reports handle the reporting - Free Crystal Reports 2008 > 30-Day > trial. Simplify your report design, integration and deployment - and focus > on > what you do best, core application coding. Discover what's new with > Crystal Reports now. http://p.sf.net/sfu/bobj-july > _______________________________________________ > Geotools-gt2-users mailing list > [hidden email] > https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users > > -- View this message in context: http://n2.nabble.com/DirectedDijkstra-tp3429853p3431330.html Sent from the geotools-gt2-users mailing list archive at Nabble.com. ------------------------------------------------------------------------------ Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day trial. Simplify your report design, integration and deployment - and focus on what you do best, core application coding. Discover what's new with Crystal Reports now. http://p.sf.net/sfu/bobj-july _______________________________________________ Geotools-gt2-users mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users ------------------------------------------------------------------------------ Come build with us! The BlackBerry® Developer Conference in SF, CA is the only developer event you need to attend this year. Jumpstart your developing skills, take BlackBerry mobile applications to market and stay ahead of the curve. Join us from November 9-12, 2009. Register now! http://p.sf.net/sfu/devconf _______________________________________________ Geotools-gt2-users mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users |
||||||||||||||||
|
Andy Turner
|
Hi,
I want to do some routing along a set of lines from origin points to destination points. I have noticed that others on this list are working on this sort of thing too. I've not got very far yet, so I am hoping that others at a more advanced stage will collaborate with me. I am currently using a set of lines in a single shapefile. The origin and destination points do not necessarily intersect any line, but they are sort of fixed. What I have thought is that I should produce a new dataset of lines which include those linked with origin and destination points. I should also find out more about what routing there is... TIA Andy http://www.geog.leeds.ac.uk/people/a.turner/ ------------------------------------------------------------------------------ Come build with us! The BlackBerry® Developer Conference in SF, CA is the only developer event you need to attend this year. Jumpstart your developing skills, take BlackBerry mobile applications to market and stay ahead of the curve. Join us from November 9-12, 2009. Register now! http://p.sf.net/sfu/devconf _______________________________________________ Geotools-gt2-users mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users |
||||||||||||||||
| Free Embeddable Forum Powered by Nabble | Help |
