Problem History/ Origin
Lately I stumbled over channels on Twitch.TV from players that perform speedruns of classic games. One of them played The Legend of Zelda - A Link to the Past. I saw many inefficient movements and I started to wonder if - given the world map data - it would be possible to write a bot that performs perfect speedruns. One quite frequently arising subproblem would be to find shortest paths between two points in a plane which I figured was such an interesting problem that I started to do more research on this.
Similar Stackoverflow Questions have been posted
Finding path obstacles in a 2D image
Algorithm to detect corners of paper sheet in photo
... and more
Of which the answers always provided a different solution to the Superproblem (described below) like using a grid based approach but not the actual Subproblem I am interested in (described below).
Superproblem Solution Description
Given two points X=(x1,x2) and Y=(y1,y2) in a plane - What is the shortest path from X to Y if the plane contains obstacles/ regions through which the path may not lead?
Differently/ More visually What is the shortest path from Link`s current position to the second red dot on the map given he cannot climb over walls or walk through bushes?
This problem is generally known as the Eucledian Shortest Path Problem and can be solved in Polynomial time in the 2-dimensional case. Awesome!
To achieve this, a so called Visibility Graph with V= {X,Y} U {"Corner-Points of obstacles}" is constructed. Edges are inserted between points P and Q if and only if it is possible to draw a straight line from P to Q without crossing any obstacle. Each edge is weighted by the Eucledian Distance between the points it connects.
In the example above the Visibility Graph would look something like this. I omitted a few edges and weights for the sake of readability. Shaded areas illustrate obstacles.
Then a shortest path can be computed using the developer's favourite Shortest Path Algorithm on the Visibility Graph.
Subproblem Description
Let us start by defining an obstacle as a continuous region of impassable terrain. How would one find the minimal number of required corners of all obstacles (and the coordinates of the corners as well) to construct the smallest possible Visibility Graph required to perform Shortest Path calculations?
For rectangular obstacles it is rather easy to find the corners as there are only few sharp edges as shown in the sketch ...
... or applied to an in-game scenario
However, as soon as the obstacles have diagonal "fronts", obtaining the corners becomes non-trivial due to the induced jigsaw-pattern (no matter the angle). The following screenshot illustrates this problem: The left hand side image shows at which coordinates points should be identified as corners whereas the right hand side picture shows where additional points would be inserted due to the "jigsaw"-pattern of diagonal lines.
The question now is: How can I exclude/ prevent these unnecessary corner points from (being inserted into) the possibly very large Visibility Graph?
