Add a collision detection algorithm

Feature description

In the physics section, you can add an algorithm that allows you to detect collisions of different types of primitives. This will be useful when creating games, etc.

Axis-Aligned Bounding Box (AABB) Collision Detection
An AABB is a rectangle whose edges are aligned with the coordinate axes. Collision detection between two AABBs is relatively straightforward:

Define Boundaries: Each rectangle is defined by its minimum and maximum x and y coordinates (or alternatively, by its top-left corner and width/height).

Check for Overlap: For two rectangles to collide, they must overlap in both the x and y axes. This can be checked with simple comparisons.

The conditions for two AABBs to intersect can be expressed as:

Rect1.x < Rect2.x + Rect2.width

Rect1.x + Rect1.width > Rect2.x

Rect1.y < Rect2.y + Rect2.height

Rect1.y + Rect1.height > Rect2.y

If all these conditions are true, the rectangles intersect.

function isColliding(rect1, rect2) {
return (
rect1.x < rect2.x + rect2.width &&
rect1.x + rect1.width > rect2.x &&
rect1.y < rect2.y + rect2.height &&
rect1.y + rect1.height > rect2.y
);
}

const rectA = { x: 10, y: 20, width: 50, height: 50 };
const rectB = { x: 40, y: 50, width: 50, height: 50 };

console.log(isColliding(rectA, rectB)); // becomes true if they overlap

this is just an snippet for an example

1️⃣ AABB (Axis-Aligned Bounding Box):

def check_aabb(rect1, rect2): # [(x,y,w,h), ...]
return not (rect1+rect1 < rect2 or
rect2+rect2 < rect1 or
rect1+rect1 < rect2 or
rect2+rect2 < rect1)

Best for simple rectangles, O(1) time complexity

2️⃣ Circle Collision:

import math
def circle_collision(c1, c2): # [(x,y,r), ...]
dx = c2 - c1
dy = c2 - c1
return math.sqrt(dx2 + dy2) <= (c1 + c2)

Distance-based check, accurate for circular shapes

Need further tweaks? Happy to refine!

Collision Detection Algorithm

Feature Description

In the physics section, you can add an algorithm that allows you to detect collisions of different types of primitives. This will be useful in creating games, etc.

The Collision Detection Algorithm for Different Primitives

Below, I've given an implementation of a collision detection algorithm that includes axis-aligned bounding boxes (AABB) and circles.

import math

class AABB:
    def __init__(self, x, y, width, height):
        self.x = x
        self.y = y
        self.width = width
        self.height = height

class Circle:
    def __init__(self, x, y, radius):
        self.x = x
        self.y = y
        self.radius = radius

def check_aabb_collision(box1, box2):
    """Check if two axis-aligned bounding boxes (AABB) collide."""
    if (box1.x < box2.x + box2.width and
        box1.x + box1.width > box2.x and
        box1.y < box2.y + box2.height and
        box1.y + box1.height > box2.y):
        return True
    return False

def check_circle_collision(circle1, circle2):
    """Check if two circles collide."""
    distance = math.sqrt((circle1.x - circle2.x) ** 2 + (circle1.y - circle2.y) ** 2)
    return distance < (circle1.radius + circle2.radius)

def check_aabb_circle_collision(box, circle):
    """Check if an AABB and a circle collide."""
    closest_x = clamp(circle.x, box.x, box.x + box.width)
    closest_y = clamp(circle.y, box.y, box.y + box.height)
    distance_x = circle.x - closest_x
    distance_y = circle.y - closest_y
    distance_squared = distance_x ** 2 + distance_y ** 2
    return distance_squared < (circle.radius ** 2)

def clamp(value, min_value, max_value):
    return max(min_value, min(value, max_value))

