satoh

知っているようで知らないデジタル図形処理 ~任意形状図形の選択から交点・接点・接線計算まで、方程式では解けないノウハウを紹介

   

画面に描いた多角形をマウスで選択してみよう

凸型多角形を選択する

三角形、四角形、さらに五角形以上の多角形をマウスで選択することを考えます。
ここでいう選択は、多角形の輪郭線上ではなく多角形の内部をクリックしたときを「選択された」と考えます。
また、このトピックでは凸型の多角形のみを扱います。

内積-1
上記の様な場合を考えていきます。

外積を使う

2つのベクトルの外積は、

   |b| = |a||b|・sinθ

で定義されます。2つのベクトルのベクトル積です。
この式を見ればわかるように、2つのベクトルのなす角度が0~180度だとsinθは正、180度より大きければ負の値を取ることが明白です。2つのベクトルのなす角度が鋭角か鈍角かの判断が簡単にできるということです。
しかしこの式の右辺を使うとベクトルabの長さおよびabのなす角度を求めねばなりません。これは面倒ですし計算コストもかかります。そこで左辺のベクトル成分の計算を使うことにします。
外積はベクトル積であることに注意します。2つのベクトルがなす平面に垂直な方向のベクトルが得られます。その大きさは2つのベクトルでできる平行四辺形の面積となります。
さて、ここではX,Yの直行座標面で考えているので、ベクトル積はZ方向を向いており、それが上向きなのか(0~180度)下向きなのか(180度より大きい)を判断できればいいことになります。
従って、外積のX,Y成分は考えなくていいことになります。
いま二つのベクトルを、

    a (ax, ay)
    b (bx, by)

という成分を持っているとします、Z成分の外積は、

    ax * by – ay * bx

となります。しかしながら先程も述べた通り、XY成分は0なのでこれがそのまま|b|となります。
以下の図を見てください。
外積のイメージ

多角形内にマウスクリック座標があるか調べる

さて、この外積をどう応用するかということになりますが以下の図を見てください。
まず、マウスクリック点が多角形の中にある場合です。
多角形の中の場合次はマウスクリック点が多角形の外にある場合です。

多角形の外の場合a1,a2,a3,a4,a5 は、マウスクリック点から多角形の頂点へのベクトルを表します。
次に a1×a2a2×a3a3×a4a4×a5a5×a1、と隣り合うベクトルの外積を求めていきます。
上図を見ると、a5a1のなす角度だけが180度を超えていることがわかります。つまり、

・多角形内の点から隣り合う多角形頂点へのなす角度は必ず180度以下である

ということです。
ここまでわかれば後は簡単です。
上記のようのマウスクリック点からのベクトルで順次外積のZ成分を計算し、全て正(または同符号)であればマウスクリック点は多角形の内部にあり、多角形を選択した、ということになります。

プログラム

以上のことを踏まえてCで書いてみます。

typedef struct {
	int x ;
	int y ;
} POINT, *PPOINT ;

typedef struct {
	int vx ;
	int vy ;
} VECTOR, *PVECTOR ;

//------------------------------------------------------
//	凸多角形のヒットテスト
//		m	:マウスクリック座標
//		num	:多角形構成点数
//		pt	:多角形構成点座標
//		返値:0 選択されてない  1 選択された
//------------------------------------------------------
int HitPolygon(POINT m, int num, PPOINT pt)
{
	PVECTOR	vec ;
	int		i ;
	int		hit ;
	int		ans ;

	hit = 1 ;

	vec = (PVECTOR)malloc(sizeof(VECTOR) * (num + 1)) ;
	for (i = 0 ; i < num ; i++) {
		vec[i].vx = pt[i].x - m.x ;
		vec[i].vy = pt[i].y - m.y ;
	}
	vec[num].x = vec[0].x ;
	vec[num].y = vec[0].y ;

	for (i = 0 ; i < num ; i++) {
		ans = vec[i].vx * vec[i+1].vy - vec[i].vy * vec[i+1].vx ;
		if (ans < 0) {
			hit = 0 ;
			break ;
		}
	}

	return hit ;
}

 - C, ヒットテスト