logo标签列表

在三维空间中计算两条直线（线段）之间的最短距离

algorithmgeometry
24

我有两条线段: X1,Y1,Z1 - X2,Y2,Z2 和 X3,Y3,Z3 - X4,Y4,Z4

我试图找到这两个线段之间的最短距离。

我已经寻找解决方案数小时，但是所有的方法似乎都是针对直线而不是线段。

任何想法或公式来源吗？

请查看论文线段之间距离的稳健计算。 - Fedor
7个回答
28

我将以matlab为例进行回答，但其他编程环境也可以使用。我想补充的是，这个解决方案适用于解决任意维度（>= 3）的问题。

假设我们在空间中有两条线段PQ和RS。以下是一些随机点集。

> P = randn(1,3)
P =
     -0.43256      -1.6656      0.12533

> Q = randn(1,3)
Q =
      0.28768      -1.1465       1.1909

> R = randn(1,3)
R =
       1.1892    -0.037633      0.32729

> S = randn(1,3)
S =
      0.17464     -0.18671      0.72579

无限直线PQ(t)可以轻松定义为：
PQ(u) = P + u*(Q-P)

同样地，我们有
RS(v) = R + v*(S-R)

对于每一条线，当参数为0或1时，我们会得到返回线上一个原始端点的结果。因此，我们知道PQ(0) == P，PQ(1) == Q，RS(0) == R和RS(1) == S。

这种通过参数定义线的方式在许多情况下非常有用。

接下来，想象我们沿着线PQ向下看。我们能找到线段RS到无限线PQ的最短距离点吗？这可以通过将其投影到线PQ的零空间中来最轻松地完成。

> N = null(P-Q)
N =
     -0.37428     -0.76828
       0.9078     -0.18927
     -0.18927      0.61149

因此，null(P-Q)是一对基向量，它们构成了与线段PQ垂直的二维子空间。
> r = (R-P)*N
r =
      0.83265      -1.4306

> s = (S-P)*N
s =
       1.0016     -0.37923

我们所做的实质上是将向量RS投影到与线PQ正交的二维子空间(平面)中。通过减去在线PQ上的一点P以获得r和s，我们确保这条无限直线在此投影平面中通过原点。

因此，我们实际上将其简化为在投影平面中从线rs(v)到原点(0,0)的最小距离。请记住，线rs(v)由参数v定义为：

rs(v) = r + v*(s-r)

线段rs(v)的法向量将会给我们所需的信息。由于我们将其简化为了2维，因为原始空间是3维，所以我们可以轻松地完成它。否则，我将再次使用null。这个小技巧在2维中起作用：

> n = (s - r)*[0 -1;1 0];
> n = n/norm(n);

n现在是一个长度为1的向量。从无限直线rs(v)到原点的距离很简单。

> d = dot(n,r)
d =
       1.0491

注意到我也可以使用s来得到相同的距离。实际距离是abs(d)，但事实证明，这里的d是正数。

> d = dot(n,s)
d =
       1.0491

我们可以从这个中推导出v吗？是的。回想一下，原点距离连接点r和s的线段有d个单位长度。因此，我们可以写出dn = r + v(s-r)，其中v是标量的某个值。将该方程两边与向量(s-r)做点积，解出v即可。

> v = dot(s-r,d*n-r)/dot(s-r,s-r)
v =
       1.2024

这告诉我们线段rs距离原点最近的接近点在线段的端点之外。因此，rs对于原点的最近点实际上是点rs(1)=s。

从投影中可以得知，线段RS到无限直线PQ的最近点是点S。

分析还有一个步骤需要进行：线段PQ上最近的点是哪个？该点是否在线段内部，还是它也落在了端点之外？

我们将点S投影到直线PQ上。（这里的u表达式很容易从之前的逻辑推导出来。注意，我使用\来完成这项工作。）

> u = (Q-P)'\((S - (S*N)*N') - P)'
u =
      0.95903

假设 u 的取值在 [0,1] 区间内，我们已经解决了这个问题。线段 PQ 上的点为：

> P + u*(Q-P)
ans =
      0.25817      -1.1677       1.1473

此外，两条线段上最近点之间的距离为：

> norm(P + u*(Q-P) - S)
ans =
        1.071

当然，所有这些可以压缩成几行代码。但是将其扩展开来以获得其工作原理的理解会有所帮助。

18

一种基本的方法与计算两条线之间的最短距离相同，只有一个例外。

如果您查看大多数查找两条线之间最短距离的算法，您会发现它找到每条线上离彼此最近的点，然后计算它们之间的距离。

将这个技巧扩展到线段（或射线）上的方法是，查看该点是否超出了线段的一个端点，如果是，则使用该端点而不是无限直线上实际最接近的点。

具体示例请参见：

http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm

更具体地说：

http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm#dist3D_Segment_to_Segment()

