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
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.
Conclusion
If you find this post useful or have any questions, please leave a comment.
