如何找到线段上的最近点到任意点？ [英] How to find the closest point on a line segment to an arbitrary point?

问题描述

这个函数应该带有一个点参数，该参数将用于找到位于线段对象上的最接近它的点。在示例断言代码中，函数 getClosestPoint（Point（））以 Point（10，0）返回点（5,5）作为最接近点点（10，0） l1 =行（Point（5,5），Point（20,35））终点为 A Point（5,5），B点（20,35）我不知道如何去解决这个问题。我目前的解决方案将返回（4,3），并且不在线段上，但在线上。

 从点导入点
导入数学
 class线：
 def __init __（self， aPoint = Point（），bPoint = Point（））：
 self.firstPoint = aPoint 
 self.secondPoint = bPoint 
 $ b $ get 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 
返回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 
  

解决方案

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

具体而言，您必须找到转换。
第二个，从新空间到原始空间很容易写（只需在纸上绘制，你会看到）：

  x =（x2  -  x1）* nx +（y2  -  y1）* ny + x1 
y =（y1  -  y2）* nx +（x2  -  x1）* ny + y1 
  

但是，您可以反转这些公式以找到（nx，ny）对应于一个点（x，y）。

当你这样做时，你应该得到这样的东西：

  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）
  

编辑：如果您实际上必须找到最近的点段而非行，因此很容易找到，因为如果投影落在段中，则 0 <= nx< = 1 在return语句之前，您可以强制 nx 停留在此区间中：

  nx = min（1，max（0，nx））
  

reedit ：
上面的语句相当于：

 如果nx <0：
 nx = 0 
如果nx> 1：
 nx = 1 
  

这样，投影（可以在段之外）的点被推回到在最近点处的段内（由 0 <= nx< = 1 定义）。 / p>

This function is supposed to take in a point parameter which will be used to find the closest point to it that lies on the line segment object. In the example assertion code the function getClosestPoint(Point()) takes Point(10, 0) as parameters and should return Point(5,5) as the closest point to Point(10, 0) that is on the line of l1 = Line(Point(5,5), Point(20,35)) With the endpoints being A Point(5,5), B Point(20,35) I'm not sure how to go about solving this problem. My current solution will return (4,3) and that is not on the line segment but is on the line.

 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

解决方案

The general answer is to project the point onto the line. One way to see it is to transform the point into the reference frame defined by your segment (p1 is the new origin (0, 0), p2 the new (1, 0)). Then, you get rid of the new y coordinate (that's where the actual projection occurs) and transform the new point (x, 0) back into the original frame.

Concretely, you'll have to find the transformations. The second one, from the new space into the original space is easy to write (just draw it on paper, you'll see):

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

But you can invert these equations to find (nx, ny) that correspond to a point (x, y).

When you do that, and assuming neither of us has made any mistakes nor typo, you should get something like:

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: If you actually have to find the closest point on the segment instead of the line, it is easy to find because if the projection falls within the segment, you have 0 <= nx <= 1 (it's a necessary and sufficient condition). Before the return statement, you can just force nx to stay in this interval:

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

reedit: The statement above is equivalent to:

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

This way, the projection of the point on the line (which can be outside the segment) gets pushed back inside the segment (defined by 0 <= nx <= 1) at the closest point.

这篇关于如何找到线段上的最近点到任意点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！