[pgrouting-dev] driving_distance Synopsis

[Mario Basa]

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 at 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 at 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 at 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 at lists.osgeo.org
>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>>
>>>
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20120307/92d9448d/attachment.html