Find indices of polygon vertices nearest to a point

Question

Heading

I need to find the indices of the polygon nearest to a point

So in this case the ouput would be 4 and 0. Such that if the red point is added I know to where to place the vertex in the array. Does anyone know where to start?

(Sorry if the title is misleading, I wasnt sure how to phrase it properly)

In this case the ouput would be 0 and 1, rather than the closest 4.

Answer 1

Point P lies on the segment AB, if two simple conditions are met together:
AP x PB = 0 //cross product, vectors are collinear or anticollinear, P lies on AB line
AP . PB > 0 //scalar product, exclude anticollinear case to ensure that P is inside the segment

So you can check all sequential vertice pairs (pseudocode):

if (P.X-V[i].X)*(V[i+1].Y-P.Y)-(P.Y-V[i].Y)*(V[i+1].X-P.X)=0 then
//with some tolerance if point coordinates are float
   if (P.X-V[i].X)*(V[i+1].X-P.X)+(P.Y-V[i].Y)*(V[i+1].Y-P.Y)>0
       then P belongs to (i,i+1) segment

This is fast direct (brute-force) method.
Special data structures exist in computer geometry to quickly select candidate segments - for example, r-tree. But these complicated methods will gain for long (many-point) polylines and for case where the same polygon is used many times (so pre-treatment is negligible)

Answer 2

I'll assume that the new point is to be added to an edge. So you are given the coordinates of a point a = (x, y) and you want to find the indices of the edge on which it lies. Let's call the vertices of that edge b, c. Observe that the area of the triangle abc is zero.

So iterate over all edges and choose the one that minimizes area of triangle abc where a is your point and bc is current edge.

a = input point
min_area = +infinity
closest_edge = none
n = number of vertices in polygon

for(int i = 1; i <= n; i++)
{   b = poly[ i - 1 ];
    c = poly[ i % n ];
    if(area(a, b, c) < min_area)
    {   min_area = area(a, b, c);
        closest_edge = bc
    }
}

You can calculate area using:

/* Computes area x 2 */
int area(a, b, c)
{   int ans = 0;
    ans = (a.x*b.y + b.x*x.y + c.x*a.y) - (a.y*b.x + b.y*c.x + c.y*a.x);
    return ABS(ans);
}

Answer 3

I think you would be better off trying to compare the distance from the actual point to a comparable point on the line. The closest comparable point would be the one that forms a perpendicular line like this. a is your point in question and b is the comparable point on the line line between the two vertices that you will check distance to.

However there's another method which I think might be more optimal for this case (as it seems most of your test points lie pretty close to the desired line already). Instead of find the perpendicular line point we can simply check the point on the line that has the same X value like this. b in this case is a lot easier to calculate:

X = a.X - 0.X;
Slope = (1.Y - 0.Y) / (1.X - 0.X);
b.X = 0.X + X;
b.Y = 0.Y + (X * Slope);

And the distance is simply the difference in Y values between a and b:

distance = abs(a.Y - b.Y);

One thing to keep in mind is that this method will become more inaccurate as the slope increases as well as become infinite when the slope is undefined. I would suggest flipping it when the slope > 1 and checking for a b that lies at the same y rather than x. That would look like this:

Y = a.Y - 0.Y;
Inverse_Slope = (1.X - 0.X) / (1.Y - 0.Y);
b.Y = 0.Y + Y;
b.X = 0.Y + (Y * Inverse_Slope);
distance = abs(a.X - b.X);

Note: You should also check whether b.X is between 0.X and 1.X and b.Y is between 0.Y and 1.Y in the second case. That way we are not checking against points that dont lie on the line segment.

I admit I don't know the perfect terminology when it comes to this kind of thing so it might be a little confusing, but hope this helps!

Answer 4

Rather than checking if the point is close to an edge with a prescribed tolerance, as MBo suggested, you can fin the edge with the shortest distance to the point. The distance must be computed with respect to the line segment, not the whole line.

How do you compute this distance ? Let P be the point and Q, R two edge endpoints.

Let t be in range [0,1], you need to minimize

D²(P, QR) = D²(P, Q + t QR) = (PQ + t QR)² = PQ² + 2 t PQ.QR + t² QR².

The minimum is achieved when the derivative cancels, i.e. t = - PQ.QR / QR². If this quantity exceeds the range [0,1], just clamp it to 0 or 1.

To summarize,

if t <= 0, D² = PQ²
if t >= 1, D² = PR²
otherwise, D² = PQ² - t² QR²

Answer 5

Loop through all the vertices, calculate the distance of that vertex to the point, find the minimum.

double min_dist = Double.MAX_VALUE;
int min_index=-1;
for(int i=0;i<num_vertices;++i) {
   double d = dist(vertices[i],point);
   if(d<min_dist) {
       min_dist = d;
       min_index = i;
   }
}