Triangle Intersection Benchmarks

Compare different ways to test triangles intersect in 2d

by eyal0

HTML

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.4/benchmark.js"></script>

<ul id='cycleResults'>

</ul>
<div id="result">

</div>
<br>
<button id="btn">
  Run Tests
</button>

JavaScript

var t0;
t0 = {
  a: {
    x: Math.random(),
    y: Math.random()
  },
  b: {
    x: Math.random(),
    y: Math.random()
  },
  c: {
    x: Math.random(),
    y: Math.random()
  }
};
var t1;
t1 = {
  a: {
    x: Math.random(),
    y: Math.random()
  },
  b: {
    x: Math.random(),
    y: Math.random()
  },
  c: {
    x: Math.random(),
    y: Math.random()
  }
};

var randomizeTriangles = function() {
  t0.a.x = Math.random();
  t0.a.y = Math.random();
  t0.b.x = Math.random();
  t0.b.y = Math.random();
  t0.c.x = Math.random();
  t0.c.y = Math.random();
  var v0x = t0.b.x - t0.a.x;
  var v0y = t0.b.y - t0.a.y;
  var v1x = t0.c.x - t0.a.x;
  var v1y = t0.c.y - t0.a.y;

  // if v0 cross v1 is positive, triangle is counter clockwise when viewed from above.
  t0.normal = v0x * v1y - v1x * v0y;

  t1.a.x = Math.random();
  t1.a.y = Math.random();
  t1.b.x = Math.random();
  t1.b.y = Math.random();
  t1.c.x = Math.random();
  t1.c.y = Math.random();
  var v0x = t1.b.x - t1.a.x;
  var v0y = t1.b.y - t1.a.y;
  var v1x = t1.c.x - t1.a.x;
  var v1y = t1.c.y - t1.a.y;
  t1.normal = v0x * v1y - v1x * v0y;
};
randomizeTriangles();

var pointInTriangleBary2 = function(point, triangle) {
  var p = point;
  var p0 = triangle.a;
  var p1 = triangle.b;
  var p2 = triangle.c;
  var dX = p.x - p2.x;
  var dY = p.y - p2.y;
  var dX21 = p2.x - p1.x;
  var dY12 = p1.y - p2.y;
  var D = dY12 * (p0.x - p2.x) + dX21 * (p0.y - p2.y);
  var s = dY12 * dX + dX21 * dY;
  var t = (p2.y - p0.y) * dX + (p0.x - p2.x) * dY;
  if (D < 0) return s <= 0 && t <= 0 && s + t >= D;
  return s >= 0 && t >= 0 && s + t <= D;
}

var linesIntersect = function(a1, a2, a3, a4) {
  var x12 = a1.x - a2.x;
  var x34 = a3.x - a4.x;
  var y12 = a1.y - a2.y;
  var y34 = a3.y - a4.y;
  var c = x12 * y34 - y12 * x34;
  if (c == 0) {
    return false;
  }
  var a = a1.x * a2.y - a1.y * a2.x;
  var b = a3.x * a4.y - a3.y * a4.x;
  var x = (a * x34 - b * x12) / c;
  var y = (a * y34 - b * y12) / c;
  return...