3
$\begingroup$

For a particular purpose, I want to define a cylinder in 3D space and go through a list of given 3D points and tell if the point is inside or outside the cylinder volume. I can define the cylinder by specifying 2 points along the axis, and the radius of the cylinder.

A (x1, y1, z1 )
B (x2, y2, z2 )
and radius = R

right now what I'm doing is that I find the vector AB, connecting A and B by

AB = A - B

then calculate the shortest distance from each point to the vector AB, if the distance is less than R, the point is inside.

The problem with this method is that it only works if either A or B is the origin.

for example, If I try to find the points inside the cylinder connecting

p1 ( 100,10,20)
p2 ( 100,-10,20)

we get the points inside the cylinder ( 0,20,0) [ which is actually the cylinder formed by ( 0,0,0) and (0,20,0) ]

certainly, I'm missing something, can anyone point it out?

N.B: For some complicated reason, I can't use an auxiliary coordinate system or shift the origin. What I'm looking for is some pure mathematical expression ( if it exists ), which can take the particulars of the cylinder and the required point and give if it is inside or outside.

similar to Empty2's answer on this question

$\endgroup$
4
  • $\begingroup$ Is the cylinder infinite ? $\endgroup$
    – user65203
    Jan 22, 2020 at 13:23
  • $\begingroup$ "it only works if either A or B is the origin": you must compute the distance to the line, not to the vector. $\endgroup$
    – user65203
    Jan 22, 2020 at 13:31
  • $\begingroup$ If your algorithm already works with, say, $A$ is the origin, why don't you "translate" $A$ (to the origin), $B$ (to $B-A$) and every point $X$ (to $X-A$), by the vector $-A$, and just apply your working algorithm. $\endgroup$
    – user700480
    Jan 22, 2020 at 13:35
  • $\begingroup$ The cylinder is not infinite, I wish to contain it between these points A and B. For some complicated reason, I can't use an auxiliary coordinate system or shift the origin. What I'm looking for is some pure mathematical expression ( if it exists ), which can take the particulars of the cylinder and the required point and give if it is inside or outside. similar to Empty2's answer on this math.stackexchange.com/questions/1472049/… $\endgroup$
    – brownser
    Jan 22, 2020 at 13:56

4 Answers 4

3
$\begingroup$

Solution

Consider the line coordinates with direction $\boldsymbol{e} = \boldsymbol{r}_B-\boldsymbol{r}_A$ and moment $\boldsymbol{m} = \boldsymbol{r}_A \times \boldsymbol{r}_B$. These two vectors represent the infinite line between ${A}$ and ${B}$.

A point ${P}$ with position $\boldsymbol{r}_{P}$ lies in the cylinder between $\boldsymbol{A}$ and $\boldsymbol{B}$ and radius $R$ if:

  1. Distance of $P$ to line $AB$ is equal or less than $R$ $$d = \frac{\|\boldsymbol{m} + \boldsymbol{e}\times\boldsymbol{r}_{P}\|}{\|\boldsymbol{e}\|}\leq R$$

    or the alternate formulation of the above

    $$d = \frac{\| \boldsymbol{e}\times\left(\boldsymbol{r}_{P}-\boldsymbol{r}_{A}\right) \|}{\|\boldsymbol{e}\|}\leq R$$

  2. Closest point $Q$ on line to $P$ is $$\boldsymbol{r}_{Q}=\boldsymbol{r}_{P}+\frac{\boldsymbol{e}\times\left(\boldsymbol{m}+\boldsymbol{e}\times\boldsymbol{r}_{P}\right)}{\|\boldsymbol{e}\|^{2}}$$

  3. The barycentric coordinates of $Q$ $\begin{pmatrix}w_{A} & w_{B}\end{pmatrix}$ such that $\boldsymbol{r}_{Q}=w_{A}\boldsymbol{r}_{A}+w_{B}\boldsymbol{r}_{B}$ are

    $$\begin{array}{c} w_{A}=\frac{\|\boldsymbol{r}_{Q}\times\boldsymbol{r}_{B}\|}{\|\boldsymbol{m}\|}\\ w_{B}=\frac{\|\boldsymbol{r}_{Q}\times\boldsymbol{r}_{A}\|}{\|\boldsymbol{m}\|} \end{array}$$ This works only when $\|\boldsymbol{m}\| >0$, or the cylinder axis does not go through the origin.

  4. Check that point $Q$ lies between $A$ and $B$ by making sure the barycentric coordinates are between 0 and 1

    $${\rm inside}=\left(w_{A}\ge0\right){\rm and}\left(w_{A}\le1\right){\rm and}\left(w_{B}\ge0\right){\rm and}\left(w_{B}\le1\right)$$


Example

The end points of a cylinder with $R=1.2$ are located at $$ \begin{aligned} \boldsymbol{r}_A & = \pmatrix{3\\0\\0} \\ \boldsymbol{r}_B & = \pmatrix{0\\7\\0} \end{aligned} $$

