Circle Line-Segment Collision Detection Algorithm

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, $C$ , with the center $O$ , and radius $R$ . We also have a line, $L$ , that’s described by two points, $P$ and $Q$ . Now we want to check if the circle $C$ and the line $L$ collide at any points or not.

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

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

In contrast, in figure B, the given line $L$ intersects with the given circle $C$ at two points. Thus, the answer is $true$ (circle $C$ and line $L$ 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 $L$ . 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:

As we can see, the minimum distance between the circle’s origin $O$ and the given line $L$ that’s described by two points, $P$ and $Q$ , 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 $(A, B, C)$ 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 $(O, P, Q)$ , we can get $\mathbf{height = \frac{2 \times TriangleArea(O, P, Q) }{base}}$ , which represents the minimum distance from the circle’s origin $O$ to the nearest point that also lies on the given line $L$ .

Finally, if the calculated height is less than or equal to the circle’s radius, then the circle collides with the given line $L$ . 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:

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, $A$ , $B$ , and $C$ , which will represent the coordinate of the vertices of the triangle.

First, we get two vectors, $AB$ and $AC$ , 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:

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), $O$ (the origin of the circle), $P$ and $Q$ (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 $O$ and the nearest points to $O$ that also lie on the given line $L$ . 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 $distance(P, Q)$ is the Euclidean distance between points $P$ and $Q$ .

Finally, if the minimum distance is less than or equal to the circle’s radius, then the circle collides with the given line $L$ . 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 $90$ degrees.
So, if the dot-product between the vectors $OP$ and $QP$ is more significant than zero, and the dot-product between the vectors $OQ$ and $PQ$ 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 $distance(O, P)$ and $distance(O, Q)$ , where the $distance$ function returns the Euclidean distance between two points.
(Recall that the Euclidean distance between points $A$ and $B$ 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 $C$ and the given line segment $PQ$ do collide. Otherwise, they don’t.

4.2. Algorithm

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

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), $O$ (the origin of the given circle), $P$ and $Q$ (the endpoints of the given line segment).

First, we declare $min \_ dist$ , representing the minimum distance between the given circle’s origin $O$ and the nearest points to $O$ that also lie on the given line segment $PQ$ . 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 $PQ$ . Otherwise, it’ll be equal to the minimum Euclidean distance between the origin $O$ and one of the endpoints, $P$ or $Q$ .

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

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 $C$ and the given line segment $PQ$ 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.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex