如何找到线段上离任意点最近的点？

Question

这个函数应该接受一个点参数，该参数将用于找到位于线段对象上的最近点。在示例断言代码中，函数 getClosestPoint(Point()) 将 Point(10, 0) 作为参数，并且应该 return Point(5,5) 作为最接近 Point(10, 0) 的点，即 l1 = Line(Point(5,5), Point(20,35)) 端点为 A Point(5,5), B Point(20,35) 我不确定如何解决这个问题。我现在的解法是 return (4,3) 就是不在线段上但是在线上。

 from point import Point
 import math
 class Line:
    def __init__(self,aPoint=Point(), bPoint=Point()):
        self.firstPoint = aPoint
        self.secondPoint = bPoint

    def getClosestPoint(self,point=Point()):

        m1 = self.getSlope()
        m2 = -1 / float(m1)
        b1 = self.p1.y - m1 * self.p1.x
        b2 = point.y - m2 * point.x
        x = float(b2 - b1) / float(m1 - m2)
        y = m1 * x + b1
        return Point(x, y)

    if __name__ == "__main__":
         p1 = Point(5,5)
         p2 = Point(20,35)
         l1 = Line(p1,p2)
         assert l1.getClosestPoint(Point(10,0)) == Point(5,5)
         assert l2.getClosestPoint(Point(25/2,25/2)


 class Point: 
    def __init__(self,x=0,y=0):
       self.x = x
       self.y = y

Answer 1

参见 this nice description by Paul Bourke。

Answer 2

一般的答案是将点投影到直线上。查看它的一种方法是将点转换为您的段定义的参考框架（p1 是新原点 (0, 0)，p2 是新原点 (1, 0)）。然后，您摆脱新的 y 坐标（即实际投影发生的位置）并将新点 (x, 0) 转换回原始框架。

具体来说，您必须找到转换。第二个，从新的space变成原来的space好写（画在纸上，你就知道了）：

x = (x2 - x1) * nx + (y2 - y1) * ny + x1
y = (y1 - y2) * nx + (x2 - x1) * ny + y1

但是您可以反转这些等式以找到对应于点 (x, y).

的 (nx, ny)

当你这样做时，假设我们都没有犯任何错误或打字错误，你应该得到类似的东西：

dx = x2 - x1
dy = y2 - y1
d2 = dx*dx + dy*dy
nx = ((x3-x1)*dx + (y3-y1)*dy) / d2
return (dx*nx + x1, dy*nx + y1)

edit：如果你实际上必须找到 segment 上的最近点而不是直线，这很容易找到，因为如果投影落在线段内，你有0 <= nx <= 1（充分必要条件）。在return语句之前，你可以强制nx停留在这个区间：

nx = min(1, max(0, nx))

重新编辑：上面的语句等价于：

if nx<0:
    nx = 0
if nx>1:
    nx = 1

这样，直线上的点（可以在线段外）的投影被推回到线段内（由 0 <= nx <= 1 定义）的最近点。

如何找到线段上离任意点最近的点？

How to find the closest point on a line segment to an arbitrary point?

python

geometry