A long time ago I find a great article about physics in 2D games from creators of N (Metanet) and want to implement all examples in JavaScript, since nobody have flash in their browser anymore

#Collisions

All platformer games need to handle collisions. To handle them games usually:

1. Get all nearest objects
2. Check collision with all of them

Step 1 can be implemented using a grid system (like in mario) or with QuadTree if we do not have a regular grid.

Let's focus on a step 2 and calculate all forces.

Velocity applied from some point to the collision plane would be split into parallel and perpendicular vectors, vectors would be multiplied to friction and bounce (correspondingly) to get the after collision velocity.

Here you can play with it:

var somePoint = new Point( 40, 40 );

var plane = [
    new Point( 10, h - 60 ),
    new Point( w - 10, h - 60 )
];

// You can drag all this points!
plane.forEach( p => movablePoints.push( p ) );
movablePoints.push( somePoint );

var frictionSlider = new Slider( {
    p1: new Point( 10, h - 30 ),
    p2: new Point( w - 10, h - 30 ),
    from: 0, to: 1, value: 0.5,
    color: 0x880000,
    label: 'friction'
} );

var bounceSlider = new Slider( {
    p1: new Point( 10, h - 10 ),
    p2: new Point( w - 10, h - 10 ),
    from: 0, to: 1, value: 0.5,
    color: 0x008800,
    label: 'bounce'
} );

move = function() {
    clear();

    // you can drag the plane (draw draggers)
    plane.forEach(p => circle( p.x, p.y, 2, 0x008800 ) );

    line( plane[ 0 ], plane[ 1 ], 0x000090 );

    var midPoint = plane[ 1 ].addClone( plane[ 0 ] ).div( 2 );
    arrow( somePoint, midPoint, 0xCC00AA, 5 );

    /* For projection — we need to be in a same coordinate system, 
       so we subtract the beginning of the plane from somePoint and planeEnd */	 
    
    var projection = somePoint.subClone( plane[ 0 ] )
        .projection( plane[ 1 ].subClone( plane[ 0 ] ) )
        .add( plane[ 0 ] );

    circle( somePoint.x, somePoint.y, 2, 0x008800 );
    arrow( somePoint, projection, 0x6677CC, 5 );

    // vector from projection point to midPoint (collision point)
    var projectionToMid = midPoint.subClone( projection );
    arrow( projection, projectionToMid.clone().absoluteAdd( -2 ).add( projection ), 0xCC0077, 5 );

    /* Friction slider have value in range [0, 1] with initial value 0.5
       By multiplying vector from projection point to collision point on `friction`
       we get the result friction Vector */
    var frictionVector = projectionToMid.clone().mul( frictionSlider.value );
    arrow( midPoint, frictionVector.addClone( midPoint ), 0xCC0077, 5 );

    // By multiplying the projectionVector on -bounce we get the bounce vector
    var bounceVector = somePoint.subClone( projection ).mul( bounceSlider.value );
    
    // Just add everything together and we get the result
    var endPoint = midPoint.addClone(frictionVector).add( bounceVector );	

    arrow( frictionVector.addClone( midPoint ), endPoint, 0x6677CC, 5 );
    arrow( midPoint, endPoint, 0xCC00AA, 5 );

    // draw sliders
    frictionSlider.draw();
    bounceSlider.draw();
};

Great paper by David Eberly describes how we can find collision of two convex shapes. The general idea is: if we can find any axis along which the projection of the two shapes does not overlap, then the shapes don't overlap.

#Separating Axis Theorem

The separating axis theorem tells us that, for two convex shapes if we can find an axis along which the projection of the two shapes does not overlap, then the shapes don't overlap.

Applying to the 2D – potential separating axes is perpendicular to one of the sides of each shape.

var points = [
  new Point( 50, 50 ),
  new Point( 150, 50 ),
  new Point( 200, 100 ),
  new Point( 40, 150 )
];

points.forEach( p => movablePoints.push( p ) );

move = function() {
  clear();

  points.forEach(p => circle( p.x, p.y, 2, 0x008800 ) );
  for(var i = 0, _i = points.length; i < _i; i++){
    var p1 = points[i], p2 = points[(i+1)%_i];
    line(p1, p2, 0xCC00AA);
    
    var center = p1.addClone(p2).div(2);
    var perpendicular = p1.subClone(p2).rotate(Math.PI/2).normalize();
    arrow(center, perpendicular.mulClone(30).add(center), 0x000090, 3);
    
    var p3 = center.addClone(p2.subClone(p1).normalize().mul(5));
    var squareSide = perpendicular.mulClone(5);
    line(p3, p3.addClone(squareSide), 0x000090);
    line(squareSide.addClone(center), p3.addClone(squareSide), 0x000090);    
  }
}

#Rectangle

Projection of a box to any axis is a segment. Center of this segment is a projection of the box center, and its half size is a sum of projections of two half width vectors xw and yw.

Drag the red point to rotate the axis.

var NAVY = 0x000090, PINK = 0xCC00AA,
    GREEN = 0x008800, BLUE = 0x0000CC,
    RED = 0xCC0000, GRAY = 0xDDDDDD;

// top byte is transparency:
// 0xE6 is 90%, 0xCC is 80%
var NAVY_FILL = 0xE6000090,
    GREEN_LINE = 0xCC008800,
    BLUE_LINE = 0xCC0000CC;
// transparent colors are mixed with it
px.background = 0xFFFFFF;

var box = Box( 120, 100, 40, 20 );
// drag the red point: the axis flies around
var handle = new Point( 200, 40 );
movablePoints.push( handle );

move = function() {
    clear();
    // the handle stays on a circle
    var dir = handle.subClone( box );
    dir.normalize();
    var onCircle = dir.mulClone( 90 ).add( box );
    // whole pixels only: drawing needs them
    handle.borrow( pix( onCircle ) );

    // axis: through the handle, along circle
    var axis = normal( dir );
    var far = axis.mulClone( 300 );
    line( pix( handle.subClone( far ) ),
        pix( handle.addClone( far ) ), GRAY );

    // where `p` falls on the axis
    var onAxis = function( p ) {
        var v = p.subClone( handle );
        var d = dot( v, axis );
        return pix( axis.mulClone( d ).add( handle ) );
    };

    // half widths look to the handle side
    var sx = handle.x < box.x ? -1 : 1;
    var sy = handle.y < box.y ? -1 : 1;
    var xw = box.xw.mulClone( sx );
    var yw = box.yw.mulClone( sy );
    var xEnd = box.addClone( xw );
    var yEnd = box.addClone( yw );

    // the full box: its two farthest corners
    var all = corners( box );
    var ends = extent( all, axis );
    var farthest = all.filter( function( c ) {
        var d = dot( c, axis );
        return ends.indexOf( d ) > -1;
    } );

    fillBox( box, NAVY, NAVY_FILL );

    [ xEnd, yEnd ].forEach( function( p ) {
        line( p, onAxis( p ), GREEN_LINE );
    } );
    farthest.forEach( function( p ) {
        line( p, onAxis( p ), BLUE_LINE );
    } );

    // heads stop 1px before the side
    var xHead = xw.clone().absoluteAdd( -1 );
    var yHead = yw.clone().absoluteAdd( -1 );
    arrow( box, xHead.add( box ), PINK, 3 );
    arrow( box, yHead.add( box ), PINK, 3 );

    // green: between the arrow ends on the axis
    ruler( handle, axis, dot( xEnd, axis ),
        dot( yEnd, axis ), GREEN, 5, 2 );
    // blue: the full box
    ruler( handle, axis, ends[ 0 ], ends[ 1 ],
        BLUE, -4, 2 );

    circle( handle.x, handle.y, 3, RED );
};

Blue line is a projection of the whole box: we need to project all corners and find the farthest ones. Green line is between projections of the two half width arrow ends (direction to the point). It is just two dot products, and it is always a half of the blue one. So for any box on any axis we know the size.

#Two boxes

Now we can check two boxes. Both of them are projected to each side, and on each side we have:

• blue — from the center of the blue box to its side which looks at the red box
• red — the same for the red box
• green — between the two centers
• arrow — how much they overlap

If blue + red is longer than green — boxes overlap on this axis and the arrow shows how much. If there is at least one axis without overlap — boxes do not collide and we can stop checking. In a game most of the objects are not colliding, so we would stop early very often.

If boxes overlap on all axes — they collide. The smallest arrow becomes red: it is the projection vector. Moving the box by it is the shortest way out.

For boxes which are aligned to the world axes (AABB) we need only x and y.

var RED = 0xCC0000, BLUE = 0x0000CC,
    GREEN = 0x008800, GRAY = 0xBBBBBB;

// top byte is transparency:
// 0xE6 is 90%, 0xCC is 80%
var RED_FILL = 0xE6CC0000,
    BLUE_FILL = 0xE60000CC,
    RED_LINE = 0xCCCC0000,
    BLUE_LINE = 0xCC0000CC;
// transparent colors are mixed with it
px.background = 0xFFFFFF;

var red = Box( 80, 75, 30, 20 );
var blue = Box( 150, 110, 25, 35 );

// x side is at the bottom, y on the right
var bottom = h - 30, right = w - 30;

// rows go away from the boxes
var onX = function( row, from, to, color ) {
    var y = bottom + row * 7;
    thickLine( from, y, to, y, color, 2 );
};
var onY = function( row, from, to, color ) {
    var x = right + row * 7;
    thickLine( x, from, x, to, color, 2 );
};

// red is top left, blue is bottom right
// b, r: centers of blue and red on one axis
// bh, rh: their half sizes
var check = function( b, r, bh, rh, draw ) {
    var blueEnd = b - bh;
    var redEnd = r + rh;

    draw( 0, b, blueEnd, BLUE );
    draw( 1, r, redEnd, RED );
    draw( 2, b, r, GREEN );

    return {
        overlap: redEnd - blueEnd,
        from: redEnd, to: blueEnd
    };
};

