Best intersection of a collection of line segments?

Question

I have a number of 2D segments that should intersect at one point, but not due to noise earlier in the calculations, which cannot be reduced.

Is there an algorithm for calculating the best approximation to the intersection of all segments. Something like a point with a minimum average distance to all line segments that do not necessarily lie on any of the segments?

Answer 1

If we have the freedom to choose a metric, the sum of the squared distances can give a simple algorithm.

We can represent the square of the distance to the line #i as a function of the point coordinates, we obtain (A[i]x,x)+(b[i],x)+c[i] , A[i] is the 3x3 matrix, b[i] is a vector, c[i] is a number, (a, b) is scalar multiplication.

Their sum will be (A[sum]x,x)+(b[sum],x)+c[sum] .

The minimum of such a function is x=-inverse(A[sum])b[sum]/2 .

Answer 2

The first comment from Amit is your answer. I will explain why.

Let p_i be your intersection points and c = 1/n sum(p_i) . We show that c minimizes the average distance d(a) between p_i and an arbitrary point a :

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

What is averaged in d(a) is, using the internal designation of the product,

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

The average value of <a,p_i> is simply <a,c> using the bilinear properties of the point product. In this way,

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

And also

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

Subtracting Two

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

So, adding d(c) to both sides, the average distance to an arbitrary point a is

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

since all terms are positive, it is minimized when |ac|^2 is equal to zero, in other words, when a = c .