Shortest distance between a point and a line in 3

问题:

I am trying to find the minimum distance from a point (x0,y0,z0) to a line joined by (x1,y1,z1) and (x2,y2,z2) using numpy or anything in python. Unfortunately, all i can find on the net is related to 2d spaces and i am fairly new to python. Any help will be appreciated. Thanks in advance!

回答1:

StackOverflow doesn't support Latex, so I'm going to gloss over some of the math. One solution comes from the idea that if your line spans the points p and q, then every point on that line can be represented as t*(p-q)+q for some real-valued t. You then want to minimize the distance between your given point r and any point on that line, and distance is conveniently a function of the single variable t, so standard calculus tricks work fine. Consider the following example, which calculates the minimum distance between r and the line spanned by p and q. By hand, we know the answer should be 1.

import numpy as np

p = np.array([0, 0, 0])
q = np.array([0, 0, 1])
r = np.array([0, 1, 1])

def t(p, q, r):
    x = p-q
    return np.dot(r-q, x)/np.dot(x, x)

def d(p, q, r):
    return np.linalg.norm(t(p, q, r)*(p-q)+q-r)

print(d(p, q, r))
# Prints 1.0

This works fine in any number of dimensions, including 2, 3, and a billion. The only real constraint is that p and q have to be distinct points so that there is a unique line between them.

I broke the code down in the above example in order to show the two distinct steps arising from the way I thought about it mathematically (finding t and then computing the distance). That isn't necessarily the most efficient approach, and it certainly isn't if you want to know the minimum distance for a wide variety of points and the same line -- doubly so if the number of dimensions is small. For a more efficient approach, consider the following:

import numpy as np

p = np.array([0, 0, 0])  # p and q can have shape (n,) for any
q = np.array([0, 0, 1])  # n>0, and rs can have shape (m,n)
rs = np.array([          # for any m,n>0.
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 1],
    [0, 2, 1],
])

def d(p, q, rs):
    x = p-q
    return np.linalg.norm(
        np.outer(np.dot(rs-q, x)/np.dot(x, x), x)+q-rs,
        axis=1)

print(d(p, q, rs))
# Prints array([1.        , 1.        , 1.41421356, 2.        ])

There may well be some simplifications I'm missing or other things that could speed that up, but it should be a good start at least.

回答2:

This duplicates @Hans Musgrave solution, but imagine we know nothing of 'standard calculus tricks' that 'work fine' and also very bad at linear algebra.

All we know is:

1. how to calculate a distance between two points
2. a point on line can be represented as a function of two points and a paramater
3. we know find a function minimum

(lists are not friends with code blocks)

def distance(a, b):
    """Calculate a distance between two points."""
    return np.linalg.norm(a-b)

def line_to_point_distance(p, q, r):
    """Calculate a distance between point r and a line crossing p and q."""
    def foo(t: float):
        # x is point on line, depends on t 
        x = t * (p-q) + q
        # we return a distance, which also depends on t        
        return distance(x, r)
    # which t minimizes distance?
    t0 = sci.optimize.minimize(foo, 0.1).x[0]
    return foo(t0)

# in this example the distance is 5
p = np.array([0, 0, 0])
q = np.array([2, 0, 0])
r = np.array([1, 5, 0])

assert abs(line_to_point_distance(p, q, r) - 5) < 0.00001 

You should not use this method for real calculations, because it uses approximations wher eyou have a closed form solution, but maybe it helpful to reveal some logic begind the neighbouring answer.