Canvasで凸包を描画する

canvasで凸包を描画する。

凸包とは、wikiにもあるが簡単にいうと輪ゴムをかけたような状態。

やること

1. 点を散りばめる
2. 最小の凸集合を求める
3. 線を引く

点を散りばめる

まずはランダムで100個の座標をつくり、座標の位置に点を描画する。

座標をつくって描画

// canvasを取得
var canvas = document.getElementById('canvas');
// canvasを画面サイズにする
canvas.width = document.documentElement.clientWidth;
canvas.height = document.documentElement.clientHeight;

// contextを取得
var context = canvas.getContext('2d');

// 点を入れる配列
var points = [];

// あまり端に行き過ぎないように乱数を作成
var margin = 100;
for (var i = 0; i < 100; i++) {
  points.push({
    x: (Math.random() * (canvas.width - margin * 2) + margin) | 0,
    y: (Math.random() * (canvas.height - margin * 2) + margin) | 0
  });
}

// 点を描画
context.fillStyle = '#00f';
points.forEach(function (point) {
  context.beginPath();
  context.arc(point.x, point.y, 1, 0, Math.PI*2);
  context.fill();
});

こんな感じ。

最小の凸集合を求める

この部分の処理はいろいろやり方がありそうだが、今回は次のようにして凸集合を求めた。

1. 100個の座標のうち、Y座標が最小のものを抽出する
2. Y座標が同じものがある場合、その中でX座標が最小のものを選択し、起点とする
3. 起点を中心とし、それ以外の99個の座標の角度を計算して求められた値が最小になった座標を次の起点とする
4. 3を最初の起点にたどり着くまで繰り返す

thetaを計算する関数はこんな感じ。

getTheta

// 座標同士の角度を計算
var getTheta = function (point1, point2) {
  var width = point2.x - point1.x,
      height = point2.y - point1.y,
      radian = Math.atan(height / width),
      theta = radian * (180 / Math.PI);

  // arctanの返り値は -90 <= 角度 <= 90 なので、
  // 座標の象限によって値の調整を行う
  if (width >= 0 && height >= 0) {
    theta += 0;
  } else if ((width < 0 && height >= 0) || (width < 0 && height < 0)) {
    theta += 180;
  } else {
    theta += 360;
  }

  return theta;
};

100個の座標から凸集合を求める関数はこんな感じ。

getConvexPoints

var getConvexPoints = function (points) {

  var convexPoints = [];

  // 一番小さいYを取得
  var minY = points.reduce(function (min, point) {
    return Math.min(min, point.y);
  }, Infinity);

  // 一番小さいYを持つ中で、一番小さいXを持つ点を取得
  var C1 = points.filter(function (point) {
    return point.y === minY;
  }).sort(function (a, b) {
    return a.x - b.x;
  })[0];

  convexPoints.push(C1);

  var Cn = C1;
  // 起点から時計回りに次の点を起点を走査していく
  while (1) {
    var minTheta = Infinity,
        cLength = convexPoints.length,
        borderTheta = cLength === 1 ? 0 : (function () {
          var current = convexPoints[cLength-1],
              prev = convexPoints[cLength-2];

          return getTheta(prev, current)
        })(),
        index = -1;

    points.forEach(function (point, i) {
      if (point === Cn || point == null) { return; }

      var theta = getTheta(Cn, point);
      if (minTheta >= theta && theta >= borderTheta) {
        minTheta = theta;
        index = i;
      }
    });

    Cn = points[index];

    if (Cn === C1) { break; }

    convexPoints.push(Cn);

  };

  return convexPoints;
};

線を引く

最後に、求めた凸集合の座標に沿って線を引く。

線を引く

var convexPoints = getConvexPoints(points);
context.strokeStyle = '#000';
context.beginPath();
convexPoints.forEach(function (point) {
  context.lineTo(point.x, point.y);
});
context.closePath();
context.stroke();

こんな感じ。

demo