如何检查线段是否与矩形相交？

1. Introduction

In this tutorial, we’ll show how to check if a line segment intersects a rectangle.

2. Intersection

Let’s say that the segment’s endpoints are U(x_u, y_u) and V(x_v, y_v) . Similarly, let A_1(x_1, y_1) , A_2(x_2, y_2) , A_3(x_3, y_3) , and A_4(x_4, y_4) be the rectangle’s corners.

We say that the segment intersects the rectangle A_1A_2A_3A_4 if has at least one common point with at least one rectangle’s side. For example:

Intersection examples

So, the idea is to check if intersects A_1A_2 , A_2A_3 , A_3A_4 , or A_4A_1 . If we find an intersection with any side, we don’t need to check the rest.

3. The Intersection of Two Segments

So, let’s see how we can check if intersects A_1A_2 . The steps will be the same for the three remaining sides.

If intersects A_1A_2 , there will be at least one point that belongs to both and A_1A_2 :

The intersection of A1A2 and UV

Focusing on the triangle UA_1Z and treating A_1 , A_2 , , , and as vectors directed from the origin, we see that the following must hold:

$[\begin{aligned} &Z = &A_1 + \alpha(A_2 - A_1) = U + \beta(V - U) \\ &\iff &\alpha(A_2 - A_1) + \beta (U - V) = U - A_1 \\ && \alpha, \beta \in [0, 1] \end{aligned}]$

The condition $\boldsymbol{\alpha, \beta \in [0, 1]}$ ensures that $\boldsymbol{Z}$ belongs to both segments.

3.1. Solving a Linear System

If A_1=(x_1, y_1) , A_2=(x_2, y_2) , U=(x_u, y_u) , and V=(x_v, y_v) , we get a system of two linear equations:

(1) $\begin{equation*} \alpha \begin{bmatrix}x_2 - x_1 \\ y_2 - y_1 \end{bmatrix} + \beta \begin{bmatrix}x_u - x_v \\ y_u - y_v \end{bmatrix} = \begin{bmatrix} x_u - x_1 \\ y_u - y_1 \end{bmatrix} \end{equation*}$

The next step is to solve it for $\alpha$ and $\beta$ .

3.2. Interpreting the Solution

If the system has no solution, doesn’t intersect .

If there’s a unique solution such that $\alpha \in [0, 1]$ and $\beta \in [0,1]$ , then they intersect at a single point .

If there’s more than one solution, we’ll get a range of values for $\alpha$ and $\beta$ . If the ranges include values from [0, 1] , and A_1A_2 coincide at least partially. In particular, if the ranges are completely inside [0, 1] , we have $UV \subseteq A_1A_2$ , $A_1A_2 \subseteq UV$ , or both.

3.3. Algorithm

Here’s our algorithm:

algorithm CheckIfLineSegmentIntersectsRectangle(UV, A1, A2, A3, A4):
    // INPUT
    //    UV = a line segment
    //    A1, A2, A3, A4 = the corners of the rectangle
    // OUTPUT
    //    Returns true if UV intersects A1A2A3A4; otherwise, returns false

    for XY in {A1A2, A2A3, A3A4, A4A1}:
        Formulate the system for UV and the side XY
        Solve the system
        if the system has a solution in [0, 1]^2:
            return true
    
    return false

So, we start with one side and check all the others iteratively until we either find an intersection or test all of them without success.

Since we deal with a fixed number of dimensions, solving systems takes O(1) time, so the complexity of the entire algorithm is also $\boldsymbol{O(1)}$ .

3.4. What if the Segment Is Inside the Rectangle?

We set out the problem and formulated our algorithm to test only if has a mutual point with the rectangle’s boundary.

On the other hand, if we want to cover the rectangle’s interior, we need to extend our algorithm. The already formulated pseudocode deals with all the cases except when lies inside the interior of A_1A_2A_3A_4 .

To handle it, we note that is inside the rectangle only if and are linear combinations of the rectangle’s directed non-parallel sides such that all the coefficients are between 0 and 1:

The segment inside the rectangle

We can take any two adjacent sides as the vectors as long as we direct them so that the interior points have positive coefficients.

To check that, we solve two linear systems we derive from:

$[U = \alpha_u (A_2 - A_1) + \beta_u (A_4 - A_1)]$

and

$[V = \alpha_v (A_2 - A_1) + \beta_v (A_4 - A_1)]$

If both have single solutions $(\alpha_u, \beta_u) \in [0, 1]^2$ and $(\alpha_v, \beta_v) \in [0, 1]^2$ , is in the interior of A_1A_2A_3A_4 .

4. Conclusion

In this article, we talked about how to check if a line segment intersects with a rectangle. We differentiated between two cases: in the first one, we considered if the segment intersects the rectangle’s boundary, and in the second one, the case where we covered the intersections with the interior as well.

Persistence

REST

Security