一组线段的最佳交点是什么？

Question

我有一些2D线段，它们应该在一个点相交，但由于早期计算中的噪声无法减少，它们并没有相交。

是否有一种算法可以计算所有线段相交的最佳近似值。类似于与所有线段的平均距离最小的点，不一定位于任何线段上的点？

- nickponline

---

所有交集的简单平均有什么问题吗？如果可以的话，它既简单又直接，你应该使用它。如果不行，请描述一下问题在哪里——这将帮助我们更好地理解你的问题。 - amit

如果交点必须位于其中一个线段上，那么靠近交点平均值的交点可能是一个不错的选择。 - Fred Foo

@amit 同意。证明交点的平均值最小化到交点的平均距离在我的下面答案中给出。 - A. Webb

@amit是正确的，但您不必计算所有成对交集。您可以将其公式化为最小二乘问题，其中您正在寻找一个点，该点最接近支持线段的所有线。这在线段数量上具有线性复杂度。 - killogre

Answer 1

Amit的第一个评论就是你的答案。我来解释一下为什么。

设 p_i 为交点，c = 1/n sum(p_i)。我们来证明 c 是平均距离 d(a) 最小的点集 p_i 和任意点 a 之间的距离：

d(a) = 1/n sum( |a-p_i|^2 )  

在 d(a) 中被求平均的是，使用内积符号表示为：

|a-p_i|^2 = <a-p_i, a-p_i> = |a|^2 + |p_i|^2 - 2<a,p_i>`

< p > <a,p_i> 的平均值就是使用点积的双线性性质得到的 <a,c>。因此，

d(a) = |a|^2 - 2<a,c> + 1/n sum( |p_i|^2 )

因此同样地

d(c) = |c|^2 - 2<c,c> + 1/n sum( |p_i|^2 ) = -|c|^2 + 1/n sum( |p_i|^2 )

两者相减

d(a) - d(c) = |a|^2 - 2<a,c> + |c|^2 = |a-c|^2

因此，将d(c)添加到两侧后，任意点a到平均距离为：

d(a) = d(c) + |a-c|^2

由于所有项都是正数，因此当|a-c|^2为零时最小化，换句话说，当a=c时。

- A. Webb

Answer 2

如果我们有自由选择度量标准，平方距离之和可能会给出一个简单的算法。

我们可以将到第i条线的距离的平方表示为点坐标的函数，我们将得到(A[i]x,x)+(b[i],x)+c[i]，其中A[i]是一个3x3矩阵，b[i]是一个向量，c[i]是一个数字，(a,b)是标量乘法。

它们的总和将是(A[sum]x,x)+(b[sum],x)+c[sum]。

这种函数的最小值是x=-inverse(A[sum])b[sum]/2。

- maxim1000