SAT for Polygon intersection in 50 lines of Haxe

polygon.hx

  // Given a Vec2 vector class...
  function hitPolygonAxis(points: Array<Vec2>, ret: Array<Float>) {
    for (i in 0...points.length) {
      var a = points[i];
      var b = points[(i+1) % points.length];
      var v = Vec2.make(b.x - a.x, b.y - a.y).normal();
      // we should be able to only use half circunference.
      ret.push(v.angle());
    }
  }

  function hitMinMaxProjectPolygon(points: Array<Vec2>, angle: Float): Vec2 {
    var ret = Vec2.make(Math.POSITIVE_INFINITY, Math.NEGATIVE_INFINITY);

    var axis = Vec2.make(1, 0);
    axis.rotate(angle);

    for (p in points) {
      var r = axis.dot(p);
      ret.x = Math.min(ret.x, r);
      ret.y = Math.max(ret.y, r);
    }

    return ret;
  }

  // Returns true if polygon formed by a set of points pa intersect with polygon pb.
  function hitPolygonPolygon(pa: Array<Vec2>, pb: Array<Vec2>): Bool {
    // Calculate all interesting axis.
    var axis = new Array<Float>();
    hitPolygonAxis(pa, axis);
    hitPolygonAxis(pb, axis);
    
    // this is a small optimization so we don't do the same axis twice.
    axis.sort(function (x, y) { return x > y ? 1 : x < y ? -1 : 0; });
    var lastangle = axis[0] - 1;
    for (angle in axis) {
      if (angle - lastangle < 1e-15) continue;
      lastangle = angle;

      // .x = min projected vertex, .y = max projected vertex.
      var a = hitMinMaxProjectPolygon(pa, angle);
      var b = hitMinMaxProjectPolygon(pb, angle);

      // we found a non intersecting axis. By the SAT, there is no collision.
      if (a.y < b.x || b.y < a.x) {
        return false;
      }
    }
    return true;
  }