Intersection tutorial

This is going to be a brief tutorial on collision detection. Before we can dive in the intersection algorithms, let's look at some basic geometry operations.
Note that in examples involving rectangles, we will deal with several implementations because rectangles could be represented in a number of ways.

Left: box
Center: aabb
Right: rect

Box (center point with half-width/height extents)
One way to represent rectangles is as a center point (x, y) with half-width and half-height extents (hw, hh). This is very useful when programming games, because it's generally easier to work with the centers of collisions shapes. Also, it's easier to include rotation or other transformations to the rectangle when its origin is at the center.

AABB (left, top, right, bottom)
A second implementation treats rectangles as four numbers (l, t, r, b) where (l, t) is the top-left corner and (r, b) is the bottom-right corner.

Rect (top-left point with width/height extents)
The last example represent rectangles as a point (x, y) with width and height extents (w, h) where (x, y) is the top-left corner.

Nearest point

Given an arbitrary position (P) outside of a shape, we want to find the nearest point (P2) on that shape. If P is already inside the area of the shape, the algorithms return the original point P. The nearest point algorithms can be used to solve more complicated intersection tests.


Examples of the nearest point to a line segment, circle, rectangle and triangle
P: point
P2 nearest point

Nearest point on a segment

Given a line segment (x1, y1, x2, y2) we find the nearest point from position (px, py). The result is obtained using two dot products "cx*dx + cy*dy" and "dx*dx + dy*dy". One caveat is that if the segment is degenerate (has zero length) a division by zero will occur. That's why we need the check "if d == 0".
function point_on_segment(px, py, x1, y1, x2, y2)
  local cx, cy = px - x1, py - y1
  local dx, dy = x2 - x1, y2 - y1
  local d = (dx*dx + dy*dy)
  if d == 0 then
    return x1, y1
  end
  local u = (cx*dx + cy*dy)/d
  if u < 0 then
    u = 0
  elseif u > 1 then
    u = 1
  end
  return x1 + u*dx, y1 + u*dy
end
One modification could be to remove the two if/else statements "if u < 0" and "elaseif u > 1" and then the segment (x1, y1, x2, y2) will be treated as an infinite line.

Nearest point on a circle

Another common operation is finding the nearest point in the circle area from an arbitrary position (px, py). Note that the original point (px, py) is returned if it's already inside the circle.
local sqrt = math.sqrt
function point_on_circle(px, py, cx, cy, r)
  local dx, dy = px - cx, py - cy
  local d = sqrt(dx*dx + dy*dy)
  if d <= r then
    return px, py
  end
  return dx/d*r + cx, dy/d*r + cy
end

Nearest point on a rectangle

Given an arbitrary point (px, py) the following function finds the nearest point in the area of the rectangle.

Box (center point with half-width/height extents)
function point_on_box(px, py, x, y, hw, hh)
  local qx, qy = px - x, py - y
  if qx > hw then
    qx = hw
  elseif qx < -hw then
    qx = -hw
  end
  if qy > hh then
    qy = hh
  elseif qy < -hh then
    qy = -hh
  end
  return qx + x, qy + y
end
AABB (left, top, right, bottom)
function point_on_aabb(px, py, l, t, r, b)
  local qx, qy = px, py
  if qx < l then
    qx = l
  elseif qx > r then
    qx = r
  end
  if qy < t then
    qy = t
  elseif qy > b then
    qy = b
  end
  return qx, qy
end
Rect (top-left point with width/height extents)
function point_on_rect(px, py, l, t, w, h)
  local r, b = x + w, y + h
  local qx, qy = px, py
  if qx < x then
    qx = x
  elseif qx > r then
    qx = r
  end
  if qy < y then
    qy = y
  elseif qy > b then
    qy = b
  end
  return qx, qy
end
The code simply clamps the given point (px, py) to the extents of the rectangle. Note that the original point (px, py) is returned if it's already contained inside the rectangle.

Nearest point on a triangle

The following example finds the nearest point on a triangle using Barycentric coordinates.
local function dot(ax, ay, bx, by)
  return ax*bx + ay*by