# Example in usage
if __name__ == "__main__":
    box1 = AABB(0, 0, 10, 10)
    box2 = AABB(5, 5, 10, 10)
    box3 = AABB(20, 20, 5, 5)

    circle1 = Circle(5, 5, 3)
    circle2 = Circle(15, 15, 5)

    print(check_aabb_collision(box1, box2))  # Output: True
    print(check_aabb_collision(box1, box3))  # Output: False
    print(check_circle_collision(circle1, circle2))  # Output: False
    print(check_aabb_circle_collision(box1, circle1))  # Output: True

Separating Axis Theorem (SAT) for Convex Polygons

The Separating Axis Theorem (SAT) can be used to detect collisions between any two convex shapes. Here's an extended implementation:

import numpy as np

class Polygon:
    def __init__(self, vertices):
        self.vertices = vertices

def project_polygon(axis, polygon):
    dots = [np.dot(vertex, axis) for vertex in polygon.vertices]
    return min(dots), max(dots)

def overlap(proj1, proj2):
    return min(proj1[1], proj2[1]) >= max(proj1[0], proj2[0])

def get_axes(polygon):
    axes = []
    num_vertices = len(polygon.vertices)
    for i in range(num_vertices):
        p1 = polygon.vertices[i]
        p2 = polygon.vertices[(i + 1) % num_vertices]
        edge = p1 - p2
        normal = np.array([-edge[1], edge[0]])
        axes.append(normal / np.linalg.norm(normal))
    return axes

def check_polygon_collision(poly1, poly2):
    """Check if two convex polygons collide using the Separating Axis Theorem (SAT)."""
    axes1 = get_axes(poly1)
    axes2 = get_axes(poly2)
    
    for axis in axes1 + axes2:
        proj1 = project_polygon(axis, poly1)
        proj2 = project_polygon(axis, poly2)
        if not overlap(proj1, proj2):
            return False
    return True

# Example in usage
if __name__ == "__main__":
    poly1 = Polygon([np.array([0, 0]), np.array([2, 0]), np.array([2, 2]), np.array([0, 2])])
    poly2 = Polygon([np.array([1, 1]), np.array([3, 1]), np.array([3, 3]), np.array([1, 3])])
    poly3 = Polygon([np.array([3, 3]), np.array([5, 3]), np.array([5, 5]), np.array([3, 5])])

    print(check_polygon_collision(poly1, poly2))  # Output: True
    print(check_polygon_collision(poly1, poly3))  # Output: False

Summary

I have extended the collision detection implementation to include:

Axis-Aligned Bounding Boxes (AABB)
Circles
Convex polygons using the Separating Axis Theorem (SAT)

These algorithms, as exhibited above, can now be used to detect collisions between different types of primitives, which is useful for creating games and other applications that require physics simulations.

I'm Experienced when it come to data structures and algorithms. I cracked some leetCode problem in the past concerning collision detection.
I'm Confident I can pull this up.

Add collision detection algorithm (TheAlgorithms#12569)

https://github.com/TheAlgorithms/Python/blob/master/CONTRIBUTING.md#issues

If you are interested in resolving an open issue, simply make a pull request with your proposed fix. We do not assign issues in this repo so please do not ask for permission to work on an issue.

Do not create an issue to contribute an algorithm. Please submit a pull request instead.

Navigation Menu

Repository navigation

Add a collision detection algorithm #12569

Feature description

Collision Detection Algorithm

Feature Description

The Collision Detection Algorithm for Different Primitives

Separating Axis Theorem (SAT) for Convex Polygons

Summary

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Add a collision detection algorithm #12569

Description

Feature description

Activity

ayushh0406 commented on Feb 11, 2025

Rishiram20757 commented on Feb 12, 2025

1803053530 commented on Mar 7, 2025

joey-the-33rd commented on Mar 11, 2025

Collision Detection Algorithm

Feature Description

The Collision Detection Algorithm for Different Primitives

Separating Axis Theorem (SAT) for Convex Polygons

Summary

Adagedo commented on Jun 19, 2025

cclauss commented on Sep 6, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions