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

```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
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