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

動機

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

判定方法

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

1. 円が多角形の辺と接する
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);
	}
};

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

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

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

こちらは、以下のリンクを参考にしました。
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);
	}
};

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

実装例

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

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);
	}
});