move = function() {
    clear();

    // corners which look at the other box
    var blueCorner = new Point(
        blue.x - blue.xw.x,
        blue.y - blue.yw.y );
    var redCorner = new Point(
        red.x + red.xw.x,
        red.y + red.yw.y );

    fillBox( blue, BLUE, BLUE_FILL );
    fillBox( red, RED, RED_FILL );

    // each line goes to the row of its box
    var project = function( p, row, color ) {
        var y = bottom + row * 7;
        var x = right + row * 7;
        line( p.x, p.y, p.x, y, color );
        line( p.x, p.y, x, p.y, color );
    };
    project( blue, 0, BLUE_LINE );
    project( blueCorner, 0, BLUE_LINE );
    project( red, 1, RED_LINE );
    project( redCorner, 1, RED_LINE );
    line( red, blue, GRAY );

    var x = check( blue.x, red.x,
        blue.xw.x, red.xw.x, onX );
    var y = check( blue.y, red.y,
        blue.yw.y, red.yw.y, onY );

    // collide: overlap on both axes
    var hitX = x.overlap > 0;
    var hitY = y.overlap > 0;
    var min = x.overlap < y.overlap ? x : y;
    var color = function( axis ) {
        var hit = hitX && hitY && axis === min;
        return hit ? RED : GRAY;
    };

    var ay = bottom + 21, ax = right + 21;
    hitX && arrow( x.from, ay, x.to, ay,
        color( x ), 3 );
    hitY && arrow( ax, y.from, ax, y.to,
        color( y ), 3 );
};

All next examples do the same, so I moved it to a function testAxes. It takes a list of axes with two segments on each and returns the purple vector.

#Triangles

N tiles have a lot of right triangles. Two sides of such triangle are parallel to x and y, so they give the same axes as the box. Only the hypotenuse adds one more axis — its normal. Tiles do not move, so it can be calculated once.

var box = Box( 110, 110, 21, 14 );

// right triangle 31x50, 90 degrees at bottom left.
// `tile` is a point inside it, corners go from it
var tile = new Point( 75, 128 );
var corners3 = function() {
    return [
        tile.addClone( -15, 17 ),
        tile.addClone( 16, 17 ),
        tile.addClone( -15, -33 )
    ];
};

// the only new axis: normal of the hypotenuse.
// Triangle does not rotate, so it is calculated once
var n = normal( new Point( 31, 50 ) ).normalize();

var tests = [
    { axis: new Point( 1, 0 ) },
    { axis: new Point( 0, 1 ) },
    { axis: n }
];
rendering code
// drag the triangle: inside its box and on the inner side of the hypotenuse
tile.distance = function( p ) {
    var pts = corners3(), b = pts[ 1 ], c = pts[ 2 ];
    var inBox = p.x >= c.x && p.x <= b.x && p.y >= c.y && p.y <= b.y;
    var e = b.subClone( c ), q = p.subClone( c );
    return inBox && e.x * q.y - e.y * q.x >= 0 ? 0 : 1000;
};
tile.borrow = function( p ) {
    this.x = Math.round( p.x );
    this.y = Math.round( p.y );
    return this;
};
movablePoints.push( tile );

tests[ 0 ].at = new Point( 0, h - 24 );
tests[ 1 ].at = new Point( 24, 0 );
tests[ 2 ].at = new Point( w * 0.85, -20 );

move = function() {
    var tri = corners3();
    var hit = true, smallest = null;
    tests.forEach( function( t ) {
        t.tile = extent( tri, t.axis );
        t.box = boxInterval( box, t.axis );
        t.from = max( t.tile[ 0 ], t.box[ 0 ] );
        t.to = min( t.tile[ 1 ], t.box[ 1 ] );
        t.overlap = t.to - t.from;

        // collide: overlap on all axes
        if( t.overlap <= 0 )
            hit = false;
        // the smallest overlap is the way out
        if( !smallest || t.overlap < smallest.overlap )
            smallest = t;
    } );
    
rendering code
clear();
    var a = tri[ 0 ], b = tri[ 1 ], c = tri[ 2 ];
    triangle( a, b, c, BLUE_FILL );
    line( a, b, BLUE ); line( b, c, BLUE ); line( c, a, BLUE );
    fillBox( box, RED, RED_FILL );
    tests.forEach( function( t ) { t.tilePts = tri; } );
    drawTests( tests, box, hit, smallest );
};

#Round tiles

There are two kinds of round tiles: convex (solid quarter of a circle) and concave (square with a quarter of a circle cut out).

For both of them the extra axis goes from the circle center to the box. Here it goes to the closest corner of the box, and only when this corner is on the side of the arc.

var box = Box( 150, 60, 31, 14 );

// 45x45 tile with rounded top right corner,
// the tile is in the middle of the canvas.
// Circle center is in its bottom left corner
var r = 45;
var c = new Point( w / 2 - 22, h / 2 + 22 );

