# 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$.