[pgrouting-dev] driving_distance Synopsis

[Steve Horn]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20120306/c8c984c3/attachment-0001.html