algorithm - 线段集合的最佳交点？

Question

我有许多 2D 线段，它们都应该在一个点相交，但不会因为早期计算中的噪声而无法减少。

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

Answer 1

Amit 的第一条评论就是您的答案。我会解释为什么。

让p_i成为您的交点和c = 1/n sum(p_i)。让我们证明最小化和任意点之间c的平均距离：d(a)p_ia

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>`

的平均值<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.

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。