作成したプログラムの概要
任意の数の点が与えられた時、点と点を結び凸多角形の外周を作ります。当然ながら、凸多角形の外側には点が存在しないようにします。
これをJavaScriptで作成しました。
以下はそのスクリーンショットです。
まずは、マウスクリックで複数の点を打ったところ。
次は、startボタンを押して、凸多角形を引いたところ。
記事の最後に、CodePenのページを貼り付けているので、実際に動きを確かめることができます。
どうやって求めているか
ソースコードにコメントつけているので、それと重複しますが、以下のような手順で求めています。
- 一番左と一番右の点を求める。
- この一番左の点から傾きが最大となる点を求める。
- さらに2で求めた点から右にある点で傾きが最大となる点を求める... これを、一番右の点までたどり着くまで繰り返す。
- 今度は同様の手順で、傾きが最小となる点を求めていく、これを、一番右の点までたどり着くまで繰り返す。
これで、凸多角形の各頂点が求まります。
作成したJavaScriptのコード
JavaScriptの新し目の文法も使っているので、IEだと動きません。たぶん、ES2015の範囲で書いていると思います。
配列を展開する...演算子初めて使ったかも。
MyCanvasクラス
コンストラクタで、<canvas>要素のidとサイズを受け取ります。このcanvasに対して、点を打ったり、線を引いたりするメソッドを用意しています。
class MyCanvas {
constructor (id, width, height) {
this.canvas = document.getElementById(id);
this.ctx = this.canvas.getContext('2d');
if (width)
this.ctx.canvas.width = width;
if (height)
this.ctx.canvas.height = height;
this.width = this.ctx.canvas.width;
this.height = this.ctx.canvas.height;
// ユーザが定義するイベントハンドラ
this.onClick = null;
//let self = this;
this.canvas.onclick = (e) => {
let x = e.clientX - this.canvas.offsetLeft;
let y = e.clientY - this.canvas.offsetTop;
if (this.onClick)
this.onClick(x, y);
};
}
// 線
drawLine(x1, y1, x2, y2, color = null, width = 1) {
this.ctx.save();
if (color != null)
this.ctx.strokeStyle = color;
this.ctx.lineWidth = width;
this.ctx.beginPath();
this.ctx.moveTo(x1, y1);
this.ctx.lineTo(x2, y2);
this.ctx.closePath();
this.ctx.stroke();
this.ctx.restore();
}
drawPoint(x1, y1, size = 3) {
this.ctx.save();
this.ctx.beginPath();
this.ctx.fillStyle = '#ff6666';
this.ctx.fillRect(x1 - Math.ceil(size/2), y1-Math.ceil(size/2), size, size);
this.ctx.restore();
}
// すべてをクリア
clearAll() {
this.ctx.clearRect(0, 0, this.width, this.height);
}
}
Solverクラス
これが、このクラスの中核となるクラスです。与えられた点の集合に対して、凸多角形の頂点の集合を求め、返します。
このクラスでは描画は行っていません。つまり、Canvasからは独立したクラスとなっています。
// Solver クラス
class Solver {
constructor () {
this.points = [];
}
solve(pts) {
this.points = pts;
return this.getFramePoints();
};
// 枠を形成するポイントを求める
getFramePoints() {
// 配列内の特定の要素の最小値を求めている
let minx = Math.min(...this.points.map(o => o.x));
// 最も左側のポイントを得る
let left = this.points.find(p => p.x === minx);
// 配列内の特定の要素の最大値を求めている
let maxx = Math.max(...this.points.map(o => o.x));
// 最も右側のポイントを得る
let right = this.points.find(p => p.x === maxx);
// 下半分を求める
let q1 = this._getFramePointsHalf(left, right, (now, seq) => {
return Math.max(...seq.map(p => Solver._gradient(now, p)));
});
// 上半分を求める
let q2 = this._getFramePointsHalf(left, right, (now, seq) => {
return Math.min(...seq.map(p => Solver._gradient(now, p)));
});
return q1.concat(q2.slice().reverse()); // a.slice().reverse() で非破壊的逆順
};
// 2点の傾き
static _gradient(p1, p2) {
return (p2.y - p1.y) / (p2.x - p1.x);
};
// 上(下)半分を求める
_getFramePointsHalf(now, right, maxGradient) {
let result = [now];
while (now.x != right.x || now.y != right.y) {
// 現地点より右側にあるポイントを得る
let seq = this.points.filter(p => p.x > now.x);
// 右側にあるポイントの中で最大傾斜角をもつポイントを求める
let next = seq.find(p => Solver._gradient(now, p) == maxGradient(now, seq));
result.push(next);
now = next;
if (now === undefined)
break;
}
return result;
};
}
Prograqmクラス+メイン処理
各イベント処理（マウスクリック、ボタンクリック）を行っています。Startボタンが押されると、Solverクラスを呼び出し、凸多角形を求め、 MyCanvasクラスを使って、描画しています。
class Program {
constructor(width, height) {
this.canvas = new MyCanvas('mycanvas', width, height);
this.points = [];
}
run() {
this.canvas.onClick = (x, y) => {
this.canvas.drawPoint(x,y);
this.points.push({x : x, y : y});
};
document.getElementById('solveButton')
.addEventListener('click', () => this._solve(), false);
document.getElementById('clearButton')
.addEventListener('click', () => this._clear(), false);
};
_solve() {
let solver = new Solver();
let ans = solver.solve(this.points);
let prev = ans.shift();
ans.forEach(val => {
this.canvas.drawLine(prev.x, prev.y, val.x, val.y, `#2E9AFE`);
prev = val;
});
};
_clear() {
this.canvas.clearAll();
this.points = [];
};
}
window.onload = function() {
let program = new Program(300, 300);
program.run();
};
html
最後は、HTMLファイルです。
<!DOCTYPE html>
<html>
<head>
<title>sample</title>
<style>
#mycanvas {
background-color: rgb(248, 253, 232);
}
</style>
<script src="convexPolygon.1.js"></script>
</head>
<body>
<div>
<canvas id="mycanvas"></canvas>
</div>
<div>
<input id="solveButton" type="button" value="Start" >
<input id="clearButton" type="button" value="Clear" >
</div>
</body>
</html>
CodePenの埋め込み
上記コードをCodePenで書いて、埋め込んでみました。
マウスクリックで複数の点を打ってから、[start]ボタンを押すと描画が始まります。
See the Pen convexPolygon by Gushwell (@gushwell) on CodePen.