CGAL users discussion list

[Rémi Cura <>]

Hey,
Just an idea,

If there is a direct line between both points, easy.
Else :

break the polygon into triangles/convex parts (should be possible to scavenge that also).
http://doc.cgal.org/latest/Triangulation_2/index.html
http://doc.cgal.org/latest/Partition_2/index.html

Then you problem is much more simpler :
_building the 2D arrangement graph with all the triangles vertex, you are looking for the shortest path,
which you can solve using Dijkstra for instance (http://doc.cgal.org/latest/BGL/index.html).

Then it is almost over, you only need to optimize your path a bit by replacing some tuple of consecutive segment by one segment.

Cheers,

Rémi-C

2014-04-30 2:18 GMT+02:00 dg <>:

Hi all,

I want to find the shortest distance path between two points in a simple
polygon without holes.
Could anyone guide me if there exists such an algorithm implemented in CGAL
? The implementation might not be optimal, thats Ok.

I came across the Rubber-band algorithm research paper but couldnt find any
existing implementation in CGAL or elsewhere. Please help.

Thanks in advance.
dg.



--
View this message in context: http://cgal-discuss.949826.n4.nabble.com/Shortest-distance-path-between-two-points-in-a-simple-polygon-tp4659225.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