计算点到线段以及线段到线段的平均距离

Question

我正在寻找一种算法来计算 3D 中点和线段之间的平均距离。因此，给定表示线段 AB 的两个点 A(x1, y1, z1) 和 B(x2, y2, z2) 以及第三个点 C(x3, y3, z3)，AB 上每个点之间的平均距离是多少到C点？

我也对两条线段之间的平均距离感兴趣。那么给定线段AB和CD，AB上每个点到CD上最近点的平均距离是多少？

我尝试过的网络搜索没有任何运气，因此任何建议将不胜感激。

谢谢。

Answer 1

首先，两点之间的距离是坐标两两差的平方和的平方根。
（例如，从 (0,0,0) 到 (1,1,1) 的距离为 sqrt(3)，但这适用于任意维数的任意点。）
该距离称为 l2-norm（小写 L）或欧几里得范数。
写出 A 点和 B 点之间的距离的范数（A，B）。

关于平均距离的有趣问题......
（请注意，找到从点到线或线段之间的最小距离是一个更常见的问题。这里有一个答案，为该问题提供了很好的指导，但似乎它已在）

要求从点 C 到线段 AB 的平均距离，请考虑到 A 和 B 之间任意点的距离，即 (1-k)A+kB，其中 k 的范围为 0 到 1。
这就是范数(C, (1-k)A+kB)。
所以平均距离是norm(C, (1-k)A+kB)从k = 0到1的积分。

Mathematica 可以对任何特定的 A、B 和 C 进行积分。

这是 Mathematica 的实现：

avgd[A_,B_,C_] :=  Integrate[Sqrt@Dot[(1-k)*A+k*B-C, (1-k)*A+k*B-C], {k, 0, 1}]

被积函数也可以写成 Norm[(1-k)*A+k*BC]。无论哪种方式，Mathematica 都可以针对特定点做到这一点，但无法象征性地整合它，尽管显然 David 以某种方式做到了这一点。
这是来自评论的 David 的例子：

> avgd[{0, 0, 0}, {4, 0, 0}, {4, 3, 0}] // N

3.73594

对于两条线段之间的平均距离问题，理论上我认为这应该可行：

avgd[A_,B_,C_,D_] := Integrate[Norm[(1-k)A+k*B - (1-j)C - j*D], {k,0,1}, {j,0,1}]

但是即使对于特定的点，Mathematica 似乎也会对此感到窒息，更不用说象征性的了。

Answer 2

如果您的意思是我认为您所说的“平均”（和“距离”，即 dreeves 提到的 L2 范数），那么我认为以下过程应该适用于查找点之间的平均距离和一个线段。您需要一个函数dot(A,B)，它获取两个向量的点积。

// given vectors (points) A, B, C
K1 = dot(A-C,A-C)
K2 = 2*dot(B-A,A-C)
K3 = dot(B-A,B-A)
L1 = sqrt(K3*(K1+K2+K3))
L2 = sqrt(K3*K1)
N = 4*K3*L1 + 2*K2*(L1-L2) + (K2*K2-4*K1*K3)*log((K2+2*L2)/(2*K3+K2+2*L1))
D = N / (8*K3^1.5)

假设我已正确转录所有内容，则 D 将是平均距离。

这基本上只是用于评估我在 Mathematica 中进行的积分结果的伪代码。可能有一些简洁的计算捷径，但如果有的话，我不知道。 （除非有一个，否则我会质疑你真正需要多少来进行此计算）

如果你想找到从线段 CD 上最近的点到 AB 上所有点的平均距离，在大多数情况下是最近的点将是 C 或 D，因此您可以检查这两个值以查看哪个更接近（可能使用其他答案中引用的一些最小距离计算）。唯一的例外是当 CD 和 AB 平行时，您可以从一个到另一个垂直，在这种情况下，您必须更精确地定义您的要求。

如果你想求 CD 上所有点和 AB 上所有点之间的平均距离……可以用二重积分来完成，尽管我不禁想到结果公式会有多么复杂。

Answer 3

好吧，如果分析失败，请使用计算机并进行大量愚蠢的计算，直到您对数字有了感觉......

我也有一本 Mathematica。为了简单起见，由于三角形必须位于一个平面上，因此我在 2D 空间中进行了以下工作。为了让事情变得更加简单，我在 {0,0} 处指定了一个点，并指定了一条从 {1,0} 到 {0,1}< 的线段/代码>。如果有意义的话，从点到线的平均距离必须是从{0.0}到线段上任意位置可以绘制的所有线的平均长度。当然，这样的行有很多，所以我们从 10 行开始。在 Mathematica 中，这可能被计算为

Mean[Table[EuclideanDistance[{0, 0}, {1 - k, 0 + k}], {k, 0, 1, 10.0^-1}]]]

0.830255。下一步很明显，使我测量的线数更大。事实上，让我们制作一个 10.0 指数变小的平均值表（它们是负数！）。在 Mathematica 中：

Table[Mean[Table[EuclideanDistance[{0, 0}, {1 - k, 0 + k}], {k, 0, 1, 
10.0^-i}]], {i, 0, 6}]

产生：

{1, 0.830255, 0.813494, 0.811801, 0.811631, 0.811615, 0.811613}

按照这种方法，我重新设计了 @Dave 的示例（忘记第三维）：

Table[Mean[Table[EuclideanDistance[{0, 0}, {4, 0 + 3 k}], {k, 0, 1, 
10.0^-i}]], {i, 0, 6}]

它给出：

{9/2, 4.36354, 4.34991, 4.34854, 4.34841, 4.34839, 4.34839}

这与 @dreeves 所说的 @Dave 算法计算的内容不一致。

编辑：好的，所以我在这方面又浪费了一些时间。对于我首先使用的简单示例，即 {0,0} 处的点和从 {0,1} 延伸到 的线段>{1,0} 我在 Mathematica 中定义了一个函数（一如既往），如下所示：

fun2[k_] := EuclideanDistance[{0, 0}, {0 + k, 1 - k}]

现在，这是可积的。 Mathematica 给出：

   In[13]:= Integrate[fun2[k], {k, 0, 1}]

   Out[13]= 1/4 (2 + Sqrt[2] ArcSinh[1])

或者，如果您更喜欢数字，则：

In[14]:= NIntegrate[fun2[k], {k, 0, 1}]
Out[14]= 0.811613

这就是我之前采用的纯数值方法给出的结果。

我现在要回去工作，并让你们将其推广到由点和线段的端点定义的任意三角形。