圆与线段碰撞检测算法

1. Overview

In this tutorial, we’ll discuss how to detect collisions between a circle and a line or line segment.

First, we’ll define the problem and demonstrate it with an example. Then we’ll present two approaches to solving this problem. The first approach is to detect collisions between a line and a circle, and the second is to detect collisions between a line segment and a circle.

2. Defining the Problem

Here we have a circle, , with the center , and radius . We also have a line, , that’s described by two points, and . Now we want to check if the circle and the line collide at any points or not.

To better understand this, let’s take a look at an example:

1 1536x880

In figure A, the given line doesn’t intersect with the circle at any point; therefore, the answer is false (circle and line don’t collide).

In contrast, in figure B, the given line intersects with the given circle at two points. Thus, the answer is true (circle and line collide).

3. Line & Circle Intersection

3.1. Mathematical Idea

The main idea of this approach is to get the minimum distance between the circle’s origin and the nearest point to the circle’s origin that also lies on the line . If that distance is less than or equal to the circle’s radius, then a part of the line lies inside the circle or touches it, and therefore, the line collides with the circle. Otherwise, it doesn’t.

Initially, the nearest point to the circle’s origin that also lies on the given line is the projection of the circle’s origin onto the given line. We can imagine the desired distance as the height of the triangle (O, P, Q) . Let’s take a look at the following illustration:

2 1536x1244

As we can see, the minimum distance between the circle’s origin and the given line that’s described by two points, and , is equal to the height of the triangle (O, P, Q) . Furthermore, to get the height of this triangle, we have the advantage of calculating the area of the triangle. (Recall that the triangle’s area is equal to $\mathbf{\frac{base \times height}{2}}$ ).

We can also get the area of a triangle from the coordinates of its vertices using the cross product. (Recall that the triangle described by points has an area equal to $\mathbf{ \frac{|CrossProduct(B - A, C - A)|}{2} }$ ).

By using these two methods to calculate the area of the triangle , we can get $\mathbf{height = \frac{2 \times TriangleArea(O, P, Q) }{base}}$ , which represents the minimum distance from the circle’s origin to the nearest point that also lies on the given line .

Finally, if the calculated height is less than or equal to the circle’s radius, then the circle collides with the given line . Otherwise, it doesn’t.

3.2. Triangle Area

Now let’s take a look at the algorithm to get the triangle’s area using cross-product:

algorithm TriangleArea(A, B, C):
    // INPUT
    //    A = the first vertex of the triangle (A.x, A.y)
    //    B = the second vertex of the triangle (B.x, B.y)
    //    C = the third vertex of the triangle (C.x, C.y)
    // OUTPUT
    //    the area of the triangle described by vertices A, B, and C

    AB <- Vector(B.x - A.x, B.y - A.y)
    AC <- Vector(C.x - A.x, C.y - A.y)
    cross_product <- AB.x * AC.y - AB.y * AC.x

    return |cross_product| / 2

Initially, we define the TriangleArea function that will return the area of a triangle described by three points. Furthermore, the function will have three parameters, , , and , which will represent the coordinate of the vertices of the triangle.

First, we get two vectors, and , by subtracting the coordinate of the start point from the endpoint of the vector. Then we multiply these two vectors using any of the two cross-product formulas.

Finally, the area of the triangle (A, B, C) will be equal to the absolute value of the cross-product divided by two.

3.3. Algorithm

Then, we’ll take a look at the implementation of the algorithm:

algorithm LineCircleCollision(radius, O, P, Q):
    // INPUT
    //    radius = the radius of the circle
    //    O = the origin of the circle
    //    P = a point on the line
    //    Q = another point on the line
    // OUTPUT
    //    Returns true if the circle collides with the line.
    //    Otherwise, returns false.

    minimum_distance <- (2 * TriangleArea(O, P, Q)) / distance(P, Q)

    if minimum_distance <= radius:
        return true
    else:
        return false

Initially, we define the Collision function that will return whether the given circle collides with the given line or not. Furthermore, the function will have four parameters: radius (the radius of the circle), (the origin of the circle), and (which will be any two points that lie on the given line).

First, we declare $minimum \_ distance$ , representing the minimum distance between the given circle’s origin and the nearest points to that also lie on the given line . That $minimum \_ distance$ will be equal to the height of the triangle (O, P, Q) , and we can calculate it using the formula $\frac{2 \times TriangleArea(O, P, Q)}{distance(P, Q)}$ , where is the Euclidean distance between points and .

