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