end
function point_on_triangle(px, py, ax, ay, bx, by, cx, cy)
  local abx, aby = bx - ax, by - ay
  local acx, acy = cx - ax, cy - ay
  local apx, apy = px - ax, py - ay
  -- vertex region outside a
  local d1 = dot(abx, aby, apx, apy)
  local d2 = dot(acx, acy, apx, apy)
  if d1 <= 0 and d2 <= 0 then
    return ax, ay
  end
  -- vertex region outside b
  local bpx, bpy = px - bx, py - by
  local d3 = dot(abx, aby, bpx, bpy)
  local d4 = dot(acx, acy, bpx, bpy)
  if d3 >= 0 and d4 <= d3 then
    return bx, by
  end
  -- edge region ab
  local vc = d1*d4 - d3*d2
  if vc <= 0 and d1 >= 0 and d3 <= 0 then
    local v = d1/(d1 - d3)
    local qx = ax + abx*v
    local qy = ay + aby*v
    return qx, qy
  end
  -- vertex region outside c
  local cpx, cpy = px - cx, py - cy
  local d5 = dot(abx, aby, cpx, cpy)
  local d6 = dot(acx, acy, cpx, cpy)
  if d6 >= 0 and d5 <= d6 then
    return cx, cy
  end
  -- edge region ac
  local vb = d5*d2 - d1*d6
  if vb <= 0 and d2 >= 0 and d6 <= 0 then
    local w = d2/(d2 - d6)
    local qx = ax + acx*w
    local qy = ay + acy*w
    return qx, qy
  end
  -- edge region bc
  local va = d3*d6 - d5*d4
  if va <= 0 then
    local d43 = d4 - d3
    local d56 = d5 - d6
    if d43 >= 0 and d56 >= 0 then
      local w = d43/(d43 + d56)
      local qx = bx + (cx - bx)*w
      local qy = by + (cy - by)*w
      return qx, qy
    end
  end
  -- inside face region
  return px, py
end

Point in shape

Given an arbitrary point (px, py) we want to test if it lies inside the area of a given shape.

Point in circle

Testing if a point is inside a circle is a two-step algorithm. First, we subtract the given point from the center of the circle. Next, we compare the length of the resulting vector to the radius of the circle. As an optimization, we avoid math.sqrt by comparing the square length and the square radius (r^2 or r*r).

function point_in_circle(px, py, cx, cy, r)
  local dx, dy = px - cx, py - cy
  return dx*dx + dy*dy <= r*r
end

Point vs circle
P: point
P2: nearest point from P on the circle edge where P2 = C + s
C: circle center
d: vector from the center of the circle to point P where d = P - C. If the length of d is greater than the radius, point P is outside the circle
s: vector d clamped to the circle radius where s = normalize(d)*radius

Point in rectangle

Box (center point with half-width/height extents)
local abs = math.abs
function point_in_box(px, py, x, y, hw, hh)
  if abs(px - x) > hw then
    return false
  end
  if abs(py - y) > hh then
    return false
  end
  return true
end
AABB (left, top, right, bottom)
function point_in_aabb(px, py, l, t, r, b)
  if px < l or px > r then
    return false
  end
  if py < t or py > b then
    return false
  end
  return true
end
Rect (top-left point with width/height extents)
function point_in_rect(px, py, l, t, w, h)
  if px < l or px > l + w then
    return false
  end
  if py < t or py > t + h then
    return false
  end
  return true
end
Note that the second implementation (AABB) is the fastest code in terms of execution.

Point in triangle

The following example is based on the book Real-Time Collision Detection by Christer Ericson. It uses the cross product to check if a point is inside a triangle.
function point_in_triangle(px, py, x1, y1, x2, y2, x3, y3)
  local ax, ay = x1 - px, y1 - py
  local bx, by = x2 - px, y2 - py
  local ab = ax*by - ay*bx
  local cx, cy = x3 - px, y3 - py
  local bc = bx*cy - by*cx
  local sab = ab < 0
  if sab ~= (bc < 0) then
    return false
  end
  local ca = cx*ay - cy*ax
  return sab == (ca < 0)
end

Shape vs shape

Given two shapes, we want to find if they intersect. For performance reasons, functions that detect if two shapes are intersecting should be programmed to return "false" as soon as possible.

Segment vs segment

The following function checks if two line segments (x1, y1, x2, y2 and x3, y3, x4, y4) are intersecting. The code uses two cross product "dx2*dy3 - dy2*dx3" and "dx1*dy3 - dy1*dx3" divided by a determinant (d). Note that the first check "if d == 0" returns false when the segments are either collinear or degenerate.
function segment_vs_segment(x1, y1, x2, y2, x3, y3, x4, y4)
  local dx1, dy1 = x2 - x1, y2 - y1
  local dx2, dy2 = x4 - x3, y4 - y3
  local dx3, dy3 = x1 - x3, y1 - y3
  local d = dx1*dy2 - dy1*dx2
  if d == 0 then
    return false
  end
  local t1 = (dx2*dy3 - dy2*dx3)/d
  if t1 < 0 or t1 > 1 then
    return false
  end
  local t2 = (dx1*dy3 - dy1*dx3)/d
  if t2 < 0 or t2 > 1 then
    return false
  end
  return true
end
It is not difficult to extend the function to return the point of intersection. Just change the last line to: "return true, x1 + t1*dx1, y1 + t1*dy1"