move = function() {
    var tests = [ {
        axis: new Point( 1, 0 ),
        tile: [ c.x, c.x + r ]
    }, {
        axis: new Point( 0, 1 ),
        tile: [ c.y - r, c.y ]
    } ];

    // bottom left corner of the box: the circle
    // axis goes to it, and counts only when it
    // is on the side of the arc
    var corner = new Point( box.x - box.xw.x,
        box.y + box.yw.y );
    if( corner.x > c.x && corner.y < c.y ) {
        var d = corner.subClone( c ).normalize();
        // from the circle center to the arc
        var center = dot( c, d );
        tests.push( {
            axis: d,
            tile: [ center, center + r ]
        } );
    }

    var hit = true, smallest = null;
    tests.forEach( function( t ) {
        t.box = boxInterval( box, t.axis );
        t.from = max( t.tile[ 0 ], t.box[ 0 ] );
        t.to = min( t.tile[ 1 ], t.box[ 1 ] );
        t.overlap = t.to - t.from;

        // collide: overlap on all axes
        if( t.overlap <= 0 )
            hit = false;
        // the smallest overlap is the way out
        if( !smallest || t.overlap < smallest.overlap )
            smallest = t;
    } );
    
rendering code
clear();
    for( var x = 0; x <= r; x++ )
        for( var y = 0; y <= r; y++ )
            x * x + y * y <= r * r && point( c.x + x, c.y - y, BLUE_FILL );
    for( var i = 0; i <= r; i++ ) {
        var j = round( sqrt( r * r - i * i ) );
        point( c.x + i, c.y - j, BLUE );
        point( c.x + j, c.y - i, BLUE );
    }
    line( c.x, c.y, c.x + r, c.y, BLUE );
    line( c.x, c.y, c.x, c.y - r, BLUE );
    fillBox( box, RED, RED_FILL );

    tests[ 0 ].at = new Point( 0, h - 24 );
    tests[ 0 ].tilePts = [ c, c.addClone( r, 0 ) ];
    tests[ 1 ].at = new Point( 24, 0 );
    tests[ 1 ].tilePts = [ c, c.addClone( 0, -r ) ];
    if( tests[ 2 ] ) {
        // perpendicular from the box corner to the arc
        line( corner, pix( d.mulClone( r ).add( c ) ), GRAY );
        // the axis moves with the box, so it goes 50px aside from the circle center
        tests[ 2 ].at = normal( d ).mul( -50 ).add( c );
        tests[ 2 ].tilePts = [ c, d.mulClone( r ).add( c ) ];
    }
    drawTests( tests, box, hit, smallest );
};

For the concave tile the solid part starts after the radius. Here is a simplification: the circle axis is used only when the corner of the box is in the same quadrant as the circle part. Otherwise the box can touch only straight sides of the tile.

var box = Box( 60, 60, 31, 14 );

// 45x45 tile in the middle of the canvas, a quarter
// of a circle is cut from its top right corner.
// Circle center is in that corner
var r = 45;
var c = new Point( w / 2 + 22, h / 2 - 22 );

move = function() {
    var tests = [ {
        axis: new Point( 1, 0 ),
        tile: [ c.x - r, c.x ]
    }, {
        axis: new Point( 0, 1 ),
        tile: [ c.y, c.y + r ]
    } ];

    // bottom left corner of the box goes deepest
    // into the hole. The circle axis goes to it and
    // counts only when it is in the hole quadrant
    var corner = new Point( box.x - box.xw.x,
        box.y + box.yw.y );
    if( corner.x < c.x && corner.y > c.y ) {
        var d = c.subClone( corner ).normalize();
        // solid part goes from the far corner
        // of the tile to the arc
        var far = c.addClone( -r, r );
        tests.push( {
            axis: d,
            tile: [ dot( far, d ), dot( c, d ) - r ]
        } );
    }

    var hit = true, smallest = null;
    tests.forEach( function( t ) {
        t.box = boxInterval( box, t.axis );
        t.from = max( t.tile[ 0 ], t.box[ 0 ] );
        t.to = min( t.tile[ 1 ], t.box[ 1 ] );
        t.overlap = t.to - t.from;

        // collide: overlap on all axes
        if( t.overlap <= 0 )
            hit = false;
        // the smallest overlap is the way out
        if( !smallest || t.overlap < smallest.overlap )
            smallest = t;
    } );
    
rendering code
clear();
    for( var x = 0; x <= r; x++ )
        for( var y = 0; y <= r; y++ )
            x * x + y * y >= r * r && point( c.x - x, c.y + y, BLUE_FILL );
    for( var i = 0; i <= r; i++ ) {
        var j = round( sqrt( r * r - i * i ) );
        point( c.x - i, c.y + j, BLUE );
        point( c.x - j, c.y + i, BLUE );
    }
    line( c.x - r, c.y, c.x - r, c.y + r, BLUE );
    line( c.x - r, c.y + r, c.x, c.y + r, BLUE );
    fillBox( box, RED, RED_FILL );

    tests[ 0 ].at = new Point( 0, h - 24 );
    tests[ 0 ].tilePts = [ c.addClone( -r, 0 ), c ];
    tests[ 1 ].at = new Point( 24, 0 );
    tests[ 1 ].tilePts = [ c, c.addClone( 0, r ) ];
    if( tests[ 2 ] ) {
        // perpendicular from the box corner to the arc
        line( corner, pix( d.mulClone( -r ).add( c ) ), GRAY );
        // the axis moves with the box, it goes 50px aside from the box bottom left corner
        tests[ 2 ].at = normal( d ).mul( -50 ).add( corner );
        tests[ 2 ].tilePts = [ d.mulClone( -r ).add( c ), far ];
    }
    drawTests( tests, box, hit, smallest );
};

