# Difference between revisions of "Physics:2D Physics Engine:Intersection Detection"

The following article is part of a series:

This wiki page is under construction!

## Intersection Detection versus Collision Detection

Before progressing any further I'd like to share the difference between intersection detection and collision detection. An intersection test will tell you if two shapes or objects are interpenetrating at a given time. On the other hand a collision test will tell you if two objects will collide over a period of time.

A common example of a wrongly-named collision detection algorithm is the case of two intersecting circles. The test is commonly described:

"Given two circles with a center at point P, with radius R, the circles are colliding if the sum of the radii are greater than the distance between the two circles."

This is actually an intersection test, because it tests if the two circles are intersecting at their given positions. If the circles were not intersecting, but were moving towards each other very quickly, then they would be colliding. However, this test will not tell us that.

Why is this important? It isn't, really. However, it is information that will keep you from wondering why someone's 'collision test' doesn't work at high speeds.

## Circle Intersection

Firstly, the most simple shape to detect intersections between is the circle. You can think of a circle as a point and a radius. All you have to do to check whether two circles are intersecting, is to check whether the distance between the centers is greater than the radius. If it is, the two circles aren't touching.

Here is a simple implementation written in Python

```import math

class Circle:
self.x = x
self.y = y

def circle_intersect(circleA, circleB): # returns true if circles are overlapping
dx = circleB.x - circleA.x # get change in x
dy = circleB.y - circleA.y # get change in y
dist = math.sqrt(dx * dx + dy * dy) # find distance between centers of circles
# if the distance between the centers of the circles is less than the combined
# radii, then the circles must be overlapping

## Separating Axis Theorem for Axis Aligned Rectangles

A lot of games don't need complicated collision systems to find out whether two rectangles are intersecting. The code to find this is quite simple

```class Vect:
def __init__(self, x=0, y=0):
self.x = x
self.y = y

class Rect(Vect):
def __init__(self, w=0, h=0, x=0, y=0):
self.x = x
self.y = y
self.w = w
self.h = h

def rectangle_ovlbool(a, b):
c1 = (a.x - a.w) < (b.x + b.w)
c2 = (a.x + a.w) > (b.x - b.w)
c3 = (a.y - a.h) < (b.y + b.h)
c4 = (a.y + a.h) > (b.y - b.h)
return c1 and c2 and c3 and c4```

A good explanation of how this works can be found here and a visual representation here.

## The Separating Axis Theorem

The Separating Axis Theorem (referred to as SAT from now on) is a method to quickly and efficiently decide whether or not two convex polygons intersect.

The SAT involves projecting the two polygons onto every axis of both polygons. If these projections intersect on all axes, then the polygons are intersecting. However, if any of the projections are not intersecting, the polygons are not intersecting.

### Procedure

Non-intersecting polygons
Intersecting polygons
1. Look at the pictures. They are much easier to understand.
2. For each edge vector of both polygons:
1. Determine the separating axis. To compute the separating axis:
1. Find the unit vector of the edge (vector of magnitude 1)
2. Find the normal (perpendicular) of that unit vector
2. For each polygon:
1. Find the dot product between each point in that polygon and the separating axis
2. The projection of that polygon onto the separating axis spans between the smallest of those projected points and the largest of them
3. If the projections do not intersect, stop. That means the polygons are not intersecting.
3. If step 2 was completed, the polygons must be intersecting.

### Implementation

The following code is written in Python, but should be readable for users of other languages as well. It may look daunting, but just take it step by step. You can probably skip over the Vector class (it's fairly standard), but it is included for completeness.

```import math
class Vector:
"""Basic vector implementation"""
def __init__(self, x, y):
self.x, self.y = x, y
def dot(self, other):
"""Returns the dot product of self and other (Vector)"""
return self.x*other.x + self.y*other.y
return Vector(self.x+other.x, self.y+other.y)
return Vector(-self.x, -self.y)
def __sub__(self, other): # overloads vec1-vec2
return -other + self
def __mul__(self, scalar): # overloads vec*scalar
return Vector(self.x*scalar, self.y*scalar)
__rmul__ = __mul__ # overloads scalar*vec
def __div__(self, scalar): # overloads vec/scalar
return 1.0/scalar * self
def magnitude(self):
return math.sqrt(self.x*self.x + self.y*self.y)
def normalize(self):
"""Returns this vector's unit vector (vector of
magnitude 1 in the same direction)"""
inverse_magnitude = 1.0/self.magnitude()
return Vector(self.x*inverse_magnitude, self.y*inverse_magnitude)
def perpendicular(self):
"""Returns a vector perpendicular to self"""
return Vector(-self.y, self.x)

class Projection:
"""A projection (1d line segment)"""
def __init__(self, min, max):
self.min, self.max = min, max
def intersects(self, other):
"""returns whether or not self and other intersect"""
return self.max > other.min and other.max > self.min

class Polygon:
def __init__(self, points):
"""points is a list of Vectors"""
self.points = points

# Build a list of the edge vectors
self.edges = []
for i in range(len(points)): # equal to Java's for(int i=0; i<points.length; i++)
point = points[i]
next_point = points[(i+1)%len(points)]
self.edges.append(next_point - point)
def project_to_axis(self, axis):
"""axis is the unit vector (vector of magnitude 1) to project the polygon onto"""
projected_points = []
for point in self.points:
# Project point onto axis using the dot operator
projected_points.append(point.dot(axis))
return Projection(min(projected_points), max(projected_points))
def intersects(self, other):
"""returns whether or not two polygons intersect"""
# Create a list of both polygons' edges
edges = []
edges.extend(self.edges)
edges.extend(other.edges)

for edge in edges:
axis = edge.normalize().perpendicular() # Create the separating axis (see diagrams)

# Project each to the axis
self_projection = self.project_to_axis(axis)
other_projection = other.project_to_axis(axis)

# If the projections don't intersect, the polygons don't intersect
if not self_projection.intersects(other_projection):
return False

# The projections intersect on all axes, so the polygons are intersecting
return True```

[a note from thebluedragont] If you want to move out of intersection straight away, add to your position the inverse of one of the intersection axes multiplied by one of the overlaps: -axis * overlap.

If you want to move in a logical way (if you hit a wall you don't suddenly want to go upwards, do you?), add only the smallest overlap you got with the inverse of its axis.

For example, if you do a check against two AABBs and you get that they are intersecting, see what the overlaps are (I do it by regarding each Projection struct as a circle and do a simple circle-circle overlap test). Say you got that the overlap on the X axis is 10 and the overlap on the Y axis is 13 - you need to move your object -10 units on the X axis.

I also suggest reading this article http://www.metanetsoftware.com/technique/tutorialA.html . It explains in great detail about SAT and some common shapes, but doesn't really talk much about HOW to actually do everything. Thereof, it wouldn't be complete without this page, and Gman's other page (which I honestly think is better then this one) http://gpwiki.org/index.php/VB:Tutorials:Building_A_Physics_Engine:Basic_Intersection_Detection which explains more about the "HOW to do it".