The target point has coordinates $$ \boldsymbol{r}_P = \pmatrix{1\\2\\0} $$

  1. The infinite line is described by $$ \begin{aligned} \boldsymbol{e} & = \pmatrix{-3 \\ 7 \\ 0} \\ \boldsymbol{m} & = \pmatrix{0 \\ 0 \\ 21} \end{aligned} $$
  2. The distance of the target point to the line is $$ d = \frac{ \pmatrix{0 \\ 0 \\ 21} + \pmatrix{-3 \\ 7 \\ 0} \times \pmatrix{1\\2\\0}}{ \| \pmatrix{-3 \\ 7 \\ 0} \|} = \frac{\| \pmatrix{0 \\ 0 \\ 8} \|}{\sqrt{58}} = \tfrac{8}{\sqrt{58}} = 1.0505 $$

  3. Point on line closest to target point is $$ \boldsymbol{r}_Q = \pmatrix{1\\2\\0} + \frac{\pmatrix{-3 \\ 7 \\ 0} \times \pmatrix{0 \\ 0 \\ 8}}{58} = \pmatrix{1\\2\\0} + \frac{ \pmatrix{56\\24\\0}}{58} = \pmatrix{\tfrac{57}{29} \\ \tfrac{70}{29} \\ 0} = \pmatrix{1.9655 \\ 2.41379 \\ 0} $$

  4. Barycentric coordinates are $$ \begin{aligned} w_A & = \frac{ \| \pmatrix{\tfrac{57}{29} \\ \tfrac{70}{29} \\ 0} \times \pmatrix{0\\7\\0} \|}{\| \pmatrix{0\\0\\21} \|} = \frac{ \| \pmatrix{0\\0\\ \frac{399}{29}} \|}{21} = \tfrac{19}{29} = 0.6552 \\ w_B & = \frac{ \| \pmatrix{\tfrac{57}{29} \\ \tfrac{70}{29} \\ 0} \times \pmatrix{3\\0\\0} \|}{\| \pmatrix{0\\0\\21} \|} = \frac{ \| \pmatrix{0\\0\\ -\frac{210}{29}} \|}{21} = \tfrac{10}{29} = 0.34483 \end{aligned}$$

  5. Check that $w_A \ge 0\;\checkmark$, $w_A \le 1\;\checkmark$, $w_B \ge 0\;\checkmark$, $w_B \le 1\;\checkmark$.


Edit 1

As noted this method falls flat when the axis of the cylinder goes through the origin. This is because the barycentric calculation above is actually a shortcut of a more general method. To solve for the barycentric coordinates in the general case, you need to solve the following 2×2 system

$$ \left| \begin{matrix}1 + \boldsymbol{r}_A \cdot \boldsymbol{r}_A & 1 + \boldsymbol{r}_A \cdot \boldsymbol{r}_B \\ 1 + \boldsymbol{r}_A \cdot \boldsymbol{r}_B & 1 + \boldsymbol{r}_B \cdot \boldsymbol{r}_B \end{matrix} \right| \pmatrix{w_A \\ w_B} = \pmatrix{1 + \boldsymbol{r}_Q \cdot \boldsymbol{r}_A \\ 1 + \boldsymbol{r}_Q \cdot \boldsymbol{r}_B } $$

where $\cdot$ is the dot product of two vectors resulting in a scalar value.

$\endgroup$
10
  • $\begingroup$ Thanks, this is working fine. For future references, can you also tell me, from where did you find this? Book, website etc for future references? As I have to solve more problems like these and I could not find this with a lot of Googling. Thanks in advance :_). $\endgroup$
    – brownser
    Jan 22, 2020 at 15:38
  • $\begingroup$ The math here is something I am very familiar with ever since graduate school. But you can find some of the above information in Chapter 3 of "Foundations of Game Engine Development", Vol 1, Eric Lengyel. $\endgroup$ Jan 22, 2020 at 15:44
  • $\begingroup$ Also read about Plucker Coordinates of a spatial line. This formulation is quite powerful. The concepts here touch also on the subject of Projective Geometry & Homogeneous Coordinates. $\endgroup$ Jan 22, 2020 at 15:57
  • 1
    $\begingroup$ @user297271 - I have confirmed the equation is correct. You can rewrite it as $$d = \frac{\|\boldsymbol{e}\times\left(\boldsymbol{r}_{P}-\boldsymbol{r}_{A}\right)\|}{\|\boldsymbol{e}\|}$$ where $\boldsymbol{e}=\boldsymbol{r}_{B}-\boldsymbol{r}_{A}$. Maybe this form is less prone to implementation bugs. $\endgroup$ Feb 20, 2020 at 19:19
  • 1
    $\begingroup$ @user297271 - The formula in your link is identical to my formula. Here is the proof: $$\begin{aligned}d & =\frac{\|\left(\boldsymbol{r}_{B}-\boldsymbol{r}_{P}\right)\times\boldsymbol{e}\|}{\|\boldsymbol{e}\|}\\ & =\frac{\|\boldsymbol{e}\times\left(\boldsymbol{r}_{P}-\boldsymbol{r}_{B}\right)\|}{\|\boldsymbol{e}\|}\\ & =\frac{\|\boldsymbol{e}\times\left(\boldsymbol{r}_{P}-\left(\boldsymbol{r}_{A}+\boldsymbol{e}\right)\right)\|}{\|\boldsymbol{e}\|}\\ & =\frac{\|\boldsymbol{e}\times\left(\boldsymbol{r}_{P}-\boldsymbol{r}_{A}\right)\|}{\|\boldsymbol{e}\|} \end{aligned}$$ $\endgroup$ Feb 20, 2020 at 19:26
