DEV Community

Cover image for Get the closest point on a polygon
Daniel Neveux
Daniel Neveux

Posted on

Get the closest point on a polygon

For the technical challenge of an interview, I had to write a function to get the closest point of a polygon from a given point.

I wrote this https://codesandbox.io/s/elated-liskov-3v65c

My solution will handle four cases:

  • Case I the target is inside the polygon ( the result is the point itself)
  • Case II the target is ON the polygon edge/vetext (the result is the point itself)
  • Case III - A the target is outside the polygon and faces an edge
  • Case III - B the target is outside the polygon and does not face an edge

Limitations:

  • Does not support hole or multi shapes
  • Return always one point (in case of equidistant points)

Case I

Use the winding Number algorithm to determin if the point is inside
If so, return the given point.

Case II

Check if the point P is on a edge AB of the polygon by comparing distances
AP + PB === AB

Case III

The point is outside the polygon.

A - The point projection is on a edge:

1- For each segment I will check if the perpendicular projection of the point is on the segment. (by using a vector projection)
2- I will take the segment which has the shortest projection distance.
The result will be the projection coordinates. (the resulting of the vector operation)

B - The point projection is not on a edge:

I will select the vertex which has the shortest distance with the point. (by getting the euclidian distance)

Top comments (1)

Collapse
 
xavvvier profile image
Javier Gonzalez

Thanks for sharing! Loved the explanation of the cases 👏🏼