如何找到一条边上距离另一点最近的点

Question

我正在寻找一种有效的方法来找到一条边上距离某个点最近的点。

假设我知道两个点，它们是边的顶点。 我可以计算通过这些点的直线方程。

什么是计算平面上距离某个点最近的边上点的最佳方法。

我想发布一张图片，但我没有足够的声望点数。

- image

---

"edge"是一条直线段吗？ - Dr. belisarius

是的，它是直线段。 - image

Answer 1

假设直线由两个点（x1，y1），（x2，y2）定义，且“其他点”为（a，b）。你要寻找的点是（x，y）。

您可以轻松地找到黑线的方程式。要找到蓝线方程，请使用m1 * m2 = -1这个条件（其中m1和m2是两条线的斜率）。

显然，您要寻找的点是两条线之间的交点。

我所说的有两个例外：

1. 如果x1 = x2，则（x，y）=（x1，b）。
2. 如果y1 = y2，则（x，y）=（a，y1）。

以下Python函数查找该点（如果您不了解Python，请将其视为伪代码）：

def get_closest_point( x1,y1, x2,y2, a,b ):
    if x1==x2: return (x1,b)
    if y1==y2: return (a,y1)
    m1 = (y2-y1)/(x2-x1)
    m2 = -1/m1
    x = (m1*x1-m2*a+b-y1) / (m1-m2)
    y = m2*(x-a)+b
    return (x,y)

- snakile

Answer 2

您需要考虑三个区域。"垂直"方法适用于中间的区域：

对于其他两个区域，距离是到最近线段端点的距离。

线段的方程为：

y[x] = m x + b

位置

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

垂线的斜率为-1/m。

通过A点的垂线方程为：

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

垂直于B的直线与上述方程交换A和B后仍然相同。

因此，您可以通过在上述方程中引入其x坐标并将点的y坐标与y[x]的结果进行比较，来确定该点位于哪个区域。

编辑

如何确定您的点位于哪个区域？

假设Ax ≤ Bx（如果反过来，只需在以下公式中更改点标签）

我们将称您的点为 {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。

2）否则，计算

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

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

3）否则，您位于“垂直天蓝色区域”，任何其他答案都可以告诉您如何计算最近的点和距离（我不会剽窃 :))

希望对您有所帮助！

- Dr. belisarius

---

感谢您提供的优秀示例。但是，我该如何确定我的点位于哪个区域？如果我将某个点的x坐标引入第二个方程，并且该方程的结果等于该点的y坐标，则我将知道该点直接位于线段的边界上，但是如果方程的结果与该点的y坐标不相等呢？我该如何知道我的点位于哪个线段中？ - image

@image 请参考以下答案：https://dev59.com/fXRA5IYBdhLWcg3wuAcp#4165840 - Dr. belisarius

Answer 3

为了节省打字时间，我们继续使用2D案例。已经有一段时间了，请原谅我在代数方面可能犯的初级错误。

连接两点(x1, y1)和(x2, y2)的线段可以表示为一个函数。

y = mx + b

你需要自己找出m和b的值，但这是基础知识。

你想要做的是将从你的点（p1，p2）到这条直线上的某一点的距离最小化，即：

(p1-x)^2 + (p2-y)^2     (equation I)

遵循这个方程式

y = mx + b              (equation II)

将方程II代入方程I并解出x。你会得到两个解，选择在方程I中给出较小值的那个解。

- James McLeod

---

难道不应该是sqrt((p1-x)^2 + (p2-y)^2)吗？ - image

除非你需要实际距离，否则没有必要进行平方根运算。如果你只想知道两个距离哪一个更大，那么可以比较它们的平方值。也就是说，如果N^2 > M^2，则N > M（假设M和N为正值）。只有在真正关心M和N的值时才需要进行平方根运算。 - Jim Mischel

Answer 4

我可以用几何术语描述您想要做的事情，但手头没有算法。这样有帮助吗？

无论如何，您想要绘制一条包含杂点并垂直于边缘的线。如果有帮助的话，我认为斜率是垂直线之间的负倒数关系。

然后您需要找到两条线的交点。

- David Winant

---

我认为这会有所帮助。让我们试一试。 - image