如何检测两个非轴对齐矩形的碰撞？含单矩形旋转场景

Great question! Making the jump from axis-aligned bounding boxes (AABBs) to rotated rectangles does add some complexity, but there are tried-and-true methods to handle this reliably. Let’s break this down into two scenarios: one rotated rectangle vs. one axis-aligned, and then the fully general case of two rotated rectangles.

Scenario 1: One Rotated Rectangle, One Axis-Aligned (AABB) #

The easiest way to handle this is a simplified version of the Separating Axis Theorem (SAT)—the same core idea used for general convex polygon collision, but with fewer axes to check.

Here’s how it works:

• First, gather all key data:
  • For the AABB: Store its min/max x and y values (e.g., x_min, x_max, y_min, y_max).
  • For the rotated rectangle: Calculate its four vertex coordinates using its center position, width/height, and rotation angle. (I’ll share a quick formula for this later.)
• Check four potential separating axes:
  1. The AABB’s x-axis (vector (1, 0)).
  2. The AABB’s y-axis (vector (0, 1)).
  3. The rotated rectangle’s first edge normal (perpendicular to one of its sides).
  4. The rotated rectangle’s second edge normal (perpendicular to its adjacent side).
• For each axis, project all vertices of both rectangles onto the axis, creating two interval ranges. If any axis has non-overlapping intervals, the rectangles don’t collide. If all intervals overlap, they do collide.

Quick Vertex Calculation for Rotated Rectangles #

If you have a rectangle centered at (xc, yc) with width w, height h, and rotation angle theta (in radians), compute its four vertices like this:

import math

hw = w / 2
hh = h / 2
# Unrotated local vertices relative to center
local_verts = [(-hw, -hh), (hw, -hh), (hw, hh), (-hw, hh)]
rotated_verts = []
for (x, y) in local_verts:
    x_rot = (x * math.cos(theta)) - (y * math.sin(theta)) + xc
    y_rot = (x * math.sin(theta)) + (y * math.cos(theta)) + yc
    rotated_verts.append((x_rot, y_rot))

Scenario 2: General Case – Two Rotated Rectangles #

This is where the full Separating Axis Theorem (SAT) shines. SAT is the gold standard for convex polygon collision, and since rectangles are convex, it works perfectly here.

The core rule of SAT:

If two convex polygons do NOT collide, there exists at least one axis (perpendicular to any edge of either polygon) where their projections do not overlap.

For two rectangles, we only need to check 4 unique axes (each rectangle has two distinct edge normals—since opposite sides share the same normal):

1. Edge normal from rectangle 1’s first side.
2. Edge normal from rectangle 1’s second side.
3. Edge normal from rectangle 2’s first side.
4. Edge normal from rectangle 2’s second side.

Step-by-Step Implementation #

1. Extract edge normals: For each rectangle, take an edge vector (e.g., between vertex 0 and 1), then compute its perpendicular normal. For edge vector (dx, dy), the normal is (-dy, dx) (or (dy, -dx)—direction doesn’t matter for projection checks).
2. Project vertices onto each axis: For every axis, calculate the min and max projection values for both rectangles. Projection of a vertex (x,y) onto axis (ax, ay) is x*ax + y*ay.
3. Check interval overlap: For each axis, if the two projection intervals don’t overlap, return False (no collision). If all axes have overlapping intervals, return True (collision).

Example Code Snippet #

Here’s a simplified Python implementation to illustrate:

def project_vertices(vertices, axis):
    min_proj = float('inf')
    max_proj = -float('inf')
    for (x, y) in vertices:
        proj = x * axis[0] + y * axis[1]
        min_proj = min(min_proj, proj)
        max_proj = max(max_proj, proj)
    return (min_proj, max_proj)

def intervals_overlap(a_min, a_max, b_min, b_max):
    # Handle floating point precision with a small epsilon if needed
    epsilon = 1e-6
    return not (a_max + epsilon < b_min or b_max + epsilon < a_min)

def get_rect_normals(rect_vertices):
    # Get the two unique edge normals for a rectangle
    edge1 = (rect_vertices[1][0] - rect_vertices[0][0], rect_vertices[1][1] - rect_vertices[0][1])
    normal1 = (-edge1[1], edge1[0])
    edge2 = (rect_vertices[2][0] - rect_vertices[1][0], rect_vertices[2][1] - rect_vertices[1][1])
    normal2 = (-edge2[1], edge2[0])
    return [normal1, normal2]

def check_rotated_rect_collision(rect1_verts, rect2_verts):
    axes = get_rect_normals(rect1_verts) + get_rect_normals(rect2_verts)
    for axis in axes:
        a_min, a_max = project_vertices(rect1_verts, axis)
        b_min, b_max = project_vertices(rect2_verts, axis)
        if not intervals_overlap(a_min, a_max, b_min, b_max):
            return False
    return True

Key Notes #

• Floating Point Precision: Always use a small epsilon value when checking interval overlap to avoid false negatives from tiny calculation errors.
• Early Exit: As soon as you find an axis with non-overlapping projections, you can stop checking further axes—this saves computation time.
• SAT Limitation: Remember, SAT only works for convex shapes. Luckily, rectangles are always convex, so this isn’t an issue here.

内容的提问来源于stack exchange，提问作者Meta Xenology