Moving Circles

Solution

You may be able to find the solution on the discussion forum.

2026 Update: Collision Detection — Computational Geometry

Moving circles (or objects) that may collide is a computational geometry problem with applications in games, robotics, and simulation. The key insight: two circles collide when the distance between centers equals the sum of radii.

import math

def circles_collide(c1_pos, c1_vel, c1_radius,
                    c2_pos, c2_vel, c2_radius,
                    max_time=10.0):
    """
    Determine if two moving circles collide and when.
    c1_pos = (x1, y1), c1_vel = (vx1, vy1), etc.
    Returns collision time or None.
    """
    # Relative position and velocity
    dx = c2_pos[0] - c1_pos[0]
    dy = c2_pos[1] - c1_pos[1]
    dvx = c2_vel[0] - c1_vel[0]
    dvy = c2_vel[1] - c1_vel[1]
    r_sum = c1_radius + c2_radius

    # Distance at time t: ||(dx + dvx*t, dy + dvy*t)||^2 = r_sum^2
    # Expand: (dvx^2 + dvy^2)t^2 + 2(dx*dvx + dy*dvy)t + (dx^2 + dy^2 - r_sum^2) = 0
    a = dvx**2 + dvy**2
    b = 2 * (dx * dvx + dy * dvy)
    c = dx**2 + dy**2 - r_sum**2

    if a == 0:  # Circles moving at same velocity
        return None if c > 0 else 0  # Already colliding or parallel

    discriminant = b**2 - 4*a*c
    if discriminant < 0:
        return None  # No collision

    t1 = (-b - math.sqrt(discriminant)) / (2 * a)
    t2 = (-b + math.sqrt(discriminant)) / (2 * a)

    # Return earliest positive collision time
    for t in sorted([t1, t2]):
        if 0 <= t <= max_time:
            return t
    return None


def sweep_and_prune_1d(circles_x, radii) -> list:
    """
    Broad-phase collision detection along 1D axis.
    Find potentially overlapping pairs (then do exact check).
    """
    events = []
    for i, (x, r) in enumerate(zip(circles_x, radii)):
        events.append((x - r, 'start', i))
        events.append((x + r, 'end', i))
    events.sort()

    active = set()
    pairs = []
    for _, event_type, idx in events:
        if event_type == 'start':
            for active_idx in active:
                pairs.append((active_idx, idx))  # Potential collision
            active.add(idx)
        else:
            active.discard(idx)
    return pairs

# Test
circles_x = [0, 3, 6, 9]
radii = [1.5, 1.5, 1.5, 1.5]
potential_pairs = sweep_and_prune_1d(circles_x, radii)
print(f"Potentially colliding pairs: {potential_pairs}")

Applications in tech: Collision detection powers game physics engines, robotics path planning, and protein folding simulations. The mathematical reduction (quadratic formula for collision time) generalizes to any two objects with linear motion. For real-time applications, the “sweep and prune” broad-phase culling reduces O(n²) exact checks to O(n log n) by pre-sorting along an axis.