1
$\begingroup$

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.

enter image description here

$\endgroup$
1
$\begingroup$

Cross_Rect_1

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$
  1. translate/rotate the rectangle and the line segment so that the rectangle becomes axis parallel, with a corner at the origin;

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yves Daoust, thank you very much! Can you give some code/operations example, please? I'll be very grateful to you. $\endgroup$ – Ilya Jul 24 '15 at 15:59
  • $\begingroup$ This is a stripped down version of the Cohen-Sutherland algorithm. with a little effort you will find versions on the web. Remove the computation of intersections. You can also exploit a variant en.wikipedia.org/wiki/Line_clipping. $\endgroup$ – Yves Daoust Jul 24 '15 at 16:03
-1
$\begingroup$

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.

line/rectangle

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.