Subject: CGAL users discussion list
List archive
- From: Lee Croft <>
- To:
- Subject: Re: [cgal-discuss] Two-dimensional Euclidean shortest path algorithms in CGAL
- Date: Tue, 9 Sep 2014 23:11:12 -0700 (PDT)
Hi,
Thank you for your response and the excellent reference material. I was
happy to find that your book was available at the library of my university.
If I understand correctly the approach in section 9.3.1 however, it is not
exactly what I am looking for. To my understanding, the free space is
sub-divided into convex cells which are then searched using the
breadth-first search to find a path from the source to the destination. This
however isn't guaranteed to be a shortest path due to the fact that the
cells would not be of uniform size. I suppose that the breadth-first search
could be substituted with a uniform-cost search or Dijkstra's algorithm
using the distances between the cell interiors and vertical edge midpoints
as weights in order to find the shortest path at the cost of a slightly
higher time complexity.
I should explain that the reason I am interested in shortest path algorithms
is due to the fact that I ultimately want to compute a geodesic Voronoi
diagram with polygonal obstacles in a two-dimensional Euclidean plane. Since
a multiple source shortest path map is essentially the same as this type of
Voronoi diagram I am hoping to find something in CGAL which computes a
shortest path map. My appologies for not stating this more clearly.
Thanks,
Lee
--
View this message in context:
http://cgal-discuss.949826.n4.nabble.com/Two-dimensional-Euclidean-shortest-path-algorithms-in-CGAL-tp4659808p4659817.html
Sent from the cgal-discuss mailing list archive at Nabble.com.
- [cgal-discuss] Two-dimensional Euclidean shortest path algorithms in CGAL, Lee Croft, 09/08/2014
- Re: [cgal-discuss] Two-dimensional Euclidean shortest path algorithms in CGAL, Efi Fogel, 09/09/2014
- Re: [cgal-discuss] Two-dimensional Euclidean shortest path algorithms in CGAL, Lee Croft, 09/10/2014
- Re: [cgal-discuss] Two-dimensional Euclidean shortest path algorithms in CGAL, Efi Fogel, 09/10/2014
- Re: [cgal-discuss] Two-dimensional Euclidean shortest path algorithms in CGAL, Lee Croft, 09/10/2014
- Re: [cgal-discuss] Two-dimensional Euclidean shortest path algorithms in CGAL, Efi Fogel, 09/09/2014
Archive powered by MHonArc 2.6.18.