Finally, if the minimum distance is less than or equal to the circle’s radius, then the circle collides with the given line . Therefore, we return true. Otherwise, it doesn’t, and we return false.

3.4. Complexity

The time complexity of this algorithm is $\mathbf{O(1)}$ . This is because we’re doing a constant number of arithmetic operations.

4. Line Segment & Circle Intersection

4.1. Mathematical Idea

In this approach, we’ll use the same idea as the previous approach; however, we also need to check that the entire line segment doesn’t lie inside the given circle. Therefore, we’ll get the farthest point from the circle’s origin that lies on the given line segment, and check if it lies outside the given circle.

The nearest point to the circle’s origin that also lies on the given line segment isn’t necessarily equal to the projection of the circle’s origin of the line that has the line segment. This is because the projection of the origin might be out of the line segment boundary. In this situation, we have two options to get the desired nearest point:

We can check if the projection of the circle’s origin lies on the given line segment by using the dot-product. One of the dot-product features between two vectors is that it provides a result greater than zero if the angle between the given vectors is less than degrees.
So, if the dot-product between the vectors and is more significant than zero, and the dot-product between the vectors and is more important than zero, it means the circle’s origin projection lies on the given line segment. As a result, we get the minimum distance as the previous approach.
If the projection of the circle’s origin doesn’t lie on the given line segment, it means that the desired nearest point is one of the endpoints of the line segment. In this case, we can get the minimum distance by taking the minimum between the and , where the function returns the Euclidean distance between two points.
(Recall that the Euclidean distance between points and is equal to $\mathbf{ \sqrt{(A.x - B.x)^2 + (A.y - B.y)^2} }$ ).

Next, the maximum distance between the circle’s origin and the line segment is equal to the distance between the circle’s origin and the farthest point to the circle’s origin that should be one of the endpoints of the given line segment. We can get the maximum distance by taking the maximum between the distance(O, P) and distance(O, Q) .

Finally, if the minimum distance is less than or equal to the circle’s radius, and the maximum distance is greater than or equal to the circle’s radius, then the given circle and the given line segment do collide. Otherwise, they don’t.

4.2. Algorithm

Now, let’s take a look at the implementation of the algorithm:

algorithm LineSegmentCircleCollision(radius, O, P, Q):
    // INPUT
    //    radius = the radius of the circle
    //    O = the origin of the circle
    //    P = one endpoint of the line segment
    //    Q = the other endpoint of the line segment
    // OUTPUT
    //    Returns true if the circle collides with the line.
    //    Otherwise, returns false.

    min_dist <- infinity
    max_dist <- MAX(distance(O, P), distance(O, Q))

    if Dot(OP, QP) > 0 and Dot(OQ, PQ) > 0:
        min_dist <- 2 * TriangleArea(O, P, Q) / distance(P, Q)
    else:
        min_dist <- MIN(distance(O, P), distance(O, Q))

    if min_dist <= radius and max_dist >= radius:
        return true
    else:
        return false

Initially, we define the Collision function that returns whether the given circle collides with the given line segment or not. Furthermore, the function will have four parameters: radius (the radius of the given circle), (the origin of the given circle), and (the endpoints of the given line segment).

First, we declare $min \_ dist$ , representing the minimum distance between the given circle’s origin and the nearest points to that also lie on the given line segment . That $min \_ dist$ will be equal to the height of the triangle (O, P, Q) if the projection of the circle’s origin lies on the segment . Otherwise, it’ll be equal to the minimum Euclidean distance between the origin and one of the endpoints, or .

Then we have the $max \_ dist$ equal to the maximum Euclidean distance between the origin and one of the endpoints, or .

Finally, if the $min \_ dist$ is less than or equal to radius , and the $max \_ dist$ is greater than or equal to radius , then the given circle and the given line segment do collide, and we return true. Otherwise, they don’t, and we return false.

4.3. Complexity

The time complexity of this algorithm is $\mathbf{O(1)}$ . This is because we’re doing a constant number of arithmetic operations.

5. Conclusion

In this article, we learned how to detect collisions between a circle and a line or line segment.

First, we provided an example to explain the problem. Then we explored two approaches to solving it. The first approach was between a line and a circle, and the second was between a line segment and a circle.

Finally, we walked through the implementations and explained the time complexity for each algorithm.

Persistence

REST

Security