#Circles

Circle has no sides, so we can't take axes from it. For a circle and a box we would take axes of the box (x and y) and axes from the circle center to each corner of the box.

Drag the circle near a corner: on x and on y they overlap, but the corner axis shows a gap.

var box = Box( 120, 100, 14, 31 );

// diameter is the box diagonal
var r = round( sqrt( 14 * 14 + 31 * 31 ) );
var ball = new Point( 78, 44 );
rendering code
// only the ball can be dragged
movablePoints.splice( movablePoints.indexOf( box ), 1 );
ball.distance = function( p ) {
    return Point.prototype.distance.call( this, p ) <= r ? 0 : 1000;
};
ball.borrow = function( p ) {
    this.x = Math.round( p.x );
    this.y = Math.round( p.y );
    return this;
};
movablePoints.push( ball );

move = function() {
    var tests = [
        { axis: new Point( 1, 0 ) },
        { axis: new Point( 0, 1 ) }
    ];
    // naive way: one more axis for every corner
    corners( box ).forEach( function( corner ) {
        var d = corner.subClone( ball ).normalize();
        tests.push( { axis: d, corner: corner } );
    } );

    var hit = true, smallest = null;
    tests.forEach( function( t ) {
        var center = dot( ball, t.axis );
        t.ball = [ center - r, center + r ];
        t.box = boxInterval( box, t.axis );
        t.from = max( t.ball[ 0 ], t.box[ 0 ] );
        t.to = min( t.ball[ 1 ], t.box[ 1 ] );
        t.overlap = t.to - t.from;

        // collide: overlap on all axes
        if( t.overlap <= 0 )
            hit = false;
        // the smallest overlap is the way out
        if( !smallest || t.overlap < smallest.overlap )
            smallest = t;
    } );
    
rendering code
clear();
    fillBox( box, BLUE, BLUE_FILL );
    fillCircle( ball.x, ball.y, r, RED_FILL );
    circle( ball.x, ball.y, r, RED );
    point( ball.x, ball.y, RED );

    // the box is fixed, the ball moves: blue is the box, red is the ball
    var shown = tests.map( function( t, i ) {
        return {
            axis: t.axis,
            at: [ new Point( 0, h - 24 ), new Point( 24, 0 ) ][ i ] || t.corner,
            tile: t.box, box: t.ball,
            tilePts: corners( box ),
            moverPts: [ ball.addClone( t.axis.mulClone( r ) ), ball.subClone( t.axis.mulClone( r ) ) ],
            // corner axes go through the ball: its projections would lie on the ball itself
            noMover: i > 1,
            from: t.from, to: t.to, overlap: t.overlap
        };
    } );
    drawTests( shown, box, hit, shown[ tests.indexOf( smallest ) ], true );
};

It works, but checking all 4 corners is too much. Only the closest corner matters.

#Voronoi regions

Each feature of a shape (vertex or edge) has a region: all points which are closer to this feature than to any other one. The closest point of the shape is always in the same region as the point we are checking.

Drag the blue point. Green area is a region of the closest feature. You could also modify the triangle.

var tri = [
    new Point( 70, 60 ),
    new Point( 170, 80 ),
    new Point( 110, 150 )
];
var dragMe = new Point( 200, 160 );
rendering code
var GREEN = 0x008800,
    // green 10% over white: solid, so parts of the area do not mix twice
    GREEN_FILL = 0xE6F3E6;
// dragged points stay on whole pixels
[ dragMe ].concat( tri ).forEach( function( p ) {
    p.borrow = function( m ) {
        this.x = Math.round( m.x );
        this.y = Math.round( m.y );
        return this;
    };
    movablePoints.push( p );
} );

// normal of the side a-b which looks out of
// the triangle (c is the third vertex)
var outside = function( a, b, c ) {
    var n = normal( b.subClone( a ) ).normalize();
    if( dot( n, c.subClone( a ) ) > 0 )
        n.mul( -1 );
    return n;
};

var region = function( p ) {
    var sides = tri.map( function( a, i ) {
        var b = tri[ ( i + 1 ) % 3 ],
            c = tri[ ( i + 2 ) % 3 ],
            pa = p.subClone( a ), pb = p.subClone( b );
        return {
            a: a, b: b, n: outside( a, b, c ),
            // distance to the side line, < 0 inside
            d: dot( pa, outside( a, b, c ) ),
            // p is before a or after b
            before: dot( pa, b.subClone( a ) ) <= 0,
            after: dot( pb, a.subClone( b ) ) <= 0
        };
    } );

    // vertex: after one side and before the next
    for( var i = 0; i < 3; i++ ) {
        var s = sides[ i ], next = sides[ ( i + 1 ) % 3 ];
        if( s.after && next.before )
            return { vertex: s.b, from: s, to: next };
    }
    // outside of a side, between its ends
    for( i = 0; i < 3; i++ ) {
        s = sides[ i ];
        if( s.d > 0 && !s.before && !s.after )
            return { side: s };
    }
    // inside: the closest side line
    var best = sides[ 0 ];
    sides.forEach( function( s ) {
        if( s.d > best.d )
            best = s;
    } );
    return { side: best, inside: true };
};

