Closest Point on a Polygon
“In computational geometry, the closest point on a polygon asks to find a point on the polygon which is closest to the given point. A quick and simple algorithm to find this is very useful in various applications like computer graphics, geographical information systems (GIS), motion planning, CAD, etc.”
Some of the applications of the given problem are:
- To find the closest position to the mouse cursor inside a room using a CAD.
- One of the most basic questions asked of a GIS is “what’s near what?” For example: How close is this well to a landfill? This method can be used to answer these questions.
For solving this problem, I decided to divide the problem into 3 cases:
- Case 1: When the given point is inside the polygon.
- Case 2: When the given point is either on the edge or vertex of the polygon.
- Case 3: When the given point is outside the polygon.
Case 1: Point inside the Polygon
For this case, the problem reduces to the point in polygon(PIP) problem. To solve this case I used the Jordan Curve theorem. The Jordan Curve Theorem states that a point is inside a polygon if the number of crossings of a ray from that point in an arbitrary direction is odd.
It can be explained better with an image so let’s take a look at this figure. As you can see points 1 and 3 are inside the polygon but point 2 is not because point 1 has 1 crossing (odd), 2 has 2 crossings (even) and 3 has 3 crossings (odd).
I ran a semi-infinite ray horizontally (increasing x, fixed y) out from the test point, and count how many edges it crosses. At each crossing, the ray switches between inside and outside. For this case, the closest point to that point is the point itself.
Case 2: Point on the Polygon
For this case, you can check the distance of the point (P) from both the vertices(A, B) of the edge(AB). If it lies on the polygon, then the sum of distance(AP+PB) will be the same as the length of the edge(AB).
The closest point is the point itself. Consider two points P (on the edge of the polygon) and Q (not on the edge) as shown in the figure. It can be clearly seen that, AP+PB = AB but AQ+QB != AB.
Case 3: Point outside the Polygon
For this case, you first need to find the edge on which the perpendicular projection of the point lies.
To find the closest point, there are 3 possibilities. In the first case, the point (P0) lies in between the edges P1 & P2 because 0< cosine(parameter) <= 1. The closest point will be the foot (f) of the perpendicular from that point. In the second case, the perpendicular projection of P0 is not on the side and lies near P1 as cosine<0, then the closest point will be P1. In the third case, the perpendicular projection of P0 is not on the side and lies near P2 as cosine>1, then the closest point will be P2.
To conclude, we developed a method to find the point inside or on the polygon which is closest to a given point. This method works for any polygon with any number of edges. However, my solution does not work when there are holes in the polygon. Also, for the case of multiple equidistant points, it always returns one point.
Github link for full code: https://github.com/danijak/GetClosestPointOnPolygon