# How to check any point on polygon intersects with line?

I have input polygon, lets say I have x,y,width,height of rectangle on 2-d plane. I want to know does this ploygon intersects with a line ? What math I equations to use? I want to know, Red Rectangle intersects with blue line?

### Solutions for Rectangle

Check each edge intersects with line, may be simple and basic solution. Is there any other way?

Pls add tags for this questions.

• Can you explain what the x,y,w,h mean? I'm assuming x and y are describing a point, and the w and h mean width and height. Is this correct? Also, are we to assume that the rectangle sides are parallel to the x and y axes? Aug 28, 2020 at 18:49
• Is this a strictly two dimensional problem? Aug 28, 2020 at 19:18
• @AidenChow - Yes, and it may not be parallel to x and y plane. Aug 29, 2020 at 1:21
• yes only 2-d problem Aug 29, 2020 at 1:21

## 2 Answers

Here is one way of doing it in $$\mathbb{R}^2$$:

Suppose the line has the form $$x_0 + t d \in \mathbb{R}^2$$ for $$t \in \mathbb{R}$$. Let $$p = (-d_2,d_1)$$ ($$p$$ for 'perpendicular').

Given a point $$x$$, project $$x$$ onto the line $$t p$$, $$t \in \mathbb{R}$$ and compute the corresponding $$t$$, that is $$t(x) = {p^T x \over \|p\|}$$.

Now compute $$t(c_k)$$ for each corner $$c_k$$ and then we see that the line intersects the rectangle iff $$\min t(c_k) \le t(x_0)$$ and $$\max t(c_k) \ge t(x_0)$$.

(There is no need to divide by $$\|p\|^2$$ of course when doing the actual computation.)

I am merely stating the obvious:

If the edges of your rectangle are parallel to the $$x$$ and $$y$$ axis (as depicted in your graph), you can simplify the problem as follows. Suppose your line is of the form $$y(x)=ax+b$$.

If $$a>0$$, then it suffices to check whether $$y$$ intersects the left or lower edge of your rectangle.

If $$a=0$$, check whether it intersects the left edge.

If $$a<0$$, check whether it intersects the left or upper edge.

• The OP clarified that the sides might not be parallel to the x and y axes, so this unfortunately invalidates your answer. Aug 29, 2020 at 2:07
• @AidenChow By transforming the coordinate system accordingly (eg rotation), so that the edges of the rectangle are again parallel to the axes, you can apply the above mentioned simplification just as well. Note that this transformation will, in general, also lead to new a and b values. Aug 29, 2020 at 6:22
• Maybe you can edit your answer to clarify that. The OP might not know how to do such a transformation mathematically. Aug 29, 2020 at 6:24