## 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

*to*

**seg_a***) and the position of*

**seg_b***relative to*

**circ_pos***,*

**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

*onto*

**pt_v***:*

**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:

$$|proj_v| = \mathbf{pt_v} \cdot \frac{\mathbf{seg_v}}{|seg_v|}$$

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

*unit vector:*

**seg_v**$$\mathbf{proj_v} = |proj_v| \frac{\mathbf{seg_v}}{|seg_v|}$$

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

*to*

**closest***:*

**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*|.

$$\mathbf{offset} = (circ_{rad} - |dist_v|) \frac{\mathbf{dist_v}}{|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
def segment_circle(seg_a, seg_b, circ_pos, circ_rad):
closest = closest_point_on_seg(seg_a, seg_b, circ_pos)
dist_v = circ_pos - closest
if dist_v.len() > circ_rad:
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.

A stadium-point collision is the same as a segment-circle collision with a circle whose radius is equal to the stadium's radius.

A stadium-circle collision is the same as a segment-circle collision with a circle whose radius is equal to the sum of the original circle's radius and the stadium's radius.

## Download

segment_circle.zip - An implementation in Python and Cython.

If you find this post useful or have any questions, please leave a comment.