move = function() {
    var a = tri[ 0 ], b = tri[ 1 ], c = tri[ 2 ];
    // bisectors of the angles meet in the incenter.
    // Each vertex is weighted by the opposite side
    var la = b.distance( c ), lb = c.distance( a ),
        lc = a.distance( b );
    var incenter = a.mulClone( la )
        .add( b.mulClone( lb ) )
        .add( c.mulClone( lc ) )
        .mul( 1 / ( la + lb + lc ) );

    var my = region( dragMe );
    
rendering code
clear();
    var far = 400;
    var out = function( p, n ) { return pix( n.mulClone( far ).add( p ) ); };
    var center = pix( incenter );
    // the area where the point is
    var area;
    if( my.vertex )
        area = [ my.vertex, out( my.vertex, my.from.n ), out( my.vertex, my.to.n ) ];
    else if( my.inside )
        area = [ my.side.a, my.side.b, center ];
    else
        area = [ my.side.a, my.side.b, out( my.side.b, my.side.n ), out( my.side.a, my.side.n ) ];

    triangle( area[ 0 ], area[ 1 ], area[ 2 ], GREEN_FILL );
    area[ 3 ] && triangle( area[ 0 ], area[ 2 ], area[ 3 ], GREEN_FILL );

    // borders of all areas: bisectors inside, perpendiculars to sides outside
    tri.forEach( function( p, i ) {
        var next = tri[ ( i + 1 ) % 3 ], third = tri[ ( i + 2 ) % 3 ],
            n = outside( p, next, third );
        line( p, center, RED_LINE );
        line( p, out( p, n ), RED_LINE );
        line( next, out( next, n ), RED_LINE );
    } );
    line( a, b, RED ); line( b, c, RED ); line( c, a, RED );

    // sides of the area which go far are out of the canvas
    area.forEach( function( p, i ) {
        line( p, area[ ( i + 1 ) % area.length ], GREEN );
    } );

    // perpendicular to the closest side, or the line to the vertex
    var foot = my.vertex || my.side.n.mulClone( -my.side.d ).add( dragMe );
    line( dragMe, pix( foot ), GREEN );
    fillCircle( dragMe.x, dragMe.y, 2, BLUE );
    tri.forEach( function( p ) { fillCircle( p.x, p.y, 2, RED ); } );
};

For a box it is even simpler. After checking x and y we already know on which side of the box the circle center is. If it is out of the box on both axes — it is in a corner region, and this corner gives the only extra axis. Otherwise x and y are enough. This trick is described by James Arvo.

var box = Box( 120, 100, 40, 25 );
var r = 18;
var ball = new Point( 190, 40 );
rendering code
var GREEN = 0x008800,
    // green 10% over white
    GREEN_FILL = 0xE6F3E6;
// only the ball can be dragged
movablePoints.splice( movablePoints.indexOf( box ), 1 );
ball.distance = function( p ) {
    return Point.prototype.distance.call( this, p ) <= r ? 0 : 1000;
};
ball.borrow = function( p ) {
    this.x = Math.round( p.x );
    this.y = Math.round( p.y );
    return this;
};
movablePoints.push( ball );

move = function() {
    var tests = [
        { axis: new Point( 1, 0 ) },
        { axis: new Point( 0, 1 ) }
    ];

    // where the center is: -1 before the box,
    // 1 after it, 0 between its sides
    var dx = ball.x - box.x, dy = ball.y - box.y;
    var sx = Math.abs( dx ) > box.xw.x ?
        Math.sign( dx ) : 0;
    var sy = Math.abs( dy ) > box.yw.y ?
        Math.sign( dy ) : 0;

    // out of the box on both axes: corner region,
    // this corner gives the only extra axis
    if( sx && sy ) {
        var corner = new Point( box.x + sx * box.xw.x,
            box.y + sy * box.yw.y );
        tests.push( {
            axis: corner.subClone( ball ).normalize(),
            corner: corner
        } );
    }

    var hit = true, smallest = null;
    tests.forEach( function( t ) {
        var center = dot( ball, t.axis );
        t.ball = [ center - r, center + r ];
        t.box = boxInterval( box, t.axis );
        t.from = max( t.ball[ 0 ], t.box[ 0 ] );
        t.to = min( t.ball[ 1 ], t.box[ 1 ] );
        t.overlap = t.to - t.from;

        // collide: overlap on all axes
        if( t.overlap <= 0 )
            hit = false;
        // the smallest overlap is the way out
        if( !smallest || t.overlap < smallest.overlap )
            smallest = t;
    } );
    
rendering code
clear();
    // region of the center: green. Region borders go along the box sides
    var xs = [ 0, box.x - box.xw.x, box.x + box.xw.x, w ],
        ys = [ 0, box.y - box.yw.y, box.y + box.yw.y, h ];
    var rx = xs[ sx + 1 ], ry = ys[ sy + 1 ],
        rw = xs[ sx + 2 ] - rx + 1, rh = ys[ sy + 2 ] - ry + 1;
    rect( rx, ry, rw, rh, GREEN_FILL );
    [ 1, 2 ].forEach( function( i ) {
        line( xs[ i ], 0, xs[ i ], h, BLUE_LINE );
        line( 0, ys[ i ], w, ys[ i ], BLUE_LINE );
    } );
    strokeRect( rx, ry, rw, rh, GREEN );

    fillBox( box, BLUE, BLUE_FILL );
    fillCircle( ball.x, ball.y, r, RED_FILL );
    circle( ball.x, ball.y, r, RED );
    point( ball.x, ball.y, RED );

    // the box is fixed, the ball moves: blue is the box, red is the ball
    var shown = tests.map( function( t, i ) {
        return {
            axis: t.axis,
            at: [ new Point( 0, h - 24 ), new Point( 24, 0 ) ][ i ] || t.corner,
            tile: t.box, box: t.ball,
            tilePts: corners( box ),
            moverPts: [ ball.addClone( t.axis.mulClone( r ) ), ball.subClone( t.axis.mulClone( r ) ) ],
            // the corner axis goes through the ball: its projections would lie on the ball itself
            noMover: i > 1,
            from: t.from, to: t.to, overlap: t.overlap
        };
    } );
    drawTests( shown, box, hit, shown[ tests.indexOf( smallest ) ], true );
};

Circle vs triangles and round tiles works the same way: one more axis only when the circle center is in a corner region of the other shape.

#Points

The same code works for points. A point is just a box with zero half widths.

True or false answer would be correct, but the projection vector is not always what you want. When the point goes deep inside it can be pushed out from the wrong side. Move the point across the diagonal of the box and the arrow jumps to another side.

var box = Box( 120, 100, 70, 50 );
var p = new Point( 100, 90 );
rendering code
// only the point can be dragged
movablePoints.splice( movablePoints.indexOf( box ), 1 );
p.borrow = function( m ) {
    this.x = Math.round( m.x );
    this.y = Math.round( m.y );
    return this;
};
movablePoints.push( p );

move = function() {
    var tests = [
        { axis: new Point( 1, 0 ) },
        { axis: new Point( 0, 1 ) }
    ];

    var hit = true, smallest = null;
    tests.forEach( function( t ) {
        // a point is a box with zero half widths
        var d = dot( p, t.axis );
        t.box = boxInterval( box, t.axis );

        // how deep it is: distance to the closest
        // side of the box on this axis
        var back = d - t.box[ 0 ],
            forward = t.box[ 1 ] - d;
        t.overlap = min( back, forward );
        t.out = back < forward ? -back : forward;
        t.d = d;

        if( t.overlap <= 0 )
            hit = false;
        if( !smallest || t.overlap < smallest.overlap )
            smallest = t;
    } );

    // the way out: the smallest depth
    var push = hit && smallest.axis.mulClone( smallest.out );
    
rendering code
clear();
    // crossing a diagonal changes the closest side
    line( box.x - box.xw.x, box.y - box.yw.y, box.x + box.xw.x, box.y + box.yw.y, BLUE_LINE );
    line( box.x - box.xw.x, box.y + box.yw.y, box.x + box.xw.x, box.y - box.yw.y, BLUE_LINE );
    fillBox( box, BLUE, BLUE_FILL );

    // the box is fixed, the point moves: blue is the box, red is the point
    var shown = tests.map( function( t, i ) {
        return {
            axis: t.axis,
            at: [ new Point( 0, h - 24 ), new Point( 24, 0 ) ][ i ],
            tile: t.box, box: [ t.d, t.d ],
            tilePts: corners( box ), moverPts: [ p ],
            from: min( t.d, t.d + t.out ), to: max( t.d, t.d + t.out ),
            overlap: t.overlap
        };
    } );
    drawTests( shown, box, hit, shown[ tests.indexOf( smallest ) ], true );

    push && arrow( p, pix( p.addClone( push ) ), RED, 3 );
    fillCircle( p.x, p.y, 2, RED );
};

Same thing happens with boxes which moved too far in one frame: the shortest way out is not the way they came in. Small and fast objects have this problem more often.

In N point queries are used for homing rockets and to check if the ninja is close to a wall, so he can jump from it or slide along it.

#Fast objects

If an object moves further than its own size in one frame — it can fly through a wall and no test would see it.

The simplest solution is to not have such objects in the game. Another one is a sweep test: take the shape along its whole path and check collisions with it.

N uses multisampling: check a few positions between the previous and the new one. If the step is smaller than the radius it works very well.

Drag the start and the end points. Green circle is the only check at the new position, gray ones are samples.

var wall = Box( 120, 100, 3, 70 );
var r = 5;
var from = new Point( 30, 150 ),
    to = new Point( 210, 60 );
rendering code
var GREEN = 0x008800, DARK = 0x333333,
    // top byte is transparency: 90%
    GREEN_FILL = 0xE6008800, DARK_FILL = 0xE6333333;