Segment vs circle

Given the segment (x, y, x2, y2) we want to find if it intersect with a circle (cx, cy, r).
local function segment_vs_circle(x, y, x2, y2, cx, cy, cr)
  local qx, qy = point_on_segment(cx, cy, x, y, x2, y2)
  return point_in_circle(qx, qy, cx, cy, cr)
end

Circle vs circle

By adding the radii of the two circles, we can treat one of the circles as a point.

Circle vs circle
Black arrows: the first circle expanded with the radius of the second circle
C1: center of the first circle
C2: center of the second circle
d: vector from the center of the first circle to the center of the second circle where d = C2 - C1. The two circles cannot overlap if the length of d is greater than the sum of the radii.
s: separation vector where s = normalize(d)*(radius1 + radius2) - d

function circle_vs_circle(cx, cy, r, cx2, cy2, r2)
  return point_in_circle(cx, cy, cx2, cy2, r + r2)
end
The expanded version would be:
function circle_vs_circle(cx, cy, r, cx2, cy2, r2)
  local sradii = r + r2
  local dx, dy = px - cx, py - cy
  return dx*dx + dy*dy <= sradii*sradii
end

Circle vs rectangle

First, we find the nearest point on the rectangle to the circle center, then we compare the distance to the circle radius. Another way to describe the problem could be as "point_in_roundedrect" where the point is the circle center.

Rectangle vs circle
Black arrows: rectangle expanded to a rounded rectangle
C: circle center
R: rectangle center
P: nearest point from C to the edges of the rectangle
d: vector from the circle center (C) to the nearest edge of the rectangle where d = P - C
s: separation vector where s = normalize(d)*radius - d if the circle center (C) is outside the rectangle or s = normalize(d)*radius + d if the circle center (C) is inside the rectangle


Box (center point with half-width/height extents)
function circle_vs_box(cx, cy, cr, x, y, hw, hh)
  local qx, qy = point_on_box(cx, cy, x, y, hw, hh)
  return point_in_circle(qx, qy, cx, cy, cr)
end
Expanded version:
local abs = math.abs
local max = math.max
function circle_vs_box(cx, cy, cr, x, y, hw, hh)
  local dx = abs(x - cx)
  local dy = abs(y - cy)
  dx = max(dx - hw, 0)
  dy = max(dy - hh, 0)
  return dx*dx + dy*dy <= cr*cr
end
AABB (left, top, right, bottom)
function circle_vs_aabb(cx, cy, cr, l, t, r, b)
  local qx, qy = point_on_aabb(cx, cy, l, t, r, b)
  return point_in_circle(qx, qy, cx, cy, cr)
end
Expanded version:
function circle_vs_aabb(cx, cy, cr, l, t, r, b)
  local dx = cx
  if dx < l then
    dx = l
  elseif dx > r then
    dx = r
  end
  local dy = cy
  if dy < t then
    dy = t
  elseif dy > b then
    dy = b
  end
  dx = dx - cx
  dy = dy - cy
  return dx*dx + dy*dy <= cr*cr
end
Rect (top-left point with width/height extents)
function circle_vs_rect(cx, cy, cr, l, t, w, h)
  local qx, qy = point_on_rect(cx, cy, l, t, w, h)
  return point_in_circle(qx, qy, cx, cy, cr)
end
Expanded version:
local function clamp(n, min, max)
  if n < min then return min end
  if n > max then return max end
  return n
end
function circle_vs_rect(cx, cy, cr, l, t, w, h)
  local dx = clamp(cx, l, l + w) - cx
  local dy = clamp(cy, t, t + h) - cy
  return dx*dx + dy*dy <= cr*cr
end

Circle vs triangle

The meat of this approach is projecting the center of the circle to the edges of the triangle. Once we have found point P, the rest of the code becomes trivial.

Triangle vs circle
Black arrows: triangle expanded to a rounded triangle
C: center of the circle
P: nearest point from the center of the circle to the edges of the triangle
d: vector from the circle center to the nearest edge of the triangle, where d = P - C
s: separation vector where s = normalize(d)*radius - d if the circle center (C) is outside the triangle or s = normalize(d)*radius + d if the circle center (C) is inside the triangle
function triangle_vs_circle(ax, ay, bx, by, cx, cy, sx, sy, r)
  local qx, qy = point_on_triangle(sx, sy, ax, ay, bx, by, cx, cy)
  return point_in_circle(qx, qy, sx, sy, r)
end

Triangle vs triangle

