作成したプログラムの概要

任意の数の点が与えられた時、点と点を結び凸多角形の外周を作ります。当然ながら、凸多角形の外側には点が存在しないようにします。
これを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.

複数の点から凸多角形の外周を引く