OBB

by jmchen

HTML

<div id="info">OBB (2D)
  <br/>
  <button id="bttn">reset</button>
</div>
<script src="https://cdnjs.cloudflare.com/ajax/libs/three.js/r70/three.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/numeric/1.2.6/numeric.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.0.0-alpha1/jquery.min.js">


</script>

CSS

#info {
  position: absolute;
  top: 0px;
  width: 100%;
  padding: 10px;
  text-align: center;
  color: #ffff00
}

body {
  overflow: hidden;
}

JavaScript

var camera, scene, renderer, mesh;
var dataPoints;
var obbLine;

init();
animate();

$("#bttn").click(function() {
  randomPts();
});

function randomPts() {
  if (dataPoints) {
    scene.remove(dataPoints);
    scene.remove(obbLine);
  }

  dataPoints = new THREE.Object3D();
  scene.add(dataPoints);

  for (var i = 0; i < 5; i++) {
    var m = mesh.clone();
    m.position.set(-15 + Math.random() * 30, -15 + Math.random() * 30, 0);
    dataPoints.add(m);
  }

  var obb = findOBB(dataPoints);
  console.log(obb);
  obbLine = drawOBB(obb);
  scene.add(obbLine);
}

function findOBB(dataPoints) {
  // copy the [x,y] array
  // input: dataPoints is an Object3D (group)

  var xyArray = [];
  for (var i = 0; i < dataPoints.children.length; i++) {
    xyArray.push([dataPoints.children[i].position.x, dataPoints.children[i].position.y]);
  }

  // find mean
  var xbar = 0,
    ybar = 0;
  for (var i = 0; i < xyArray.length; i++) {
    xbar += xyArray[i][0];
    ybar += xyArray[i][1];
  }
  xbar /= xyArray.length;
  ybar /= xyArray.length;

  // adjust data
  for (var i = 0; i < xyArray.length; i++) {
    xyArray[i][0] -= xbar;
    xyArray[i][1] -= ybar;
  }

  // covariance matrix
  var xx = xy = yy = 0;
  for (var i = 0; i < xyArray.length; i++) {
    xx += xyArray[i][0] * xyArray[i][0];
    xy += xyArray[i][0] * xyArray[i][1];
    yy += xyArray[i][1] * xyArray[i][1];
  }

  // solve eigenvectors
  var cM = [
    [xx, xy],
    [xy, yy]
  ];
  var ev = numeric.eig(cM);

  // pick PC1 as +x
  var PC1 = [ev.E.x[0][0], ev.E.x[1][0]];
  console.log(PC1);

  // rotate 90 CCW as +y}
  var PC2 = [-PC1[1], PC1[0]];

  // change basis
  for (var i = 0; i < xyArray.length; i++) {
    var xp = dot(xyArray[i], PC1);
    var yp = dot(xyArray[i], PC2);
    xyArray[i][0] = xp;
    xyArray[i][1] = yp;
  }

  // find xy extreme values
  var xMin, xMax, yMin, yMax;
  xMin = yMin = 1e10;
  xMax = yMax = -1e10;

  for (var i = 0; i < xyArray.length; i++) {
    if (xyArray[i][0] < xMin) xMin =...