Efficiently determine whether a curve intersects a given rectangle?

Question

Suppose we have a straight line in Cartesian space such that $$ x_k = x_0 + k \delta x, \quad \quad y_k = y_0 + k \delta y, \quad \quad z_k = z_0 + k \delta z $$ where $k$ can take any real value. If we project that line into cylindrical polar coords then $$ R_k = \sqrt{ x_{k}^{2} + y_{k}^{2} }. $$ Now suppose there exists some rectangle in the $(R,z)$ plane having a centre at $(R_c, z_c)$ and sides of length $L_R$ and $L_z$.

The rectangle is aligned with the $R$ and $z$ axes such that a point on the curve is inside the rectangle if $|R_c - R_k| < L_R / 2$ and $|z_c - z_k| < L_z / 2$.

Can anyone suggest an efficient way to compute whether the projection of the line onto the $(R,z)$ plane intersects the rectangle?

Answer 1

Given a line

$$\mathcal L := \left\{ \begin{bmatrix} x_0\\ y_0\\ z_0\end{bmatrix} + t \begin{bmatrix} v_x\\ v_y\\ v_z\end{bmatrix} : t \in \mathbb R \right\}$$

and a cylindrical shell of thickness $r_2 - r_1$ and height $z_2 - z_1$

$$\mathcal S := \left\{ \begin{bmatrix} x\\ y\\ z\end{bmatrix} : (r_1^2 \leq x^2 + y^2 \leq r_2^2) \land (z_1 \leq z \leq z_2) \right\}$$

we would like to determine whether $\mathcal L \cap \mathcal S \neq \emptyset$.

Intersecting line $\mathcal L$ with the cylindrical shell $\mathcal S$, we obtain the following system of $4$ inequalities in $t$

$$\begin{array}{rl} (x_0 + v_x t)^2 + (y_0 + v_y t)^2 &\geq r_1^2\\ (x_0 + v_x t)^2 + (y_0 + v_y t)^2 &\leq r_2^2\\ z_0 + v_z t &\geq z_1\\ z_0 + v_z t &\leq z_2\end{array}$$

We can decide the feasibility of this system of linear and quadratic inequalities using quantifier elimination. Mathematica has the function Resolve. There are also QEPCAD and Redlog. Of course, we can also do quantifier elimination by hand, but it is rather cumbersome.