CGAL users discussion list

[Efi Fogel <>]

Hi Lee,

You can use CGAL  2D arrangements and 2D Minkowski sums to construct the configuration space and then apply all kind of computations to it. An example with explanations appears inSection 9.3.1 (A Translational Polygonal Robot) of our book:

Efi Fogel, Ron Wein, and Dan Halperin,
CGAL Arrangements and Their Applications, A Step-by-Step Guide. Springer, 2012 [link]

The code of the example can also be obtained from here (look for mp_tr_polygon.cpp).

Efi

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

On Mon, Sep 8, 2014 at 11:45 PM, Lee Croft <> wrote:

Hi,

I have a question regarding the algorithms available in CGAL. I am looking
for a shortest path algorithm which can handle shortest path queries in the
presence of polygonal obstacles in the two-dimensional Euclidean plane. Is
there anything like this in CGAL?

I have looked through the online user and reference manuals (package
overview and class and concept list) and I have searched the CGAL stack
exchange and this CGAL-Discuss archive but the only thing that I have found
which is available in relation to shortest paths is the Dijkstra's shortest
path algorithm coming from the Boost libraries which can only be applied to
graphs and not free space.

I am aware of the approach of computing a visibility graph and then running
Dijkstra's shortest path algorithm on this graph however I am looking to
implement the wavefront propagation approach of Suri and Hershberger and was
wondering if there is anything similar in CGAL.

Thanks,
Lee



--
View this message in context: http://cgal-discuss.949826.n4.nabble.com/Two-dimensional-Euclidean-shortest-path-algorithms-in-CGAL-tp4659808.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