|
|
|
Given two lines X1(s) = P1 + s * D1 and X2(t) = P2 + t * D2 we can determine the minimal distance using the squared-distance function for any two points on the lines: Q(s, t) = |X1(s) - X2(t)|^2 The function Q(s, t) is quadratic in s and t and can be represented as Q(s, t) = as^2 + 2bst + ct^2 + 2ds + 2et + f with a = D1 * D1 b = -D1 * D2 c = D2 * D2 d = D1 * (P1 - P2) e = -D2 * (P1 - P2) f = (P1 - P2) * (P1 - P2) Quadratic functions are classfied by the sign of the determinant ac - b^2. For Q(s, t) ac - b^2 = (D1 * D1) * (D2 * D2) - (D1 * D2)^2 = |D1 x D2|^2 >= 0 It is easily proven that the determinant is always >= 0. If the determinant is 0 then the two lines are parllel. To find the minimal distance between the two lines we have to minimize Q(s, t). Since Q is a continuously differentiable function, the minimum occurs where the gradient dQ = (2as + 2bt + 2d, 2bs + 2ct + 2e) = (0, 0). If the lines are not parallel (the determinant ac - b^2 > 0) then we can solve the two equations of dQ = (0, 0) to get s = (be - cd) / (ac - b^2) t = (bd - ae) / (ac - b^2) If, however, the determinant equals 0 the lines are parallel and only one of the two equations is independent. Any choice of s and t satisfying this equation will give us two points on the lines that are closest to one another. The simplest (and therefore less computationally intensive) choice is t = 0 and s = -d / a.
|
Copyright © by Martin Ecker |