# ray - parallelogram intersection in 2d

i'm looking for a fast method to get the intersecting points between a ray and a parallelgram defined by the 4 vertices!

till now i've thought to test the intersection point between ray and the 4 edge, but mayebe there are computationally faster OR mathematically more elegant way to do it.

mayebe check ray-triangles intersection with the 4 triangles that forms the parallelogram?

EDIT: as copper.hat point me out the intersection points could be 0, 1 or 2. or the entire edge if the ray is coincident with an edge

-
The intersection can be $0,1,2$ points or an entire edge. – copper.hat May 7 '12 at 23:25
yeah, thanks for point me out, the question is modified – nkint May 8 '12 at 8:10

Assume that the ray starts at the origin $o$ and has direction $u\ne0$, and let $a_0$, $a_1$, $a_2$, $a_3$ be the four vertices. The line through $o$ in direction $u$ intersects the line $a_0\vee a_1$ in a point satisfying $$t u= a_0+s (a_1-a_0)$$ with real $s$ and $t$. It follows that $$0=u\wedge a_0 +s u\wedge (a_1-a_0)\ ,\qquad t u\wedge(a_1-a_0)=a_0\wedge(a_1-a_0)\ ,$$ which gives $$s=-{u\wedge a_0\over u\wedge(a_1-a_0)}\ ,\qquad t={a_0\wedge a_1\over u\wedge(a_1-a_0)}\ .$$ The ray intersects the parallelogram side $[a_0,a_1]$ iff $t\geq0$ and $0\leq s\leq1$. Leaving the special case that the ray passes through one of the endpoints apart, the latter condition is easily seen to be equivalent with ${\rm sgn}(u\wedge a_0)=-{\rm sgn}(u\wedge a_1)$ (as is geometrically evident).

These preparations suggest the following procedure: Compute the eight quantities $$p_k:= a_{k-1}\wedge a_k\ ,\quad q_k:=u\wedge a_k\qquad(1\leq k\leq 4(=0))\ .$$ Assume for simplicity that all $q_k\ne0$. If there is a sign change between $q_{k-1}$ and $q_k$ check whether $$t_k:={p_k\over q_k-q_{k-1}}\geq0\ .$$ In this case the ray hits the side $[a_{k-1},a_k]$ of theparallelogram at the point $t_k u$.

-

Classify the four vertices with respect to the line containing the ray by computing the sign of the (degree-one) expression defining the line. If all four vertices have the same sign, then the line does not cross the parallelogram. Othewise, find the two edges where the signs differ and find the intersection points. Make sure you check the intersection points are in the ray. You'll also have to take care of the special cases of the line passing through one vertex or an edge.

-
If I understand you correctly, the sign may differ, but still have no intersection with the ray. For example, the 4 vertices may lie in the half-space 'behind' the ray, yet have vertices on either side of the line. I'm not sure which computations are considered expensive, but it would seem to me that computing which quadrant (wrt to the ray) the vertices lie in, will allow you to determine exactly which pairs of vertices to check for intersection. – copper.hat May 8 '12 at 1:05
@copper.hat, you're right, of course. But the test of whether the intersection point was in the ray was part of finding the intersection point. – lhf May 8 '12 at 1:16
True. I started counting flops but got lost after a while! – copper.hat May 8 '12 at 2:02
sorry, @lhf i didn't understand very well what you mean – nkint May 8 '12 at 8:15
@nkint, I've edited my answer slightly. – lhf May 8 '12 at 10:48