// start and end are dragged by the whole circle, on whole pixels
movablePoints.splice( movablePoints.indexOf( wall ), 1 );
[ from, to ].forEach( function( p ) {
    p.distance = function( m ) {
        return Point.prototype.distance.call( this, m ) <= r ? 0 : 1000;
    };
    p.borrow = function( m ) {
        this.x = Math.round( m.x );
        this.y = Math.round( m.y );
        return this;
    };
    movablePoints.push( p );
} );

// circle vs box: distance from the center
// to the closest point of the box
var hits = function( c ) {
    var x = max( wall.x - wall.xw.x,
        min( c.x, wall.x + wall.xw.x ) );
    var y = max( wall.y - wall.yw.y,
        min( c.y, wall.y + wall.yw.y ) );
    return Point.prototype.distance.call( c,
        new Point( x, y ) ) < r;
};

move = function() {
    // samples: the step is smaller than the radius,
    // but there are no more than 30 of them
    var count = min( 30,
        Math.ceil( from.distance( to ) / r ) );
    var samples = [], hit = null;
    for( var i = 1; i < count && !hit; i++ ) {
        var s = from.lerp( to, i / count );
        samples.push( s );
        if( hits( s ) )
            hit = s;
    }
    
rendering code
clear();
    fillBox( wall, BLUE, BLUE_FILL );
    line( from, to, LIGHT );

    var ring = function( p, color, fill ) {
        p = pix( p );
        fill && fillCircle( p.x, p.y, r, fill );
        circle( p.x, p.y, r, color );
    };
    samples.forEach( function( s ) {
        s !== hit && ring( s, GRAY );
    } );
    if( hit ) {
        ring( hit, RED, RED_FILL );
        var at = pix( hit );
        print( 'hit', at.x + r + 2, at.y - 4, RED );
    }

    // the only check at the new position
    hits( to ) ? ring( to, RED, RED_FILL ) : ring( to, GREEN, GREEN_FILL );
    ring( from, DARK, DARK_FILL );
};

N has a limit of samples, so something very fast still can fly through. This limit depends on the game. Ragdoll in N is collided this way.

#Conclusion

It is not the fastest or the most elegant method, but it worked in N. Any convex shape can be added if we can calculate its half size on an axis. For speed it is better to use shapes where it can be calculated once or very cheap.

#Basic geometry

All examples above use a few simple operations with vectors.

#Normalization

Vector with length 1. Divide both coordinates by the length sqrt(x*x + y*y). Check that the length is not 0 before dividing.

#Dot product

a.x * b.x + a.y * b.y — just a number. If it is positive — vectors look in the same direction, if negative — in opposite. If one of them is normalized, it is a length of the other one along it.

#Projection

Projection of a to b is (dot(a, b) / dot(b, b)) * b. If b is normalized it is just dot(a, b) * b.

Drag p0, p1 and p2. Green vector is a projection of p1 → p0 to the line through p1 and p2.

var BLUE = 0x0000CC, GREEN = 0x008800,
    GRAY = 0xDDDDDD, CYAN = 0x00AADD,
    BLACK = 0x222222;

var p0 = new Point( 80, 40 ), p1 = new Point( 40, 150 ), p2 = new Point( 200, 120 );
rendering code
// dragged points stay on whole pixels
[ p0, p1, p2 ].forEach( function( p ) {
    p.borrow = function( m ) {
        this.x = Math.round( m.x );
        this.y = Math.round( m.y );
        return this;
    };
    movablePoints.push( p );
} );

move = function() {
    clear();
    var a = p0.subClone( p1 ), b = p2.subClone( p1 );
    line( p1.subClone( b.mulClone( 2 ) ), p1.addClone( b.mulClone( 3 ) ), GRAY );

    var projection = b.mulClone( dot( a, b ) / dot( b, b ) );
    // drawing needs whole pixels
    var end = pix( p1.addClone( projection ) );
    line( p0, end, CYAN );
    arrow( p1, p0, BLUE, 3 );
    arrow( p1, end, GREEN, 3 );

    [ [ p0, 'p0' ], [ p1, 'p1' ], [ p2, 'p2' ] ].forEach( function( item ) {
        circle( item[ 0 ].x, item[ 0 ].y, 2, GREEN );
        print( item[ 1 ], item[ 0 ].x + 4, item[ 0 ].y - 10, BLACK );
    } );
};

#Normals

Normal is a perpendicular vector (do not mix it with normalization). Each vector has two of them: right hand (-a.y, a.x) and left hand (a.y, -a.x).

var start = new Point( 120, 100 ), end = new Point( 190, 70 );
movablePoints.push( start, end );

move = function() {
    clear();
    var a = end.subClone( start );
    var right = new Point( -a.y, a.x ), left = new Point( a.y, -a.x );

    arrow( start, end, 0x000090, 3 );
    arrow( start, start.addClone( right ), 0xCC00AA, 3 );
    arrow( start, start.addClone( left ), 0x008800, 3 );
    print( 'right', start.x + right.x + 4, start.y + right.y, 0xCC00AA );
    print( 'left', start.x + left.x + 4, start.y + left.y, 0x008800 );
    circle( start.x, start.y, 2, 0x008800 );
    circle( end.x, end.y, 2, 0x008800 );
};