3
SoftSurfer的代码相当不错。它在处理几乎平行的线时有些问题。我最终编写了一个检查“几乎平行”线的代码。一旦我这样做了，它就运行良好。我不确定为什么内置在SoftSurfer中的“几乎平行”线检查没有奏效。只是想让下一个用户知道... - Tim Perry
2
我发现和@TimPerry一样的问题。我使用了这个并行检查：bool parallel = dot(u, v) / (u.length() * v.length()) > 1 - SMALL_NUM;请根据您的向量库进行修改。 - Michael Taylor
@ReedCopsey 我使用了dist3D_Segment_to_Segment()函数，并尝试了如下线段： LineSegment lineSegmentA; lineSegmentA.startPoint = PointType(0.,0.,0.); lineSegmentA.endPoint = PointType(1.,0.,0.);LineSegment lineSegmentB; lineSegmentB.startPoint = PointType(.5,0.2,0.); lineSegmentB.endPoint = PointType(.5,1.2,0.);最近的距离应该是从lineSegmentB的终点到lineSegmentA的中心点，其值应为“0.2”。然而，该函数返回距离为“0.538”。你有什么想法吗？ - David Doria
@DavidDoria 您几乎肯定将函数转录错误了。如果选择了 D < SMALL_NUM 路线，那就是您会得到的值。它不应该被选择，实际上也没有被选择。您需要确保正确地转录代码。 - David Heffernan
3
这些链接已经失效了。你能找到新的链接吗？是否有新的来源可以链接？ - robotsfoundme
这就是为什么你不要发布链接的原因... - David C. Rankin
2
我建议您将两条线段分别用一个参数进行参数化，每个参数的取值范围为0到1（包括0和1）。然后找出两条线函数之间的差异，并将其作为目标函数用于线性优化问题中，其中参数作为变量。
比如说，你有一条从（0,0,0）到（1,0,0）的线段，另一条从（0,1,0）到（0,0,0）的线段（是的，我使用了简单的例子）。这些线段可以被参数化为（1*t，0*t，0*t），其中t在[0,1]范围内，以及（0*s，1*s，0*s），其中s在[0,1]范围内，与t无关。
然后，您需要最小化||（1*t，1*s，0）||，其中t，s在[0,1]范围内。这是一个相当简单的问题要解决。
给定从p1到p2和从q1到q2的线段，您需要计算所有以下距离并取最小值：（line1，line2），（p1，line2），（p1，q1），（p1，q2），（p2，line2），（p2，q1），（p2，q2），（line1，q1），（line1，q2）。 （或者也许您可以在数学上表明一些可以被消除。） - j_random_hacker
1
这个问题是由弗拉基米尔·J·卢梅尔斯基在1985年的文章《关于线段距离快速计算的研究》中提出的主题。该算法不仅能够找到最小欧几里德距离（MinD），而且还能找到两条线段上与该距离相隔的点。
一般算法如下：
  1. 计算全局MinD（全局意味着包含线段的两条无限直线之间的距离），以及最小距离线的两个点（基点）的坐标，参见skew lines；如果两个基点都在线段内，则实际MinD等于全局MinD；否则，继续。
  2. 计算两个线段端点之间的距离（总共四个距离）。
  3. 计算从一个线段的端点到另一个线段上垂线的基点坐标；计算那些基点位于相应线段内的垂线长度（最多四个基点和四个距离）。
  4. 在剩余的距离中，最小的就是所寻找的实际MinD。总的来说，这代表了六个点和九个距离的计算。

该文章随后描述并证明了如何根据算法初始步骤接收到的数据减少测试量，并处理退化情况（例如，线段的端点相等）。

可以在这里找到Eric Larsen的C语言实现，查看SegPoints()函数。

1

基于在两条无限直线之间找到距离，然后将无限直线限制在有限直线上来寻找两条有限直线之间的距离并不总是有效。例如，请尝试这些点。

Q=[5 2 0]
P=[2 2 0]
S=[3 3.25 0]
R=[0 3 0]

基于无限方法，该算法选择R和P进行距离计算（距离=2.2361），但在R和S的中间某处，有一个更接近P点的距离。显然，从R到S线上选择P和[2 3.166]的距离更短，为1.1666。即使通过精确计算并找到从P到RS线的正交线，这个答案也可以得到改进。

我已经尝试了不同的点和方法，这是我目前的发现。当您使用项目方法来查找两条有限线之间的距离时，必须在两侧执行投影。这意味着您必须先将RS投影到PQ，然后再反过来得到正确的答案。在这种方法中，计算出两个不同的距离，最低的那个就是您要寻找的距离。 - morteza
-1

首先，找到最接近的线段桥接它们的延长线。我们称之为LineSeg BR。

如果BR.endPt1落在LS1上，BR.endPt2落在LS2上，那么你就完成了...只需计算BR的长度。

如果桥梁BR与LS1相交但不与LS2相交，则使用这两个距离中较短的距离：smallerOf(dist(BR.endPt1, LS2.endPt1), dist(BR.endPt1, LS2.endPt2))

如果桥梁BR与LS2相交但不与LS1相交，则使用这两个距离中较短的距离：smallerOf(dist(BR.endPt2, LS1.endPt1), dist(BR.endPt2, LS1.endPt2))

如果没有满足以上条件，那么最接近的距离就是相对线段端点的最接近配对。

-1

将线段延伸为无限长的直线，找到两条直线之间的最短距离。然后找到每条直线上最短距离线段的端点。

如果每条直线上的点都在原始线段上，则您已经得到了答案。如果每条直线上的某个点不在原始线段上，则该点是原始线段的一个端点。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接