如何在边缘上找到与另一点最接近的点 [英] How to find the point on an edge which is the closest point to another point

问题描述

我正在寻找有效找到边缘上与其他点最接近的点的方法.

I'm searching the way to efficiently find the point on an edge which is the closest point to some other point.

比方说，我知道两个点，它们是边缘的顶点.我可以计算出与这些点交叉的线的方程.

Let's say I know two points which are vertices of the edge. I can calculate the equation of the line that crosses those points.

计算边缘上与平面中其他点最接近的点的最佳方法是什么.

What is the best way to calculate the point on the edge which is the closest point to some other point in the plane.

我会发布图片，但是我的信誉点不够.

I would post an image but I don't have enough reputation points.

推荐答案

您需要考虑三个区域. 垂直"方法适用于中间区域:

You have three zones to consider. The "perpendicular" approach is for the zone in the middle:

对于其他两个区域，该距离是到最近的线段终点的距离.

For the other two zones the distance is the distance to the nearest segment endpoint.

该细分的等式为:

y[x] = m x + b

哪里

  m -> -((Ay - By)/(-Ax + By)), 
  b -> -((-Ax By + Ay By)/(Ax - By))  

垂直线的倾斜度为-1/m

And the perpendiculars have slope -1/m

通过A的垂直通过方程为:

The equations for the perpendicular passing thru A is:

  y[x] = (-Ax + By)/(Ay - By) x + (Ax^2 + Ay^2 - Ax By - Ay By)/(Ay - By)

通过B的垂直方向通过相同的方式交换上式中的A和B.

And the perpendicular passing thru B is the same exchanging the A's and B's in the equation above.

因此您可以知道您的点在哪个区域中，在上述方程式中引入其x坐标，然后将点的y坐标与y [x]的结果进行比较

So you can know in which region lies your point introducing its x coordinate in the above equations and then comparing the y coordinate of the point with the result of y[x]

修改

如何找到您的观点所在的地区?

How to find in which region lies your point?

让我们假设斧头≤ Bx(否则，只需更改以下公式中的点标签即可)

Let's suppose Ax ≤ Bx (if it's the other way, just change the point labels in the following formulae)

我们将致电给您{x0，y0}

We will call your point {x0,y0}

1)计算

 f[x0] =  (-Ax + By)/(Ay - By) x0 + (Ax^2 + Ay^2 - Ax By - Ay By)/(Ay - By)

并与y0进行比较.

如果y0> f [x0]，则您的点位于上图中的绿色字段中，最近的点是A.

If y0 > f[x0], then your point lies in the green field in the figure above and the nearest point is A.

2)其他，计算

g[x0] =  (-Bx + Ay)/(By - Ay) x0 + (Bx^2 + By^2 - Bx Ay - By Ay)/(By - Ay)  

并与y0进行比较.

如果y0< g [x0]，则您的点位于上图中的黄色字段中，最近的点是B.

If y0 < g[x0], then your point lies in the yellow field in the figure above and the nearest point is B.

3)否则，您位于垂直的浅蓝色区域"中，其他任何答案都告诉您如何计算最近的点和距离(我不会窃:))

3) Else, you are in the "perpendicular light blue zone", and any of the other answer tell you how to calculate the nearest point and distance (I am not going to plagiarize :))

HTH！

这篇关于如何在边缘上找到与另一点最接近的点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！