1

I want to calculate a point/vector with the least Euclidian distance to a given set of N lines (e.g. given by a point and a vector for the direction) in a D dimensional space (for example by least squares)

Since I use Python for my project, I was wondering, whether there are already appropriate implementations for this general problem in some standard library like numpy, but I have not found any.

There are already related questions like:

Finding the centre of multiple lines using least squares approach in Python

nearest intersection point to many lines in python

However, these questions did not consider a dimension larger than 3 and in my case, I would like to adapt the problem to dimensions like 100.

I also found this resource for Matlab, which does not seem to be used that much, but it deals with the same problem: https://de.mathworks.com/matlabcentral/fileexchange/59805-line-line-intersection-n-lines-d-space?s_tid=FX_rc1_behav

Chrixtar
  • 13
  • 2

1 Answers1

0

If each line with index i is given by a unit vector column

vi = {
       v1i,
       v2i,
       v3i,
       ...
       vDi
      }

pointing along the line i, and a point given by a vector column

pi = {
       p1i,
       p2i,
       p3i,
       ...
       pDi
      }

, where i = 1...N, then the point x you seek, given as a column, is given by the equation

x = inverse( sum(i=1:N, I - vi * transposed(vi)) ) * sum(i=1:N, (I - vi * transposed(vi)) * pi);

Here I is the D-dimensional identity square matrix.

If each line is given by two points pi and qi then you can calculate

vi = (qi - pi) / sqrt(transposed(qi - pi) * (qi - pi))

Futurologist
  • 1,874
  • 2
  • 7
  • 9