0
$\begingroup$

You should consider an auxiliary coordinate frame that has its origin at $A$ and its $z$ axis parallel to $AB$. The coordinate transformation is the combination of a translation and a rotation; it can be obtained by Gram-Schmidt orthogonalization.

Now the inside of the cylinder has the simple equation

$$x^2+y^2\le R^2.$$

(And possibly, $0\le z\le \|AB\|$.)


Alternatively, let the test point be $P$. An arbitrary point along the cylindre axis is given by

$$tA+(1-t)B$$ where $t$ runs from $0$ to $1$.

Now the shortest squared distance from $P$ to $Q$ is the one that minimizes

$$(tPA+(1-t)PB)^2=(PB+tBA)^2=PB^2+2PB\cdot BA\,t+BA^2 t^2.$$

By canceling the derivative we obtain

$$t=-\dfrac{PB\cdot BA}{BA^2},$$ which tells if the point lies between the two basis, and the distance is

$$\left\|PB-\dfrac{PB\cdot BA}{BA^2}BA\right\|=\sqrt{PB^2-\frac{(PB\cdot BA)^2}{BA^2}}.$$

$\endgroup$
0
$\begingroup$

For your information: I think you mean by a cilinder a body with a circle (not an eclipse) as a ground surface. In $2D$ it simply means that you want to verify if a point $(x_1, y_1)$ is located within the circle with radius $R$, to which most people will say "Easy: just check if $x_1^2+y_1^2 \le R^2$", which is, mathematically speaking, completely correct.

However, when dealing with computers, the situation becomes more complicated: although the mentioned formula is still correct, an easy improvement is possible:

// This is the normal function
function bool inside(float X1, float Y1, float R)
{
    return X1^2+Y1^2 <= R^2;
}

As you can easily see, you are doing at least two multiplications of floating point numbers, which might be very time consuming (certainly when you start checking hundreds, thousands, ... of numbers).
Therefore you can do the following instead:

// This is a faster function
function bool inside_fast(float X1, float Y1, float R)
{
    if (abs(X1) > R
      return false;
    if (abs(Y1) > R
      return false;
    return X1^2+Y1^2 <= R^2;
}

This will check if your point $(x_1, y_1)$ is located within the square with radius $R$. In most cases, your point will be outside and you get a false result, without needing to do any floating point calculation. Only in the case where your point is inside that square, the complete calculation will be performed.

$\endgroup$
0
$\begingroup$

We can solve this by constructing the cylinder negatively: start with an infinite space, and throw out everything that isn't within the cylinder. This uses John Alexiou's answer but makes it significantly simpler for the second part, as well as more generally correct as it has no special cases where it doesn't work.

This is done with 3 cuts:

First, a cylindrical cut of radius R about an infinite line that goes through A and B. This proceeds as per John Alexiou's answer above:

  • Points A and B have vectors $\boldsymbol{r}_A$ and $\boldsymbol{r}_B$ .

  • Direction between them is:

    $$\boldsymbol{e} = \boldsymbol{r}_B-\boldsymbol{r}_A$$

  • Distance from any point P at $\boldsymbol{r}_P$ to the line is:

    $$d = \frac{\| \boldsymbol{e}\times\left(\boldsymbol{r}_{P}-\boldsymbol{r}_{A}\right) \|}{\|\boldsymbol{e}\|}$$

  • Exclude all points with $d > R$.

    This can be optimised slightly by comparing the square of the magnitude and radius, avoiding the square root.

Second, a planar cut that throws away the space above the "top" of the cylinder, which I'm calling A.

  • The plane is defined by any point on it (A will do), and any normal pointing out of the cylinder, $-\boldsymbol{e}$ will do (i.e. in the opposite direction to $\boldsymbol{e}$ as defined above).

  • We can see which side a point is of this plane as per Relation between a point and a plane:

    The point is "above" the plane (in the direction of the normal) if:

    $$(\boldsymbol{r}_P - \boldsymbol{r}_A) \cdot -\boldsymbol{e} > 0$$

  • Exclude points which match the above.

Third, a planar cut which throws away the space below the bottom of the cylinder B.

  • Same as the previous step, but with the normal vector in the other direction, so the condition is:

    $$(\boldsymbol{r}_P - \boldsymbol{r}_B) \cdot \boldsymbol{e} > 0$$

This process constructs the cylinder negatively, and translates directly into 3 tests which must all pass if a point is within the cylinder.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .