Polygon Collision Detection

Detecting collisions for regular polygons is relatively simple.
A square will always have 4 sides, a pentagon will always have an internal angle of 108º and so on. Their shapes and properties are always the same, no matter their size or position.

But what if we're dealing with irregular polygons?
They can assume an infinite number of shapes, sides and angles. They're impossible to predict!

The first thing we need to learn is how we tell if a point is inside a polygon or not. There are several techniques, but I'm going to use the Jordan Curve Theorem.

This theorem basically says that a closed shape divides the space in an "inside" and an "outside" areas. And if a point is inside the shape, when you cast a ray it will always have an odd number of intersections with the shape's boundaries.
There is one exception however. If the point is inside, but the ray passes through exactly at one of the vertices, the number of intersections is even, not odd.

So if we have a point (p) and the list of points that define the polygon, the first thing we need to do is define a line that passes through the point. Personally I always define a vertical line, to make the next calculations easier.

x = p_x

The next thing we need to do is loop through the polygon points and find the equation of the line for each edge. Then we just need to replace the X with the value of the vertical line to find the intersection point of both lines (and check if it's within the edge's boundaries).

y = m p_x + b

But since we're dealing with a full line and not a semi-straight line passing through the point, we need to count the amount of intersections that are occurring below and above the point.

if ( y < p_y ){
     // The intersection is below the point
}

if ( y > p_y ){
     // The intersection is above the point
}

As for detecting the collision between 2 polygons, finding out if the vertices of one polygon is inside the other isn't enough, because it can be only the edges that are colliding.
So we need to loop between the vertices of both polygons, define the lines and find out if the they're intersecting each other, as it's explained here.

Read more...

Simple Line Collision Detection

It might not be obvious at first, but Line Intersections are actually very handy.
For example, you can use them to define complex polygon shapes (octagons, stars, etc) and from there calculate the collision between them!

But in order to determine where the lines collide with each other, we first need the equation of a straight line:

y = m x + b

m =  y₁ - y₂  
        x₁ - x₂

So to determine any given point of a line we need to know its slope (m) and its y-intercept (b). Then all we need to do is give a X coordinate to obtain the corresponding Y coordinate of the point.

As for determining if a point belongs to a line, all we need to do is to use the point's X coordinate and check if the resulting Y matches the point's.

There are 2 exceptions we have to keep in mind however, vertical and horizontal lines. These follow special equations, where b is a constant value:

x = b

y = b

Now unless 2 lines have the same slope (which makes them parallel), they will intersect at some point, even if it's far off in space.
So the first thing we need is the equation of both lines. Each has its own slope and y-intercept, but because we're trying to find the point they have in common, the X and Y coordinate is the same for both:

y = m₁ x + b₁
y = m₂ x + b₂

From there all we need to do is to replace the Y to make the equations equal to each other and find the X value. Then we just need to replace the X value in either of the equations to get the Y, like in this example.
Just in case it's ever needed, this is how the equation solved to X looks like (it doesn't work for vertical or horizontal lines though):

 x =   b₂ - b₁  
        m₁ - m₂

Now there's only one thing missing. The equations we've used so far stretch into infinity, but what happens when we're dealing with line segments?
The computer would say the red and green lines are colliding, even though we can see the green line ends before it touches the red one.

So once we have the intersection point, we need to find out if it's within the boundaries of both segments:

flag_line1 = false
flag_line2 = false

if ( ( P_x >= L1_x1 AND P_x <= L1_x2 ) OR ( P_x <= L1_x1 AND P_x >= L1_x2 ) OR
     ( P_y >= L1_y1 AND P_y <= L1_y2 ) OR ( P_y <= L1_y1 AND P_y >= L1_y2 ) ) {

     flag_line1 = true
}

if ( ( P_x >= L2_x1 AND P_x <= L2_x2 ) OR ( P_x <= L2_x1 AND P_x >= L2_x2 ) OR
     ( P_y >= L2_y1 AND P_y <= L2_y2 ) OR ( P_y <= L2_y1 AND P_y >= L2_y2 ) ) {

     flag_line2 = true
}

if (flag_line1 == true AND flag_line2 == true ) {

      // The line segments collide
}

Read more...

Simple Circle Collision Detection

Circle are pretty popular. From basketballs and billiard balls to bullseye targets and frisbees, there are plenty of games where circles play an important role.
But unless we're dealing with soap bubbles, we need a way to tell the computer when the circles are colliding.

If we take the Equation of the Circle (with "r" being the radius and "C" the center of the circle) we can easily determine if a point (P) is inside the circle:

( P_x - C_x )² + ( P_y - C_y )² <= r²

But if we want to detect the collision between 2 circles, it's more intuitive to calculate the distance between the centers (C1 and C2) first and then check if it's smaller than the sum of the radius (r1 and r2):

distance = √(( C2_x - C1_x)² + ( C2_y - C1_y)²)

if (  distance  <=  r1 + r2 ){
     // The circles are colliding
}

Read more...

Simple Rectangle Collision Detection

We use collision detection all the time. Grabbing a cup of coffee, scratching our nose, sitting on a chair... even when walking our body detects the presence of other objects and surfaces outside of its own.
For computers it's a bit different. They can't detect anything unless we tell them how.

(Unrotated) rectangle collision is one of the simplest ones. If any point (P) isn't between the coordinates of both axis of the rectangle (R), then it's not colliding:

if ( P_x >= R1_x  AND  P_x <= R2_x  AND
     P_y >= R1_y  AND  P_y <= R2_y){

     // The point is inside the rectangle
}
else{
     // The point is outside the rectangle
}

With 2 rectangles (R1 and R2) we need to check, on both axis, if the coordinates of the edges of the 1st rectangle is between the coordinates of the 2nd:

if ( R1_x2 > R2_x1 AND R1_x1 < R2_x2 AND
     R1_y2 > R2_y1 AND R1_y1 < R2_y2 ){

     // The rectangles collided
}

Read more...