# Efficiently determine whether a curve intersects a given rectangle?

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?

• are you assuming the rectangle is axis-aligned with respect to x,y,z ? – spektr Mar 22 '17 at 22:35
• @C.Howard yes I'm assuming its alligned with the R and z axes, thanks for pointing out that omission - I'll edit the question – CBowman Mar 22 '17 at 23:03
• Do you have the angle in cylindrical coordinates that defines what direction $R_c$ is in? There's infinitely many $R-z$ planes until you specify some angle. Now if you wanted to see if the straight line intersects the rectangle, I would just find the plane equation for the rectangle, find the intersection (or closest point of intersection) of the line with this plane, and then check if this location is within the rectangle you care about. – spektr Mar 23 '17 at 4:34
• @C.Howard so the angle doesn't actually matter in this case - so perhaps my use of the word 'plane' is not helpful. We only care whether, for some value of $k$, there exists a $R_k$ and $z_k$ that simultaneously satisfy the inequalities in the question. Another way to think about this is therefore "does the curve intersect the volume created by rotating the rectangle through $2\pi$ in $\phi$" – CBowman Mar 23 '17 at 10:24

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.