Although quite inefficient, the following example shows us how to use the previously defined "segment_vs_segment" and "point_in_triangle" functions.
function triangle_vs_triangle(ax, ay, bx, by, cx, cy, a2x, a2y, b2x, b2y, c2x, c2y)
  -- edge vs edge
  if segment_vs_segment(ax, ay, bx, by, a2x, a2y, b2x, b2y) then return true end
  if segment_vs_segment(ax, ay, bx, by, b2x, b2y, c2x, c2y) then return true end
  if segment_vs_segment(ax, ay, bx, by, c2x, c2y, a2x, a2y) then return true end
  if segment_vs_segment(bx, by, cx, cy, a2x, a2y, b2x, b2y) then return true end
  if segment_vs_segment(bx, by, cx, cy, b2x, b2y, c2x, c2y) then return true end
  if segment_vs_segment(bx, by, cx, cy, c2x, c2y, a2x, a2y) then return true end
  if segment_vs_segment(cx, cy, ax, ay, a2x, a2y, b2x, b2y) then return true end
  if segment_vs_segment(cx, cy, ax, ay, b2x, b2y, c2x, c2y) then return true end
  if segment_vs_segment(cx, cy, ax, ay, c2x, c2y, a2x, a2y) then return true end
  -- triangle (a,b,c) inside (a2,b2,c2)
  if point_in_triangle(ax, ay, a2x, a2y, b2x, b2y, c2x, c2y) then return true end
  if point_in_triangle(bx, by, a2x, a2y, b2x, b2y, c2x, c2y) then return true end
  if point_in_triangle(cx, cy, a2x, a2y, b2x, b2y, c2x, c2y) then return true end
  -- triangle (a2,b2,c2) inside (a,b,c)
  if point_in_triangle(a2x, a2y, ax, ay, bx, by, cx, cy) then return true end
  if point_in_triangle(b2x, b2y, ax, ay, bx, by, cx, cy) then return true end
  if point_in_triangle(c2x, c2y, ax, ay, bx, by, cx, cy) then return true end
  return false
end

Rectangle vs rectangle

The rectangle vs rectangle test checks each axis and returns false if there cannot be an intersection.

Rectangle vs rectangle
Black arrows: the first rectangle expanded with the width and height extents of the second rectangle
R1: center of the first rectangle
R2: center of the second rectangle
dx, dy: x-axis and y-axis distances from the center of the first rectangle (R1) to the center of the second rectangle (R2) where dx = R2.x - R1.x and dy = R2.y - R1.y. The two rectangles cannot overlap if abs(dx) is greater than the sum of the half-width extents (hw + hw2) or if abs(dy) is greater than the sum of the half-height extents (hh + hh2).
sx, sy: x-axis and y-axis separation, where abs(sx) = hw + hw2 - abs(dx) and abs(sy) = hh + hh2 - abs(dy). To find the separation vector, the longer axis is ignored

Box (center point with half-width/height extents)
local abs = math.abs
function box_vs_box(x, y, hw, hh, x2, y2, hw2, hh2)
  if abs(x - x2) > hw + hw2 then
    return false
  end
  if abs(y - y2) > hh + hh2 then
    return false
  end
  return true
end
AABB (left, top, right, bottom)
function aabb_vs_aabb(l, t, r, b, l2, t2, r2, b2)
  if l > r2 or l2 > r then
    return false
  end
  if t > b2 or t2 > b then
    return false
  end
  return true
end
Rect (top-left point with width/height extents)
function rect_vs_rect(l, t, w, h, l2, t2, w2, h2)
  if l > l2 + w2 or l2 > l + w then
    return false
  end
  if t > t2 + h2 or t2 > t + h then
    return false
  end
  return true
end
Again, the second implementation (AABB) is the fastest although the parameters must be aligned so that: l < r and t < b and l2 < r2 and t2 < b2.

Nearest edge

Given an arbitrary position (P) inside a shape, we want to find its position on the nearest edge on that shape and possibly the face normal.

Nearest edge of a circle

function circle_normal(px, py, x, y, r)
  local dx = px - x
  local dy = py - y
  local d = math.sqrt(dx*dx + dy*dy)
  assert(d > 0, "more than one normal")
  return dx/d, dy/d
end

Nearest edge of a rectangle

function box_normal(px, py, x, y, hw, hh)
  local dx = px - x
  local dy = py - y
  local nx = 0
  local ny = 0
  if dx < 0 then
    nx = -1
  elseif dx > 0 then
    nx = 1
  end
  if dy < 0 then
    ny = -1
  elseif dy > 0 then
    ny = 1
  end
  if hw - dx*nx > hh - dy*ny then
    nx = 0
  else
    ny = 0
  end
  assert(nx ~= 0 or ny ~= 0, "more than one normal")
  return nx, ny
end


References:
Realtime Collision Detection by Christer Ericson
Path by Cosmin Apreutesei