LoginSignup
17

More than 5 years have passed since last update.

円と多角形が重なることの判定

Posted at

動機

あるイベントで図形が可変する多角形と重なるならば、色を塗るという実装を作成しました。
今後も実装する機会はあるので、備忘録として、残しておきます。
ちなみに、three.jsを使っている前提となります。
collision_001.png

判定方法

大きく分けると、2つの処理が必要になります。

  1. 円が多角形の辺と接する
  2. 円の中心が多角形の中に存在する

多角形が多角形と重なるかということは、各点について、いずれかが多角形の中に存在するかなので、2のみ実装すれば、OKですが、円となると1の実装も必要になります。

実装

円が多角形の辺と接する

円の中心と線分との距離が、円の半径以内であれば、接するということになります。

以下のリンクを参考にしています。
http://1st.geocities.jp/shift486909/program/collision.html

「2.円がレーザーの線分に触れてないがどうか」を参考に、内積を使う方法で実装しました。

CircleUtil.js
var CIRCLE_UTIL = {
    /*
    円が多角形と接する
    */
    isTouchedShape : function (cent, radius, shapeVertices) {
        var count = shapeVertices.length;
        for (var i = 0; i < count; i++) {
            var isCrossed = CIRCLE_UTIL.isTouchedLine(cent, radius, shapeVertices[i], shapeVertices[(i+1)%shapeVertices]);
            if (isCrossed) {
                return true;
            }
        }
        return false;
    },
    /*
    円が線と接する。
    */
    isTouchedLine: function (cent, radius, v0, v1) {
        var v0c = new THREE.Vector3();
        var v01 = new THREE.Vector3();
        var v1c = new THREE.Vector3();
        v0c.subVectors(v0, cent);
        v1c.subVectors(v1, cent);
        v01.subVectors(v0, p1);
        var v0cLen = v0c.length(), v01Len = v01.length();
        var dot = v01.dot(v0c);
        var k = dot/Math.pow(v01Len, 2);
        // 各端への距離が半径より小さいか
        if (v0c.length() < radius || v1c.length() < radius) {
            return true;
        }
        // 線分上にあるか
        if (k < 0 || k > 1) {
            return false;
        }
        // 半径より、線分への距離が近いかどうか
        return Math.pow(v0cLen, 2) - Math.pow(dot, 2)/Math.pow(v01Len, 2) < Math.pow(radius, 2);
    }
};

円の中点と半径、多角形の点を引数に渡せば、接するかどうか判定できるようになりました。

collision_002.png

円の中心が多角形の中に存在する

点が多角形の中に存在するかどうかを判定します。

こちらは、以下のリンクを参考にしました。
http://www.nttpc.co.jp/technology/number_algorithm.html

Crossing Number Algorithmのほうになります。
ほぼそのままですが・・・。

PointUtil.js
var POINT_UTIL = {
    /*
    点が多角形の中にある
    Crossing Number Algorithm

    多角形が閉じていること(始点と終点が同じ)
    自己交差はほどく必要あり
    */
    isInShape : function (point, shapeVertices) {
        var count = 0;
        var vertexCount = shapeVertices.length;

        for (var i = 0; i < vertexCount; i++) {
            var p0 = shapeVertices[i];
            var p1 = shapeVertices[(i+1)%vertexCount];

            if (
                // 上向き
                ((p0.y <= point.y) && (p1.y > point.y))
                // 下向き
                || ((p0.y > point.y) && (p1.y <= point.y))) {
                    // 辺は右側、重ならない
                    var intersectionX = p0.x + (point.y - p0.y) * (p1.x - p0.x) / (p1.y - p0.y);
                    if (point.x < intersectionX) {
                        ++count;
                    }
            }
        }
        // 奇数であれば、内部にある
        return !!(count%2);
    }
};

コメントにも書いてありますが、多角形の辺が交差している箇所がある場合、それをほどくなり、別の多角形として、分割する必要があります。

collision_003.png

実装例

これを組み合わせれば、例えば、こんなかんじで、円と多角形が重なることが判定できるようになります。

example.js
renderer.domElement.addEventListener('mousemove', function(e){
    var centroid = new THREE.Vector3(e.offsetX, e.offsetY, 0);
    circle.position.x = centroid.x;
    circle.position.y = centroid.y;
    // 円が多角形の辺に接せず、内部にある場合
    if (POINT_UTIL.isInShape(centroid, vertices)
        || CIRCLE_UTIL.isTouchedShape(centroid, radius, vertices)) {
        line.material.color = new THREE.Color(0xff0000);
    } else {
        line.material.color = new THREE.Color(0xffffff);
    }
});

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
17