4.000.000 Rectangle Collisions Per Second

However easy rectangle-collision-detection may look like, it is not. Well, before your rectangles got rotated, all you have to do is to measure points intersection on x and y axis, but once they got rotated you have to rethink the whole algorithm. After reading an article N Tutorial A – Collision Detection and Response, I got inspired and soon Math2D and FastCollisions were born.

What you have to do is to construct a new axis based on rectangle rotation. What first looked like x and y axis, now results into 2 axises per each rectangle (4 in total). First is the one that joins points 1 and 2, second that joins points 2 and 3 (see the final .swf to understand). Once you have 4 new axises you have to project points from other rectangle into the each axis and test intersection.

Lets start with crating axis and projecting point into the axis. For this purpose I created Math2D class functions projectX() and projectY()

var b1:Point; // any point on axis
var b2:Point; // any other point on axis
var p:Point; // point we want to project on axis
var x:Number = Math2D.projectX(b1.x, b1.y, b2.x, b2.y, p.x, p.y);
var y:Number = Math2D.projectY(b1.x, b1.y, b2.x, b2.y, p.x, p.y);
// result is a point projected on axis

Projecting to Axis – wonderfl build flash online

Next thing is to project all rectangle points into the axis and test intersections

var b1:Point; // any point on axis
var b2:Point; // any other point on axis
var r2p1:Point, r2p2:Point, r2p3:Point, r2p4:Point // rectngle corners (raw values, not projected to axis!)
var collision:Boolean = Math2D.isProjectedAxisCollision(
    b1.x, b1.y, b2.x, b2.y,
    r2p1.x, r2p1.y, r2p2.x, r2p2.y, 
    r2p3.x, r2p3.y, r2p4.x, r2p4.y);

Rectangle Intersection with Axis – wonderfl build flash online

We can now test intersections on our all 4 axis and if all results in collision, we have rectangle collision. In order to speed up the whole testing I extracted from Math2D and created class FastCollisions. FastCollisions contains optimized math from Math2D functions.

var r1p1:Point, r1p2:Point, r1p3:Point, r1p4:Point // rectangle 1 corners
var r2p1:Point, r2p2:Point, r2p3:Point, r2p4:Point // rectangle 2 corners
var collision:Boolean = FastCollisions.rectangles(
    r1p1.x, r1p1.y, r1p2.x, r1p2.y, r1p3.x, r1p3.y, r1p4.x, r1p4.y, 
    r2p1.x, r2p1.y, r2p2.x, r2p2.y, r2p3.x, r2p3.y, r2p4.x, r2p4.y);

It is important to insert rectangle corner points in correct order!

1 --- 2
|     |
4 --- 3

Click flash to see the speed (collision tests per second). Results may differ based on when the first short circuit (no colliding axis) appears. 4.000.000 – 1.200.000 per second on my PC (2GHz dual core).

Rectangle Collisions – wonderfl build flash online

2 comments so far

  1. Art June 5, 2011 09:46

    Thanks a lot! This is the best and quickest method we tried!

  2. Lex August 15, 2013 14:50

    Fantastic! Beautiful code … Thank you

Leave a comment

Please be polite and on topic. Your e-mail will never be published.