Hello list.
I am interested in digging in more to the driving_distance functions to do some refining and perhaps improve the usefulness of the results (http://lists.osgeo.org/pipermail/pgrouting-dev/2012-February/000458.html).
Having a hard time deciphering the current implementation, mostly because of my lack of familiarity with c/c++. Is there someone who wouldn’t mind giving a synopsis of the overall approach that the algorithm takes?
Thanks!
Hello Steve,
I wrote the initial code for the driving_distance, although Anton modified it quite a bit afterwards.
Basically it uses a slightly modified Dijkstra that traverses the graph from a starting point while measuring the lenght/time along the way. After a set length/time has been reached, all the nodes (along with the x,y coordinates) are passed to CGAL to get the outer points and create a concave hull polygon.
The bottleneck here is in the passing of the nodes since in a dense graph, the data can be quite large. Anton and I were trying all sorts of ways to filter first the nodes, but couldn’t find an efficient method without loosing accuracy.
Regards,
Mario.
On Wed, Mar 7, 2012 at 9:36 AM, Steve Horn steve@stevehorn.cc wrote:
Hello list.
I am interested in digging in more to the driving_distance functions to do some refining and perhaps improve the usefulness of the results (http://lists.osgeo.org/pipermail/pgrouting-dev/2012-February/000458.html).
Having a hard time deciphering the current implementation, mostly because of my lack of familiarity with c/c++. Is there someone who wouldn’t mind giving a synopsis of the overall approach that the algorithm takes?
Thanks!
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
Hi Steve,
My answer probably isn’t complete, but I hope others will add additional comments.
This is what I think could be improved:
Driving Distance should have the possibility to return a polygon, but the “core” algorithm should just return a list of points that are within driving distance together with useful attributes as for example the cost to reach the point, or the previous point ID.
Currently it requires CGAL for the “alphashape” function. It would be nice, not to have CGAl as a dependency. With PostGIS 2.0 it’s maybe possible to use ST_ConcaveHull instead.
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_2/Chapter_main.html
For large networks it’s a good idea to select only a small part (BBOX). This is easy as long as the cost attribute is in the same unit as the network data (ie. degree or meter). But if the cost is time for example, how to define a BBOX extent? If the BBOX is too small the driving distance area will look like the BBOX itself 
Daniel
On Wed, Mar 7, 2012 at 10:36 AM, Steve Horn steve@stevehorn.cc wrote:
Hello list.
I am interested in digging in more to the driving_distance functions to do some refining and perhaps improve the usefulness of the results (http://lists.osgeo.org/pipermail/pgrouting-dev/2012-February/000458.html).
Having a hard time deciphering the current implementation, mostly because of my lack of familiarity with c/c++. Is there someone who wouldn’t mind giving a synopsis of the overall approach that the algorithm takes?
Thanks!
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de
On Tue, Mar 6, 2012 at 9:01 PM, Daniel Kastl <daniel@georepublic.de> wrote:
Hi Steve,
My answer probably isn’t complete, but I hope others will add additional comments.
This is what I think could be improved:
Driving Distance should have the possibility to return a polygon, but the “core” algorithm should just return a list of points that are within driving distance together with useful attributes as for example the cost to reach the point, or the previous point ID.
Currently it requires CGAL for the “alphashape” function. It would be nice, not to have CGAl as a dependency. With PostGIS 2.0 it’s maybe possible to use ST_ConcaveHull instead.
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_2/Chapter_main.html
I’ve been using the points_as_polygon successfully. It would be nice to be able to have some ability to fine tune the alpha shape, but it does the job.
- For large networks it’s a good idea to select only a small part (BBOX). This is easy as long as the cost attribute is in the same unit as the network data (ie. degree or meter). But if the cost is time for example, how to define a BBOX extent? If the BBOX is too small the driving distance area will look like the BBOX itself
My use case works with time (how far can I travel in n minutes). Streets/highways in the US rarely exceed 65mph/100kmph so I make my BBOX the size of the maximum possible distance that would be able to be traveled if all streets in all directions were the max speed.
Daniel
On Wed, Mar 7, 2012 at 10:36 AM, Steve Horn steve@stevehorn.cc wrote:
Hello list.
I am interested in digging in more to the driving_distance functions to do some refining and perhaps improve the usefulness of the results (http://lists.osgeo.org/pipermail/pgrouting-dev/2012-February/000458.html).
Having a hard time deciphering the current implementation, mostly because of my lack of familiarity with c/c++. Is there someone who wouldn’t mind giving a synopsis of the overall approach that the algorithm takes?
Thanks!
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
–
Steve Horn
http://www.stevehorn.cc
steve@stevehorn.cc
http://twitter.com/stevehorn
740-503-2300
First of all, thanks for your contribution! I am using it successfully and am getting great results.
Can you expound a little more on “uses a slightly modified Dijkstra”? I’m trying to imagine how you start from the starting vertex and “crawl” out to all the surrounding vertexes.
On Tue, Mar 6, 2012 at 9:00 PM, Mario Basa <mario.basa@gmail.com> wrote:
Hello Steve,
I wrote the initial code for the driving_distance, although Anton modified it quite a bit afterwards.
Basically it uses a slightly modified Dijkstra that traverses the graph from a starting point while measuring the lenght/time along the way. After a set length/time has been reached, all the nodes (along with the x,y coordinates) are passed to CGAL to get the outer points and create a concave hull polygon.
The bottleneck here is in the passing of the nodes since in a dense graph, the data can be quite large. Anton and I were trying all sorts of ways to filter first the nodes, but couldn’t find an efficient method without loosing accuracy.
Regards,
Mario.
On Wed, Mar 7, 2012 at 9:36 AM, Steve Horn steve@stevehorn.cc wrote:
Hello list.
I am interested in digging in more to the driving_distance functions to do some refining and perhaps improve the usefulness of the results (http://lists.osgeo.org/pipermail/pgrouting-dev/2012-February/000458.html).
Having a hard time deciphering the current implementation, mostly because of my lack of familiarity with c/c++. Is there someone who wouldn’t mind giving a synopsis of the overall approach that the algorithm takes?
Thanks!
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
–
Steve Horn
http://www.stevehorn.cc
steve@stevehorn.cc
http://twitter.com/stevehorn
740-503-2300
On 3/6/2012 8:36 PM, Steve Horn wrote:
Hello list.
I am interested in digging in more to the driving_distance functions to
do some refining and perhaps improve the usefulness of the results
(http://lists.osgeo.org/pipermail/pgrouting-dev/2012-February/000458.html).Having a hard time deciphering the current implementation, mostly
because of my lack of familiarity with c/c++. Is there someone who
wouldn't mind giving a synopsis of the overall approach that the
algorithm takes?
Mario and Daniel thank you for your responses. It is really good to know why the existing code is structured the way it is and I'm sure it will help Steve find his way through the code.
I would like to propose a more layered approach to solving this problem. There are benefits and downsides to this approach, so let me throw this out for discussion.
I see the problem like this:
1. compute the points by solving the graph for some maximum cost where we get back a set of: node, cost, x, y
select * from pgr_driving_distance(sql_for_edges, node_id, cost_column, maxcost);
2. separate from 1. have a function(s) to post process a of: node, cost, x, y
select cost, polygon from pgr_alphashapes(sql_for_points, maxcost, slice);
3. optionally, for performance is needed, create a combined function of 1 and 2 in a single call.
select cost, polygon from pgr_driving_distance_alphashapes(sql_for_edges, node_id, cost_column, maxcost, slice);
One of the reasons for this, is that this would make it easy to replace the pgr_alphashapes() algorithm with postgis convexhull, concavehull, points_as_polygon, or a triangular surface generator that I have that then slice the surface into contours.
If the cost of passing a lot of data about is too much then you can later optimize it with step 3 above, but I would focus on keeping the pieces smaller and modular like postgis so that we can reuse the components.
-Steve
Dijkstra traverses each node of the graph and returns to the specified start node to determine (calculate) the shortest path based on the cost.
For driving-distance, the Dijkstra algorithm was modified so that it does not have to return back, and instead just accumulate the cost of each node from the start node while traversing the graph.
Mario.
On Wed, Mar 7, 2012 at 10:19 AM, Steve Horn steve@stevehorn.cc wrote:
First of all, thanks for your contribution! I am using it successfully and am getting great results.
Can you expound a little more on “uses a slightly modified Dijkstra”? I’m trying to imagine how you start from the starting vertex and “crawl” out to all the surrounding vertexes.
On Tue, Mar 6, 2012 at 9:00 PM, Mario Basa <mario.basa@gmail.com> wrote:
Hello Steve,
I wrote the initial code for the driving_distance, although Anton modified it quite a bit afterwards.
Basically it uses a slightly modified Dijkstra that traverses the graph from a starting point while measuring the lenght/time along the way. After a set length/time has been reached, all the nodes (along with the x,y coordinates) are passed to CGAL to get the outer points and create a concave hull polygon.
The bottleneck here is in the passing of the nodes since in a dense graph, the data can be quite large. Anton and I were trying all sorts of ways to filter first the nodes, but couldn’t find an efficient method without loosing accuracy.
Regards,
Mario.
On Wed, Mar 7, 2012 at 9:36 AM, Steve Horn steve@stevehorn.cc wrote:
Hello list.
I am interested in digging in more to the driving_distance functions to do some refining and perhaps improve the usefulness of the results (http://lists.osgeo.org/pipermail/pgrouting-dev/2012-February/000458.html).
Having a hard time deciphering the current implementation, mostly because of my lack of familiarity with c/c++. Is there someone who wouldn’t mind giving a synopsis of the overall approach that the algorithm takes?
Thanks!
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev–
Steve Horn
http://www.stevehorn.cc
steve@stevehorn.cc
http://twitter.com/stevehorn
740-503-2300
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
On 3/6/2012 11:11 PM, Mario Basa wrote:
Dijkstra traverses each node of the graph and returns to the specified
start node to determine (calculate) the shortest path based on the cost.For driving-distance, the Dijkstra algorithm was modified so that it
does not have to return back, and instead just accumulate the cost of
each node from the start node while traversing the graph.Mario.
On Wed, Mar 7, 2012 at 10:19 AM, Steve Horn <steve@stevehorn.cc> wrote:
First of all, thanks for your contribution! I am using it
successfully and am getting great results.Can you expound a little more on "uses a slightly modified
Dijkstra"? I'm trying to imagine how you start from the starting
vertex and "crawl" out to all the surrounding vertexes.
Steve,
Dijkstra does not crawl out to each node, it instead converts the graph into a tree with the start node as the root of the tree. So from the root node you can travel only to the connected nodes down the tree, and from each of those nodes only down to the connected nodes again. Once a node has been added to the tree it is marked in the graph so you can node add it again unless it is a smaller cost, then you have to fixup the tree. And so on and so on. The algorithms in graph theory are designed for the most part to convert complex problems of analyzing graphs into simpler problems that are easier to solve. In the case of Dijkstra, the resulting tree represents the possible paths that one could "crawl". If you sum the cost of each edge in the tree to a leaf node that is the cost to get there.
The slightly modified Dijkstra keeps that summed cost as the tree is developed, so you do not have to do the summing at the end.
-Steve
On Tue, Mar 6, 2012 at 9:00 PM, Mario Basa <mario.basa@gmail.com
<mailto:mario.basa@gmail.com>> wrote:Hello Steve,
I wrote the initial code for the driving_distance, although
Anton modified it quite a bit afterwards.Basically it uses a slightly modified Dijkstra that traverses
the graph from a starting point while measuring the lenght/time
along the way. After a set length/time has been reached, *all*
the nodes (along with the x,y coordinates) are passed to CGAL to
get the outer points and create a concave hull polygon.The bottleneck here is in the passing of the nodes since in a
dense graph, the data can be quite large. Anton and I were
trying all sorts of ways to filter first the nodes, but couldn't
find an efficient method without loosing accuracy.Regards,
Mario.
On Wed, Mar 7, 2012 at 9:36 AM, Steve Horn <steve@stevehorn.cc>
wrote:Hello list.
I am interested in digging in more to the driving_distance
functions to do some refining and perhaps improve the
usefulness of the results
(http://lists.osgeo.org/pipermail/pgrouting-dev/2012-February/000458.html).Having a hard time deciphering the current implementation,
mostly because of my lack of familiarity with c/c++. Is
there someone who wouldn't mind giving a synopsis of the
overall approach that the algorithm takes?Thanks!
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
<mailto:pgrouting-dev@lists.osgeo.org>
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev--
Steve Horn
http://www.stevehorn.cc
steve@stevehorn.cc
http://twitter.com/stevehorn
740-503-2300 <tel:740-503-2300>_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev