[pgrouting-dev] driving_distance Synopsis

[Stephen Woodbridge]

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