10
$\begingroup$

Given that all 3 lines are infinitely long, how do I find the smallest sphere that intersects (or touches) those 3 lines in 3D?

There is a simple case where the sphere can be calculated from just 2 lines and the third line can just pass through the sphere. You can ignore that case.

The case I want to solve here is when the distances from the sphere center to all 3 lines are equal (all the lines are tangent to the sphere surface). Trying to solve this case leads me to the path of solving quadratic equation systems and Lagrange multiplier which I cannot solve for an exact closed-form solution.

As I want this solution to be efficient, I try to avoid iterative methods/numerical optimizations.

$\endgroup$
3
  • $\begingroup$ Do you know beforehand the radius of your sphere ? $\endgroup$
    – Jean Marie
    Nov 21 at 6:39
  • $\begingroup$ Both radius and the center's coordinate are not known. $\endgroup$
    – koonyook
    Nov 22 at 7:04
  • 1
    $\begingroup$ The locus of the centre of the spheres touching three lines is the intersection of two a quadrics, i.e. a quartic curve. See here: nerds-math.com/1043/synthetic-geometry $\endgroup$ Nov 22 at 14:06
2
$\begingroup$

Let the three lines be given by parametric equations

$ R_i(t) = P_{i} + t V_{i} ,\hspace{20pt} i = 1, 2, 3 $

where the direction vectors $\{ V_i \}$ are assumed to be unit vectors.

Given the distance $d$ between the center of the sphere $C$ and each of these lines ($d$ is the radius of the sphere), we can write three equations in the vector $C$:

$(C - P_{i} )^T (I_3 - {V_i V_i}^T ) (C - P_{i} ) = d^2, \hspace{20pt} i = 1, 2, 3 $

The above equation(s) are three equations of 3 cylinders (which are quadrics) having axes pointing along $\{V_i \}$ and passing through $\{ P_i \}$ respectively.

I don't know if an analytic solution exists for $C$ given $d$, but what I did was vary $d$ (in a descending variation) and compute $C$ numerically until no solution was possible. This way I was able to determine the minimum $d$ possible which is the radius of the smallest sphere.

$\endgroup$
7
  • $\begingroup$ [+1] for the equation of a cylinder. Can you give me a reference (preferably with derivation) for this equation? $\endgroup$
    – brainjam
    Nov 25 at 16:52
  • 1
    $\begingroup$ Some intuition dropping $i$ to look at one cylinder: $C$ is any point on the cylinder's surface, and $P$ is some fixed point on the axis. So $C-P$ points towards $P$ from surface point $C$ potentially very far down the axis from $P$ (i.e. as induced by large $t$). $VV^T$ is the matrix which projects $\mathbb{R}^3$ onto the axis, so the vector produced by $(I-VV^T)(C-P)$ points from surface point $C$ to the nearest point on the axis. i.e. a 'radius vector' for the cylinder's cross section at $C$. The remaining multiplication by $(C-P)^T$ is the inner product of... $\endgroup$
    – kdbanman
    Nov 25 at 18:50
  • 1
    $\begingroup$ ...the radius vector and the vector pointing from $C$ to $P$. A) Consider the trivial case where $P$ is the axis point nearest to $C$. Then our projection subtraction step is the identity, and our inner product's square is distance from $C$ to $P$. By fixing this at $d^2$, we describe those points $C$ which are the endpoints of fixed-length vectors orthogonal to the axis, which is a circle of radius $d$. (Note: $d$ is simultaneously the radius of our cylinder and the radius of the circle which OP's problem requests. That's why @Potato's system of quadrics solves the problem.) ... $\endgroup$
    – kdbanman
    Nov 25 at 19:18
  • 1
    $\begingroup$ ... B) For the remaining cases where the axis point nearest $C$ is some other point along $R(t)$, the inner product jointly measures alignment between the 'radius vector' at $C$ and the distance from $C$ to $P$ as we move away from the $t=0$ trivial case. I'll leave it an exercise to the reader to intuit why the described alignment-distance balance is a cylinder (points $C$ fixed distance from the axis) and not something like, say, a double-ended horn (points $C$ become more distant from the axis as $t$ grows.) Also it's an exercise for me, as I don't yet have the intuition myself! $\endgroup$
    – kdbanman
    Nov 25 at 19:22
  • 1
    $\begingroup$ @kdbanman thanks very much. "$VV^T$ is the matrix which projects $\mathbb{R}^3$ on the axis" is the key insight I was missing. $\endgroup$
    – brainjam
    Nov 25 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.