The shortest way INSIDE a polygonal algorithm / pseudo-code

Question

I have a polygon (in PHP) represented by an array of points X, Y. I want to find the shortest path inside the polygon between point A and point B. In practical terms, I have an arbitrary area defined as a simple polygon about which I want to know the distance (for example, think of it as a polygon representing a trace - I want to evaluate how long the trail takes).

Look for pseudo code or a few tips on where to start. I browsed the Internet and it seemed unlucky, except for some it’s hard to understand the documents on triangulation and funnel algorithms.

Answer 1

Searching by shortest path through a polygon opens up many useful links. A good description of one algorithm is found here (complete with applet, animation algorithm in action). Many of the algorithms are designed for a more complex problem that allows holes in the polygon. They can be used unchanged for your case with a simple polygon. (In fact, your problem can be considered as a special case of finding a path through a common polygon in which all holes (obstacles) share a point with an edge.)

I think the best approach is to search A * through the space defined by the graph of visibility of the vertices of the polygon plus the start and end points (if they are no longer vertices).

Answer 2

A simple algorithm uses the fact that the path must move from the reflex vertex to the reflex vertex (with the exception of the first and last steps). So make a graph using all the reflex vertices and the start and end points, and use the standard shortest path algorithm to find the shortest path. I have a fairly short Mathematica code that does all this and will soon post a demo on the site.wolfram.com demo site. Send me a message if you want a code.