Help us understand the problem. What is going on with this article?

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

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

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

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

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

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

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

どうやって求めているか

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

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

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

作成したJavaScriotのコード

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.

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした