# How can I find closest point on a polygon from a point

I have a point that may be inside or outside of a polygon, I need to find the nearest point on the polygon boundary from the point.

Point(x,y) may be inside or outside of the polygon, shortest distance between polygon ABCDE and point(x,y) is marked as red line, the intersecting point is Point (m,n). I need the value of m and n.

I have ABCDE and Point(x,y)

-
I'm afraid your question is not clear. Could you indicate with an image what exactly you need? – Devdatta Tengshe Jul 4 '14 at 6:28
Sorry .Now I was add an image – Virender Sehwag Jul 4 '14 at 6:42

You can get it with JSTS.

Check DistanceOp.js.

-
but I am using google map – Virender Sehwag Jul 4 '14 at 10:33
There is not such feature in gmap (AFAIK). Can't you use gmap and JSTS together? – julien Jul 4 '14 at 13:36
Correct link to DistanceOp.js – Björn Harrtell Feb 29 at 20:11
Link corrected. Thanks ! – julien Feb 29 at 21:47

Find the two nearest points to your point; just do this with pythagoras, but don't sqrt, you don't need the distance, only the order.

Work out the gradient between these two points (y1-y2)/(x1-x2) where 1 is one of the points and 2 is the other. This is from solving y=mx+c for m for the two points (simultaneous equation). Then use one of these points to calculate c by substituting back into the equation y=m*x+c for one of the two points, you'll use this later.

Divide -1 by this gradient, called mn (This calculates the gradient of the normal, a line perpendicular to the original line), then calculate cn=y-mn*x, where x and y are your initial point.

You then have two lines so you have to solve the simultaneous equation y=mn*x+cn and y=m*x+c for both x and y. That's your answer!

-
Sorry was in a rush, ask if there's any clarification you want. – James Jul 4 '14 at 13:01
This is incorrect. You cannot make assumptions based on which segment endpoints are closest. – jku Jul 4 '14 at 13:02
Please clarify your point. BTW, this goes through some of the theory. math.ucsd.edu/~wgarner/math4c/derivations/distance/… – James Jul 4 '14 at 13:07
Your link talks about distance from point to line, that part is fine. The problem is that you said you can select the correct line segment based on the distances from the segment endpoints to the reference point. This is not true for a lot of polylines: imagine a trapezoid with one very short segment and one very long segment on the opposite side. The segments are very close to each other. It's trivial to find a reference location where closest segment end points are on the short segment, but closest point is on long segment. – jku Jul 4 '14 at 13:20
OK, thinking about it, this is a quick and dirty solution. The only way I can think of doing it rigorously is to work out the distance between all the segments and the point, select the shortest and then working out the point on that segment it corresponds to. You'll then have to check that the point is actually between the two point, and not on an extension of the lines between points that isn't part of the segment. I think the choice depends on the complexity of your shapes. – James Jul 4 '14 at 13:23

The basic algorithm is to check every segment of the polygon and find the closest point for it. This will either be the perpedicular point (if it is on the segment) or one of the endpoints.

After doing this for all segments, pick the point with the smallest total difference.

So in your example it would be the segments:

• AB, outside, pick B
• BC, inside, try that point
• CD, utside, try C
• DE, outside, try D
• EA, outside, try A

When you compare the differences, you will see that the perpendicular point from segment BC is the closest match. You can also do this comparison in the same run.

-

A very simple solution: solve an equasion for each pair of poly vertices.

An algorithm for one segment of the polygon (gray in the picture) with points a and b:

• vector A is just point a coordinates
• vector S(egment) = b - a
• vector N is normal to S (-ys, xs)
• vector P is coordinates of point

You want to check the length of normal from point to Segment and make sure the target point is inside Segment.

Here's the equasion you want to solve:

In the solution, i must be between 0 and 1. If it is, then the distance is |iN| and the point is P + iN, otherwise it's the closest between vertices (a & b). Then you can find the closest point among those for each edge.

Here's a Javascript code that searches for closest distance, but it should be easy to modify for closest point:

function vlen(vector) {
return Math.sqrt(vector[0]*vector[0] + vector[1] * vector[1]);
}

function vsub(v1, v2) {
return [v1[0] - v2[0], v1[1] - v2[1]];
}

function vscale(vector, factor) {
return [vector[0] * factor, vector[1] * factor];
}

function vnorm(v) {
return [-v[1], v[0]];
}

function distance_to_poly(point, poly) {
var dists = \$.map(poly, function(p1, i) {
var prev = (i == 0 ? poly.length : i) - 1,
p2 = poly[prev],
line = vsub(p2, p1);

if (vlen(line) == 0)
return vlen(vsub(point, p1));

var norm = vnorm(line),
x1 = point[0],
x2 = norm[0],
x3 = p1[0],
x4 = line[0],
y1 = point[1],
y2 = norm[1],
y3 = p1[1],
y4 = line[1],

j = (x3 - x1 - x2 * y3 / y2 + x2 * y1 / y2) / (x2 * y4 / y2 - x4),
i;

if (j < 0 || j > 1)
return Math.min(
vlen(vsub(point, p1)),
vlen(vsub(point, p2)));

i = (y3 + j * y4 - y1) / y2;

return vlen(vscale(norm, i));
});

return Math.min.apply(null, dists);
}
-