# Ray polytope intersection?

Context: I am working with polytopes, I am looking for a general way of testing if a point exists within an n-polytope by a vector ray-cast (most of what I have been able to gather while hunting via google was in relation to ray-plane intersection while employing line/plane equations, I believe this approach is restrictive or that a more robust solution can be developed to solve this problem because e.g. I don’t see how the equation for say a non-convex 5-polytope is possible, I may be wrong, regardless I am looking for a solution where I am not being restricted in this manner).

I have a 2-polytope (from a 3-polytope) made up of vertices $$a,b,c$$ and vectors $$\vec{v_1}, \vec{v_2}, \vec{v_3}$$.
$$e$$ is the origin of the ray being cast, $$\vec{u}$$ is the ray-vector, $$d$$ is the point the ray-vector hits the 2-polytope while $$\vec{n}$$ below is the normal to the 2-polytope (I am guessing this might be required for any general solution) How do I get the point $$d$$ where the ray $$\vec{u}$$ hits $$a,b,c$$. I know that this is rather supposed to be a simple question using some vector algebra/rule but the only thing I am seeing is $$\vec{v_1} \times \vec{ad}=0$$, $$\vec{v_2} \times \vec{bd}=0$$ etc since they lie within the same plane.

I hope to adapt the logic of whatever general solution provided to the problem above to that being addressed by the context provided earlier

• What do you mean by "a point exists within a polytope" ? What does "within" mean ? Are you assuming that you are given a point that is already in the plane of the polytope ? Mar 3, 2022 at 16:40
• @Calmdownandhavesometea ”…within a polytope” asper a point lying on or being enclosed by the surfaces of a polytope e.g. a point existing within a 3-polytope would mean that point is either being enclosed by all or it lying on any 2-polytopes(surfaces) of the 3-polytope, same logic would also be applicable say we have a 4-polytope; that would mean the point is either being enclosed by all or it lying on any of its 3-polytopes .etc Mar 4, 2022 at 9:11

With $$\vec d=\vec e+\lambda\vec u$$, you want $$\left(\vec e + \lambda\vec u\right)\cdot\vec n=\vec a\cdot n$$, so

$$\lambda=\frac{\left(\vec a-\vec e\right)\cdot\vec n}{\vec u\cdot\vec n}\;,$$

which gives you

$$\vec d=\vec e+\frac{\left(\vec a-\vec e\right)\cdot\vec n}{\vec u\cdot\vec n}\,\vec u\;.$$

Dot products are your (dimension-independent) friend here. One approach is to write $$d = e + tu$$ with $$t$$ unknown. The point $$d$$ lies in the plane containing $$a$$ and perpendicular to $$n$$ if and only if $$0 = n \cdot (d - a) = n \cdot (e - a) + t(n \cdot u),$$ from which we obtain $$t = \frac{n \cdot (a - e)}{n \cdot u}$$, and therefore $$d = e + \frac{n \cdot (a - e)}{n \cdot u}\, u.$$

The ray $$R$$ from the point $$e$$ in the direction of the vector $$\vec{u}$$ can be expressed parametrically as the set of points $$(x,y,z)$$ such that \left\lbrace \begin{align*} x&=e_x+u_xt\\ y&=e_y+u_yt\\ z&=e_z+u_zt\\ \end{align*} \right. where the parameter $$t$$ satisfies $$t\ge 0$$, but is otherwise arbitrary.

Let $$P$$ be the plane through the $$3$$ distinct points $$a,b,c$$.

Choose a point $$(x_0,y_0,z_0)$$ on the plane $$P$$ (for example you could take $$(x_0,y_0,z_0)=a$$).

Then $$P$$ is the set of points $$(x,y,z)$$ satisfying the equation $$n_x(x-x_0)+n_y(y-y_0)+n_z(z-z_0)=0$$ Assume $$e$$ is not on $$P$$.

To find the point $$d$$ where the ray $$R$$ passes through the plane $$P$$ simply plug the parametric form for $$R$$ into the equation for $$P$$ and solve for $$t$$. Since $$e$$ is not on $$P$$, there will be at most one solution for $$t$$. The point $$d$$ exists provided a solution for $$t$$ exists and has $$t > 0$$.

Let $$T$$ denote the closed triangular region with vertices $$a,b,c$$.

To determine whether $$d$$ resides in $$T$$, proceed as follows . . .

. Express the vector $$\vec{d}-\vec{a}$$ as a linear combination of the vectors $$\vec{b}-\vec{a},\vec{c}-\vec{a}$$. $$d-a = g_b(\vec{b}-\vec{a}) + g_c(\vec{c}-\vec{a})$$ Then expand and rewrite the above equation in the form $$d = h_a\vec{a} + h_b\vec{b} + h_c\vec{c}$$ where $$h_a+h_b+h_c=1$$.

Then $$d$$ resides in $$T$$ if and only if $$h_a,h_b,h_c\ge 0$$.

Suppose the 2-polytope has $$N$$ vertices $$\{P_i\}$$, numbered $$i = 0, 1, 2, ..., N-1$$, such that the numbering is sequential, i.e.

$$(P_k - P_i) \times (P_{k+1} - P_i )$$ doesn't change its sign for all $$i$$ and $$k$$

Now define the normal to the plane of the 2-polytope as follows

$$n = (P_1 - P_0) \times (P_2 - P_0)$$

To determine if a point $$Q$$ lies inside the 2-polytope, we have to consider all the sides and define vectors

$$V_i = P_{i+1} - P_i$$

And define the vectors pointing to the inside of the 2-polytope as follows

$$U_i = n \times V_i \hspace{25pt}, i = 0, 1, 2,... , N-1$$

Then, evaluate the dot product

$$\alpha_i = U_i \cdot (Q - P_i)$$ for all $$i = 0, 1, 2, ..., N-1$$

For point $$Q$$ to be within the 2-polytope we must have

$$\alpha_i \ge 0 , \hspace{25pt} i = 0, 1, 2, ..., N-1$$