Polygon and line intersection Does anyone help me with the fast algorithm to determine the intersection of a polygon (rotated rectangle) and a line (definite by 2 points)?
The only true/false result is needed.

 A: 
Take your rectangle $ABCD$, put ,e.g., 
$$
\left| {AB} \right| = b\quad \left| {AD} \right| = d
$$
and consider the unit vectors
$$
{\bf u} = {{\mathop {AB}\limits^ \to  } \over {\left| {AB} \right|}} = {1 \over b}\mathop {AB}\limits^ \to  \quad \quad
 {\bf v} = {{\mathop {AD}\limits^ \to  } \over {\left| {AD} \right|}} = {1 \over d}\mathop {AD}\limits^ \to  
$$
Then a generic point $P$ will be inside the rectangle if the projection of $\vec {AP}$
onto $\bf u$ and $\bf v$ is
$$
\left\{ \matrix{
  0 \le \mathop {AP}\limits^ \to   \cdot {\bf u} \le b \hfill \cr 
  0 \le \mathop {AP}\limits^ \to   \cdot {\bf v} \le d \hfill \cr}  \right.
$$
The point $P$ will be on and inside the segment if
$$
\mathop {OP}\limits^ \to   = \lambda \mathop {OQ}\limits^ \to   + \left( {1 - \lambda } \right)\mathop {OR}\limits^ \to  \quad \left| {\;0 \le \lambda  \le 1} \right.
$$
or what is the same, if
$$
\mathop {AP}\limits^ \to   = \mathop {AR}\limits^ \to   + \lambda \mathop {RQ}\limits^ \to  \quad \left| {\;0 \le \lambda  \le 1} \right.
$$
So the rectangle and the segment will have points in common iff
$$
\begin{array}{l}
 \left\{ \begin{array}{l}
 0 \le \mathop {AP}\limits^ \to   \cdot {\bf u} \le b \\ 
 0 \le \mathop {AP}\limits^ \to   \cdot {\bf v} \le d \\ 
 \mathop {AP}\limits^ \to   = \mathop {AR}\limits^ \to   + \lambda \mathop {RQ}\limits^ \to   \\ 
 0 \le \lambda  \le 1 \\ 
 \end{array} \right.\quad  \Rightarrow \quad \left\{ \begin{array}{l}
 0 \le \lambda \mathop {RQ}\limits^ \to   \cdot {\bf u} + \mathop {AR}\limits^ \to   \cdot {\bf u} \le b \\ 
 0 \le \lambda \mathop {RQ}\limits^ \to   \cdot {\bf v} + \mathop {AR}\limits^ \to   \cdot {\bf v} \le d \\ 
 0 \le \lambda  \le 1 \\ 
 \end{array} \right. \\ 
  \Rightarrow \quad \left\{ \begin{array}{l}
 \frac{{\mathop {RA}\limits^ \to   \cdot {\bf u}}}{{\mathop {RQ}\limits^ \to   \cdot {\bf u}}} \le \lambda  \le \frac{{\mathop {RB}\limits^ \to   \cdot {\bf u}}}{{\mathop {RQ}\limits^ \to   \cdot {\bf u}}} \\ 
 \frac{{\mathop {RA}\limits^ \to   \cdot {\bf v}}}{{\mathop {RQ}\limits^ \to   \cdot {\bf v}}} \le \lambda  \le \frac{{\mathop {RD}\limits^ \to   \cdot {\bf v}}}{{\mathop {RQ}\limits^ \to   \cdot {\bf v}}} \\ 
 0 \le \lambda  \le 1 \\ 
 \end{array} \right. \\ 
 \end{array}
$$
Therefore it is just to check if the tree intervals specified for $\lambda$
have a common intersection or not, and if they have that will 
identify an interval for $\lambda$ wich gives the points of the segment internal
to the rectangle.
Only it is to pay attention to the special cases in which $\mathop {RQ}\limits^ \to   \cdot {\bf u} =0$,
which means that the segment $RQ$ is normal to side $AB$, or otherwise that $\mathop {RQ}\limits^ \to   \cdot {\bf v} =0$
which means normal to the $AD$ edge.
In one of this cases (cannot be both) the corresponding condition shall become , e.g. for the first
$$
\mathop {RA}\limits^ \to   \cdot {\bf u} \le 0 \le \mathop {RB}\limits^ \to   \cdot {\bf u}
$$
and the intersection for $\lambda$ will be given by other two intervals only.
A: *

*translate/rotate the rectangle and the line segment so that the rectangle becomes axis parallel, with a corner at the origin;

*perform the region discussion as in the Cohen-Sutherland Line Clipping algorithm.
In case of a trivial reject or trivial accept, you are done. Otherwise, you will need to plug the coordinates of a corner in the implicit equation of the line of support of the line segment.
You will make is fast by unrolling the decision tree.
For one line segment, the procedure will cost:


*

*eight multiplies and eight adds to apply the rotation/translation to the endpoints,

*eight comparisons for the region dicusssion,

*in case a line comparison is needed, two extra multiplies and adds.
A: If your lines and rectangles are fairly predictable, a fast techinque is to use the rectangle as aligned to the axis, and rotate the line segment accordingly.

Parameterize the line, and see if any point lies inside the rectangle.
