CGAL users discussion list

[Efi Fogel <>]

You are correct. The example program does not compute the shortest path.

I guess the shortest path would be a polyline that comprises either
- a segment from the source to the destination,
- two segments one from the source and one to the destination, where their common endpoint coincides with an obstacle vertex, or
- more than two segments: two segments one from the source and one to the destination; the remaining segments overlap the convex hull of the obstacles.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Wed, Sep 10, 2014 at 9:11 AM, Lee Croft <> wrote:

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.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss