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