# Line Segment to Circle Collision/Intersection Detection :: 13 Jul 2009

## Style and Notation

• All variables are represented in italics except in the diagrams and Python code.
• Vectors are shown in bold except in the diagrams and Python code.
•  The notation a is used to represent the length of a vector named a.

## Introduction to the problem

Start by defining a few points (vectors from the world origin):

Now, from these points, you can easily calculate two useful values, the segment vector, seg_v (from seg_a to seg_b) and the position of circ_pos relative to seg_a, pt_v.

seg_v = seg_b - seg_a

pt_v = circ_pos - seg_a

## Closest point to the circle’s center on the segment

The next step is to find the closest point to the circle’s center on the segment (labeled “closest” on the diagram). To do this, we must project pt_v onto seg_v:

To project on vector onto another, take the dot product of the vector and the unit vector of the projection target. That is:

Note that this dot product returns a scalar value (the length of proj_v), not a vector.

 We now need to take a small break from the main goal and look into a special case: the ends of the segment. If proj_v is less than 0 or greater than seg_v , the closest point to circ_pos on the segment will be one of the segment’s endpoints. That is:
if |proj_v| < 0:
closest = seg_a
if |proj_v| > |seg_v|:
closest = seg_b


 Next, calculate the actual proj_v vector, rather than just its length ( proj_v ). To do this, simply multiply by the seg_v unit vector:

The only thing left to do is to convert this into world coordinates (rather than coordinates relative to seg_a) to get the closest point:

closest = seg_a + proj_v

## Checking for a intersection

Now that we’ve calculated the closest point on the segment (the variable “closest”), we can check if the circle and segment intersect. To do this, first find the vector from closest to circ_pos:

dist_v = circ_pos - closest

If the length of this vector is less than the circle’s radius, the circle and segment are intersecting:

if |dist_v| < circ_rad:
They are intersecting
else:
They are not intersecting


## Collision response

 A useful bit of data in collision response is the amount of overlap between two shapes and the direction a shape must be moved in order to resolve the collision. This can be represented as a vector that points in the same direction as dist_v whose length is equal to the difference between circ_rad and dist_v .

## Python implementation

Here is a Python implementation of everything in this post. For the sake of clarity, I avoided optimizations. vec is assumed to be a fully implemented 2d vector class:

def closest_point_on_seg(seg_a, seg_b, circ_pos):
seg_v = seg_b - seg_a
pt_v = circ_pos - seg_a
if seg_v.len() <= 0:
raise ValueError, "Invalid segment length"
seg_v_unit = seg_v / seg_v.len()
proj = pt_v.dot(seg_v_unit)
if proj <= 0:
return seg_a.copy()
if proj >= seg_v.len():
return seg_b.copy()
proj_v = seg_v_unit * proj
closest = proj_v + seg_a
return closest

closest = closest_point_on_seg(seg_a, seg_b, circ_pos)
dist_v = circ_pos - closest
return vec(0, 0)
if dist_v.len() <= 0:
raise ValueError, "Circle's center is exactly on segment"
offset = dist_v / dist_v.len() * (circ_rad - dist_v.len())
return offset


## Similar algorithms

Collisions involving stadiums (a type of rounded rectangle) can be calculated in a similar manner. A stadium is essentially a line segment with a radius.