I asked a question a while back about how to form a (Cylinder in 3D from five points? ). I'm still in search for a good solution, as my last solution produced too much error and required nine points.
Here's my updated problem statement.
A cylinder's surface can easily be expressed as all points $p$ which reside a particular distance $r$ from a line with origin $c$ and direction $n$ (seven variables in total).
A simple way to express this is: $\left\Vert (p - c) \times n \right\Vert_2 = r$
To make my life sane, I have added the following requirements that ought to reduce my problem space to five free variables:
$n^T \; n = 1$
$c^T \; n = 0$
After a bunch of steps (including using orthogonal vectors to $n$ to do projections and avoid a cross product), I found that I can express it as:
$n^T \; P \; n + 2 \; c^T p + r ^2 - c^T c - 1 = 0$
where $P = p\; p^T = \left[\begin{array}{c c c} p_x^2 & p_x p_y & p_x p_z \\ p_x p_y & p_y^2 & p_y p_z \\ p_x p_z & p_y p_z & p_z^2 \end{array}\right]$
In theory, with only five free variables, I should be able to use five points to recover the free variables.
But I had another thought: After doing a partial Gaussian elimination (with five input points), I can produce a single symmetric matrix $M$ such that:
$n^T \; M \; n = 0$.
Now the question still remains - how do I solve for $n$? I tried to diagonalize $M$ via eigenvalues/vectors to develop a solution for $n$, but I couldn't figure out how to transform the solution space back to $n$ without complications.
Any advice? I'm sure I probably need at least two $M$ matrices, along with the earlier assumption ($n^T \; n = 1$) to recover $n$, but I'm just plain lost. It's been way too long since I took linear algebra.
Thanks in advance!
I think I've found a five-point solution. I don't like it, but it gets me there...
If I apply a transformation to my points and variables (via transform, rotate, uniform scaling), the solution is a little bit easier to reach.
Choosing 3 initial points, it should be possible to find a non-skewing transform T (e.g. the cylinder would still be a cylinder after the transform) such that after the transform, the three points will reside at:
$\begin{array}{c c c} [0 & 0 & 0] \\ [1 & 0 & 0] \\ [0 & a & 0] \end{array}$
Plugging these 3 points into the original quadric equation above (with a post-transformation $r'$, $c'$, $n'$, and $r'$), we can determine that:
$r'^2 - c'^T c' = 0$ (this is useful in simplifying the original quadric)
$c_x' = \dfrac{n_x'^2-1}{2}$
$c_y' = \dfrac{a^2\; n_y'^2 - 1}{2a}$
$n_z' = \sqrt{1-n_x'^2-n_y'^2}$ (from $n^T n = 1$)
$c_z' = \dfrac{c_x'\;n_x' + c_y'\;n_y'}{n_z'}$ $ = \dfrac{n_x'^3/2-n_x'/2 + a \; n_y'^3/2 - n_y'/2a}{\sqrt{1-n_x'^2-n_y'^2}}$ (from $c^T n = 0$)
The quadric is now dependent on just two free variables $n_x'$ and $n_y'$, so with two more points (bringing the total to five points) the solution should be achievable.
The only downside is that with $n_z' = \sqrt{1-n_x'^2-n_y'^2}$, my 5-point solution will probably end up being a pretty high-order polynomial.
So, to go back to my original question, yes, it is possible to find a cylinder from only five points, but it doesn't appear to be practical.