DEV Community

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

Posted on

4

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)

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more

Top comments (1)

Collapse
 
xavvvier profile image
Javier Gonzalez

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