计算点到线段的平均距离和线段到线段的平均距离

Question

计算点到线段的平均距离和线段到线段的平均距离

mathgeometrywolfram-mathematica

6

我正在寻找一种算法，用于计算三维空间中点与线段之间的平均距离。给定两个点A（x1，y1，z1）和B（x2，y2，z2），表示线段AB，以及第三个点C（x3，y3，z3），每个点在AB上到点C的平均距离是多少？

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

我尝试了很多网络搜索，但都没有成功，所以非常感谢您的建议。

谢谢。

- Fred

1

你为什么要计算这个？这似乎是一个不太常见的计算，而且我担心它并不简单。你确定这就是你要找的吗？ - brainjam

3个回答

1

如果你所说的“平均值”和“距离”是我想象中的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上所有点之间的平均距离...可以用双重积分来完成，尽管我不敢想象得出的公式会有多么复杂。

- David Z

我印象深刻，David！你是如何让Mathematica对具有符号A、B、C的积分进行求解的？不幸的是，我们中的某个人犯了一个错误，因为当我将你的算法与Integrate[Norm[(1-k)A+kB-C], {k,0,1}]（针对特定的A、B、C）进行比较时，它们并不匹配。你有什么想法吗？ - dreeves

PS：我现在确定 David 的算法有误，但我还没想出如何重现他的操作以确定错误所在！ - dreeves

这是我的做法：线段可以被参数化为A+k(B-A)，因此我手动计算了(A+k(B-A)-C)^2，得到了(A-C)^2+2k(B-A).(A-C)+k^2(B-A)^2。我设定了K1=(A-C)^2，K2=2(B-A).(A-C)和K3=(B-A)^2，并让Mathematica计算Integrate[Sqrt[K1 + K2 k + K3 k^2],{k,0,1}]。 - David Z

啊，我想我明白发生了什么事情了：当我输入公式时，我不小心交换了K1和K3。现在应该已经修复了。 - David Z

谢谢David！我对你的公式进行了一系列随机测试以验证其正确性。至少现在我不会因为自己没有想出来而感到难过了。如果可能的话，我想尝试找到一个更简单的公式来得到一个好的近似值。 - Fred

这可能不是一个坏主意，尽管你可以使用的近似类型取决于你特定的应用。例如，从你的点到线段的最小距离与线段的长度相比如何？如果其中一个远小于另一个，我可以想出一些快速公式来解决问题。如果您在此问题中编辑更多有关程序的详细信息，我们可以帮助您找到适当的近似值。 - David Z

1

如果分析失败了，就去用计算机做大量的计算，直到你对数字有了感觉...

我也有一份Mathematica的副本。为了保持简单，由于三角形必须位于一个平面上，我在二维空间中进行了以下工作。为了保持额外的简单性，我指定了一个点在{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

这就是我之前采用的纯数字方法所得到的结果。

现在我要回去工作了，把这个推广到由一个点和线段的端点定义的任意三角形留给大家。

- High Performance Mark

对于最后一个例子，我认为我们在计算不同的距离。在我的评论中，我说的是边长为4和其相对顶点之间的平均距离，但是看起来你计算的是边长为3和其相对顶点之间的平均距离。这可能解释了为什么数字不匹配。 - David Z

@David -- 是的，当我重新调整我的计算时，我也得到了3.73594。 - High Performance Mark

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dreeves · Accepted Answer

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

接下来是有趣的平均距离问题... （注意，找到点到线或线段之间的最小距离是一个更常见的问题。这里有一个答案，提供了很好的指导，但似乎已经在此期间被删除。）

要找到点C到线段AB的平均距离，请考虑到A和B之间的任意点的距离，即(1-k)A+kB，其中k从0到1。那就是norm(C，(1-k)A+kB)。因此，平均距离是从k = 0到1的积分norm(C，(1-k)A+kB)。

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*B-C]的形式。无论哪种方式，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似乎在特定点上甚至无法处理，更不用说符号化处理了。