Polygon and line intersection

Question

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.

Answer 1

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.

Answer 2

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.