CODEWITHSUNDEEP
algorithmmathgeometrycomputational-geometry
nickponline
nickponline

Reputation: 25914

Best intersection of a collection of line segments?

I have a number of 2D line segments that should all intersect at one point but don't because of noise earlier in the calculations that cannot be reduced.

Is there an algorithm to compute the best approximation to the intersection of all the line segments. Something like the point with the minimum average distance to all the line segments that doesn't necessarily lie on any of the segments?

Upvotes: 4

Views: 1492

Answers (2)

A. Webb
A. Webb

Reputation: 26436

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

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

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

What is being averaged in d(a) is, using inner product notation, 

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

The average of <a,p_i> is just <a,c>, using the bilinear properties of dot product. So,

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

And so likewise

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

Subtracting the two

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

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

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

which since all terms are positive is minimized when |a-c|^2 is zero, in other words, when a = c.

Upvotes: 3

maxim1000
maxim1000

Reputation: 6365

If we have freedom to select a metric, sum of squared distances may give a simple algorithm.

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

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

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

Upvotes: 0

Related Questions