Visibility Graph

A vertex \(p_1\) that belongs to a polygon \(P\) is visible from vertex \(q_1\) that belongs to a polygon \(Q\) if the open segment going from \(p_1\) to \(q_1\) does not intersect with any other edge.

The Visibility Graph of a set of polygons \({P_1, P_2, ..., P_n}\) is the set of arcs that connects all the visible vertices.

The naive algorithm iterates each vertex of every polygon and it verifies its visibility against all other vertices. At each verification step the segment formed from one vertex to another should test that there is not any intersection with any other polygon. Thus the time complexity of this algorithm is \(O(n^3)\) where \(n\) is the total number of vertices. Other algorithms can compute the visibility graph in \(O(n^2log n)\) using a rotational sweep line to verify each vertex visibility. For simplicity reasons the \(O(n^3)\) algorithm will be used.

Returning to the robot path planning problem, remember that there are two types of representation spaces: a work space and a configuration space. In the work space the polygons represent the obstacles and the robot (represented by a polygon) is positioned somewhere in the arena (a plane) and plans to move to a goal position without colliding with any obstacle. However if the same problem is translated for the configuration space, the obstacles are the Minkownski Sum of the work-space obstacles and the robot polygon, being the later a point in space. In order to find the shortest path from the start robot position to the goal robot position it sufices to find the visibility graph between the obstacles and the two points (start and goal) each edge of a visibility graph is associated with a distance value that represents the cost of traveling from one point of the edge to another. Using Dijsktra's algorithm is possible to find the shortest path between the initial and the goal points and thus resolving the problem initially proposed.

Try it by yourself!

This is an example that shows the visibility graph (red edges) of five polygons in white color and two points. Dijkstra algorithm is used to find the shortest path between the two points through the visibility graph edges (green path).