[pgrouting-dev] Driving Distance Help

[Stephen Woodbridge]

On 2/19/2012 7:20 PM, Steve Horn wrote:
> Steve,
> I've been working with the driving_distance function in pgRouting, and
> as far as I can tell it is one contour at a time.

Yeah, digging through the code that was my conclusion also.

> A possible way to improve the function is to make the result set a
> little more useful. If I was able to follow a path from the centerpoint
> to the extent of the contour via a tree structure I would be able to
> create one contour for a maximum radius, then on the client derive
> countours for less time.

I have done some work on this for some projects that I have worked on, 
but it is all outside pgRouting and the database. I have a modified 
drivingdistance function somewhere that does the following.

> The tuple returned could be something like:
> vertex_id, parent_vertex_id, cost

I used this when I was trying to develop a map matching algorithm. For 
driving distance I give it a max cutoff and a slice then get all the 
points for the max cutoff and compute all the contours at once. If you 
take the x,y of the node and z=cost, you can build a 3D triangulated 
surface and slice it into multiple contours.

> Another improvement to the function would be to return an extra edge
> past the max cost (or make that an option). I think currently the
> algorithm will not return any edges that put the total cost past the
> input cost parameter. My thought is I could take the extra edge and then
> interpolate the point on the line that meets my cost exactly (or, even
> better - have the algorithm compute this).

Agreed, I did this in my version of the code. If I get some time or a 
contract to support it, I want to clean up what I have done outside of 
pgRouting and move it into pgRouting.

The problem is the coding up cool little algorithms is the 10% of the 
work that is fun and it takes 90% more effort to clean up the code, 
check it in, write documentation, etc.

We really need to get a developer that is interested in pulling together 
a release and helping to build out our testing and release tools.

Thanks,
  -Steve

> On Sun, Feb 19, 2012 at 3:01 PM, Stephen Woodbridge
> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>
>     Hi all,
>
>     Since I wrote my own driving distance code years ago and have been
>     happy with it, I have just now looked into how the pgRouting code works.
>
>     Does this code return multiple contours in a single request? How?
>
>     It looks like this code can only return a single contour for a
>     single request. This means if I want say contours for 5, 10, 15
>     minutes that I have to make 3 requests which means fetching the
>     data, building the graph and creating the contours all have to be
>     processed 3 times. It seem that it would make more sense to setup
>     the problem once and compute all the contours at once and return 3
>     results.
>
>     Thoughts?
>
>     -Steve
>     ______________________________ _________________
>     pgrouting-dev mailing list
>     pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
>     http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>     <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>
>
>
>
> --
> Steve Horn
> http://www.stevehorn.cc
> steve at stevehorn.cc
> http://twitter.com/stevehorn
> 740-503-2300
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev