Circle Intersection Test

Yet another quick test for a geometry function:

Click, drag, and release to draw a line. A point will be drawn at the intersections if there are any. Hit ‘S’ to toggle between treating the drawn segment as a line segments or a line.

The demo uses some basic Phaser features for the interaction and drawing. The Javascript code is:

var game = new Phaser.Game(530, 300, Phaser.CANVAS, 'container',
                           { create: create, update: update, render: render });

var line;

var setting;

var result1;
var result2;

var circle;

var segment = true;

function create() {

  line = new Phaser.Line(game.world.width/4, game.world.height/4,
                         3*game.world.width/4, 3*game.world.height/4);

  circle = new Phaser.Circle(game.world.width/2, game.world.height/2,
                             Math.min(game.world.height, game.world.width)/2);

  game.input.onDown.add(click, this);
  setting = false;

  result1 = new Phaser.Point();
  result2 = new Phaser.Point();

    game.input.keyboard.addKey(Phaser.Keyboard.S)
        .onDown.add(function() {
            segment = !segment;
        }, this);
}


function update() {

    if (setting) {
        line.end.set(game.input.activePointer.x,
                      game.input.activePointer.y);

        if (!game.input.activePointer.isDown) {
            setting = false;
        }
    }
}


function click(pointer) {
    setting = true;
    line.start.set(pointer.x, pointer.y);
}


function render() {
  game.debug.geom(line);

  game.debug.geom(circle, '#00ff00', false, 2);

  var res = intersection(line, circle, result1, result2, segment);
  if (res) {
    result1.x--;
    result1.y--;
    result2.x--;
    result2.y--;

    game.debug.geom(result1, '#ff0000');

    if (res == INTERSECTION)
      game.debug.geom(result2, '#ff0000');
  }

}


var NO_INTERSECTION = 0;
var INTERSECTION = 1;
var SINGLE_INTERSECTION = 2;
var TANGENT = 3;

function intersection(line, circle, result1, result2, segment) {
  var lx = line.end.x - line.start.x;
  var ly = line.end.y - line.start.y;

  var len = Math.sqrt(lx*lx + ly*ly);

  var dx = lx / len;
  var dy = ly / len;

  var t = dx*(circle.x-line.start.x) + dy*(circle.y-line.start.y);

  var ex = t * dx + line.start.x;
  var ey = t * dy + line.start.y;

  var lec = Math.sqrt((ex-circle.x)*(ex-circle.x) +
                      (ey-circle.y)*(ey-circle.y));

  if (lec < circle.radius) {

    var dt = Math.sqrt(circle.radius*circle.radius - lec*lec);

    var te = dx*(line.end.x-line.start.x) + dy*(line.end.y-line.start.y);

    if (segment) {
      if ((t-dt < 0 || t-dt > te) &&
          (t+dt < 0 || t+dt > te)) {
            return NO_INTERSECTION;
      } else if (t-dt < 0 || t-dt > te) {
          result1.x = (t+dt)*dx + line.start.x;
          result1.y = (t+dt)*dy + line.start.y;
          return SINGLE_INTERSECTION;
      } else if (t+dt < 0 || t+dt > te) {
          result1.x = (t-dt)*dx + line.start.x;
          result1.y = (t-dt)*dy + line.start.y;
          return SINGLE_INTERSECTION;
      }
    }

    result1.x = (t-dt)*dx + line.start.x;
    result1.y = (t-dt)*dy + line.start.y;

    result2.x = (t+dt)*dx + line.start.x;
    result2.y = (t+dt)*dy + line.start.y;

    return INTERSECTION;
  } else if (lec == circle.radius) {

    result1.x = ex;
    result1.y = ey;

    result2.x = ex;
    result2.y = ey;

    return TANGENT;
  }

  return NO_INTERSECTION;
}

Line Intersection Test

Working on another game feature, I now need to compute actual line and rectangle intersections rather than just detecting them. This is a quick test:

Click, drag, and release to draw a line. A point will be drawn at the intersection if there is one. Hit ‘S’ to toggle between treating the geometry as line segments or lines.

The demo uses some basic Phaser features for the interaction and drawing. The calculation is taken straight from Phaser’s Arcade Physics math. The full Javascript code is:

var game = new Phaser.Game(530, 300, Phaser.AUTO, 'gamecontainer',
                           { create: create, update: update, render: render });

var linea;
var lineb;

var setting;

var result;

var segment;

function create() {

    linea = new Phaser.Line(game.world.width/4, game.world.height/4,
                            3*game.world.width/4, 3*game.world.height/4);
    lineb = new Phaser.Line(game.world.width/4, 3*game.world.height/4,
                            3*game.world.width/4, game.world.height/4);

    game.input.onDown.add(click, this);
    setting = false;

    result = new Phaser.Point();

    segment = true;

    game.input.keyboard.addKey(Phaser.Keyboard.S)
        .onDown.add(function() {
            segment = !segment;
        }, this);
}


