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


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

任意の数の点が与えられた時、点と点を結び凸多角形の外周を作ります。当然ながら、凸多角形の外側には点が存在しないようにします。
これをJavaScriptで作成しました。


以下はそのスクリーンショットです。

まずは、マウスクリックで複数の点を打ったところ。

<img src="https://qiita-image-store.s3.amazonaws.com/0/29415/a7169c5c-d90c-fcf4-2270-1ad8ec784b2b.png" width=50%>


次は、startボタンを押して、凸多角形を引いたところ。

<img src="https://qiita-image-store.s3.amazonaws.com/0/29415/7eb4718c-ea96-90c0-5a63-b50f6c9ae994.png" width=50%>

記事の最後に、CodePenのページを貼り付けているので、実際に動きを確かめることができます。

# どうやって求めているか

ソースコードにコメントつけているので、それと重複しますが、以下のような手順で求めています。

1. 一番左と一番右の点を求める。
2. この一番左の点から傾きが最大となる点を求める。
3. さらに2で求めた点から右にある点で傾きが最大となる点を求める... これを、一番右の点までたどり着くまで繰り返す。
4. 今度は同様の手順で、傾きが最小となる点を求めていく、これを、一番右の点までたどり着くまで繰り返す。

これで、凸多角形の各頂点が求まります。


# 作成したJavaScriptのコード

JavaScriptの新し目の文法も使っているので、IEだと動きません。たぶん、ES2015の範囲で書いていると思います。

配列を展開する`...演算子`初めて使ったかも。


## MyCanvasクラス

コンストラクタで、`<canvas>`要素のidとサイズを受け取ります。このcanvasに対して、点を打ったり、線を引いたりするメソッドを用意しています。

```js
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からは独立したクラスとなっています。

```js
// 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クラスを使って、描画しています。



```js
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ファイルです。

```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]ボタンを押すと描画が始まります。


<p class="codepen" data-height="450" data-theme-id="0" data-default-tab="js,result" data-user="gushwell" data-slug-hash="xMRgjy" style="height: 265px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid black; margin: 1em 0; padding: 1em;" data-pen-title="convexPolygon">
  <span>See the Pen <a href="https://codepen.io/gushwell/pen/xMRgjy/">
  convexPolygon</a> by Gushwell (<a href="https://codepen.io/gushwell">@gushwell</a>)
  on <a href="https://codepen.io">CodePen</a>.</span>
</p>
<script async src="https://static.codepen.io/assets/embed/ei.js"></script>