Finding shortest path between two points in a polygon whose vertices are given?

Question

A contiguous single polygon is specified by it's vertices $(v_1, \ldots, v_n)$, given in order such that the line between $v_i$ and $v_{i+1}$ is an edge of the polygon (there's also an edge between $v_n$ and $v_1$). For example, a triangle might look like $v_1=(0, 0), v_2 = (1, 1), v_3 = (2, 0)$.

Anyways, given two points $p_1$ and $p_2$ that lie within the polygon, I want to find the shortest path between them. If the polygon is convex, this is obviously simple and just the line between the points. But in the worst case, the polygon can literally trace out a maze.

If possible, I'd like an answer that reduces this to a problem of finding the shortest path in a graph.

In particular, one idea I have is that, since the shortest path will have you always going between vertex to vertex (or between the initial/end point and a vertex), one constructs a graph of all vertices, with edges connecting them if there is a direct line (that doesn't exit the polygon) between them (and the edge having corresponding weight of the length of that direct line). This graph would also contain the start/end points, and edges between them and all their directly-accessible vertices. From there, you can just use something like A-star or Djikstra's on the graph to find the shortest path, I imagine.

The problems with my method are

1. given two vertices $v_i$ and $v_j$, how does one know whether the line between them doesn't exist the polygon?
2. Is there a significantly more efficient way of constructing the graph other than $O(n^2)$ checking every pair of vertices?
3. Is my method decently good, or is there a much more optimal standard solution for this problem?

I'd imagine that the solution to (1.) will take $O(n)$ time for each edge, making the entire algorithm take $O(n^3)$, which isn't...the best.

Answer 1

The graph that you defined is known as visibility graph. You can find a $O(n^2 \log n)$ algorithm here. There are other better algorithms stated in the first link. Note the algorithms are for the visibility graph over obstacles. However, you can use the same algorithm by creating a convex hull of the vertices of the polygon; and defining the region between the boundary of convex hull and the polygon to be obstacles.

---

There is dedicated chapter named ""Visibility Graphs" for the same problem in Computational Geometry book by Berg et al. You can find more recent results in its chapter notes.