function update() {

    if (setting) {
        lineb.end.set(game.input.activePointer.x,
                      game.input.activePointer.y);

        if (!game.input.activePointer.isDown) {
            setting = false;
        }
    }
}


function click(pointer) {
    setting = true;
    lineb.start.set(pointer.x, pointer.y);
}


function render() {
    game.debug.geom(linea);
    game.debug.geom(lineb);

    if (intersection(linea.start.x, linea.start.y,
                     linea.end.x, linea.end.y,
                     lineb.start.x, lineb.start.y,
                     lineb.end.x, lineb.end.y,
                     segment,
                     result)) {
        result.x--;
        result.y--;
        game.debug.geom(result, '#ff0000');
    }
}

function intersection(ax, ay, bx, by, ex, ey, fx, fy, asSegment, result) {

    var a1 = by - ay;
    var a2 = fy - ey;
    var b1 = ax - bx;
    var b2 = ex - fx;
    var c1 = (bx * ay) - (ax * by);
    var c2 = (fx * ey) - (ex * fy);
    var denom = (a1 * b2) - (a2 * b1);

    if (denom === 0) {
        return false;
    }

    result.x = ((b1 * c2) - (b2 * c1)) / denom;
    result.y = ((a2 * c1) - (a1 * c2)) / denom;

    if (asSegment) {
        if ( result.x < Math.min(ax, bx) || result.x > Math.max(ax, bx) ||
             result.y < Math.min(ay, by) || result.y > Math.max(ay, by) ||
             result.x < Math.min(ex, fx) || result.x > Math.max(ex, fx) ||
             result.y < Math.min(ey, fy) || result.y > Math.max(ey, fy) ) {
            return false;
        }
    }

    return true;

}

Line Test Demo

While entangled in the bowels of a diseased telecon I decided to make good use of my time and wrote this simple test:

Click, drag, and release to draw a new line. The text will (should?!) indicate whether or not the two points are on the same side of the line or not.

The demo uses some basic Phaser features for the interaction and drawing. Really though it’s just quadruple checking a basic calculation:

(Bx – Ax) * (Cy – Ay) – (By – Ay) * (Cx – Ax)

Where the line is defined by (Ax,Ay)–(Bx,By) and a point is (Cx, Cy). The value will be 0 if the point is on the line, and otherwise negative or positive depending on which side of the line it is on. The specific sign depends on the orientation of the line, but you can compare the sign for two points to determine if they’re on the same side or not. That can be boiled down into a single calculation. However, testing if four points are on the same side is a key part of a simple line/rectangle intersection test. For that use it seemed simpler to just calculate each separately.

The full Javascript code is:

var game = new Phaser.Game(530, 300, Phaser.AUTO, 'gamecontainer',
                           { create: create, update: update, render: render });

var line;
var setting = false;

var point1;
var point2;

var textSame;
var textDiff;


function create() {

  line = new Phaser.Line(game.world.width/4, game.world.height/4,
                         3*game.world.width/4, 3*game.world.height/4);

  point1 = new Phaser.Point(game.world.width/2, game.world.height/4);
  point2 = new Phaser.Point(game.world.width/2, 3*game.world.height/4);

  textSame = game.add.text(4, 0, "Same Side", { fill: '#ffffff' });
  textSame.visible = false;

  textDiff = game.add.text(0, 0, "Different Side", { fill: '#ffffff' });
  textDiff.visible = false;

  game.input.onDown.add(click, this);

  setting = true;

}

function update() {

  if (setting) {
    if (game.input.activePointer.isDown) {
      line.end.set(game.input.activePointer.x, game.input.activePointer.y);
    } else {
      setting = false;

        var sign1 =
            (line.end.x - line.start.x) * (point1.y - line.start.y) -
            (line.end.y - line.start.y) * (point1.x - line.start.x);

        var sign2 =
            (line.end.x - line.start.x) * (point2.y - line.start.y) -
            (line.end.y - line.start.y) * (point2.x - line.start.x);

        console.log("Signs are " + sign1 + "  " + sign2);

        if ((sign1<0 && sign2<0) ||
            (sign1>0 && sign2>0) ||
            (sign1==0 && sign2==0)) {

            textSame.visible = true;
            textDiff.visible = false;

        } else {
            textSame.visible = false;
            textDiff.visible = true;
        }
    }
  }
}

function click(pointer) {
  setting = true;
  line.start.set(pointer.x, pointer.y);
}

function render() {
  game.debug.geom(line);
  game.debug.geom(point1, '#ff0000');
  game.debug.geom(point2, '#ff0000');
}