第32回 プログラミングについて 『ポリゴンの話2』
『ポリゴンの話2』
前回はポリゴンのデータ表現について考えてみました。今回はポリゴンの回転方向を調べる方法を考えてみましょう。
ＣＡＤのアプリケーションなどを作っているとどうしてもポリゴンの回転方向を調べなければならないときがあります。例えば左回りが塗りのポリゴンで、右回りが抜きのポリゴンとしたときにはその方向が分からなければ実行できません。
ポリゴンが右回りか左回りかを調べたいとき、まず考えられるのは角度の和の符号を調べることです。具体的には次のようなアルゴリズムになります。
（１）角度の総和を０にします。
（２）最初の辺を０度とし、次の辺の角度が０以上～１８０度以下のときには角度の総
和にそのまま加算します。１８０より大きく３６０度より小さいときにはその角
度から３６０を引いた角度を加算します。
この計算をすべての辺について行ないます。
（３）角度の総和が正のときには左回り、負のときには右回りとなります。
多分この方法が世間一般のやり方です。しかしこの方法ではすべての辺の角度を求めなければなりませんので、大量の計算を行なわなければなりません。
ところが人間がポリゴンの回転方向を判断するときにはこのような計算は行なっていません。下の図を見て下さい。
８ ７
・ーーーー・
｜ １１ ｜
・ーー・ ｜ ５
９ ｜ ・ーーーーー・
１３ ｜ ６ ｜
・ーー・ ３ ｜
｜ １２ ・ーーー・
｜ ｜ ４
｜ ｜
・ーーーーーー・
１ ２
この図を見て人間はすべての辺の角度の計算などは行なわずに左回りと判断できます。図形が複雑になっても不思議なことに人間は簡単に判断してしまいます。いったいどのように人間はこの判断を行なっているのでしょうか。更に次の図を見て下さい。
３
・
／｜
／ ｜
／ ｜
／ ｜
／ ｜
／ ｜
／ ｜
／ ｜
・ーーーーーーーー・
１ ２
３角形は一番頂点の数（辺の数も）の少ないポリゴンです。この図では一目瞭然です。人間はこの３角形を見たとき辺１２と頂点３を対象に見たとき、辺１２より頂点３の方が上にあるので左回りと判断しているのです。それでは先ほどの変な図を見て下さい。
その変な図の辺１２と頂点３の関係もこの３角形の関係とまったく同じです。
これをプログラムで表現するには、
（１）ポリゴンの各頂点の中で、最も右、または最も左、または最も上、または最も下にあるものを探します。
（２）その頂点と次の頂点を結ぶ辺を０度としたときに、辺の次の頂点が辺の上にあるときには左回り、そうでないときには右回り。
というアルゴリズムになります。この最も右とか左とかがこのアルゴリズムの大切な部分です。そうでなければ違った答えになる可能性があります。
このアルゴリズムをプログラムにすると次のようになります。関数の引数は配列形式とし、最後の要素は最初の要素と同じ座標値ではないとします。
get_polygon_direction(xary,yary,lary)
double xary[],yary,
int lary;
{
double xm;
int cxm;
int nxm;
int pxm;
double agl,x,y;
int i;
/*
* " 最も左の頂点を探す "
*/
for(i=0;i<lary;i++){
if(i==0 || xary[i]<xm){
cxm=i;
xm=xary[cxm];
}
}
/*
* " 辺の角度を求める "
*/
/* 次の頂点の位置を求める */
if(cxm==lary-1)nxm=0;
else nxm=cxm+1;
/* 辺の角度を求める */
angle(xary[cxm],yary[cxm],xary[nxm],yary[nxm],&agl);
/*
* " 辺の次の頂点との位置関係を調べる "
*/
/* 辺の次の頂点の位置を求める */
if(nxm==lary-1)pxm=0;
else pxm=nxm+1;
/* 辺の角度を０度にするように頂点を回転 */
rotation(
xary[cxm],yary[cxm],-agl,
xary[pxm],yary[pxm],
&x,&y);
/* 頂点と回転の中心のＹ座標を比較 */
if(y>yary[cxm])return 1; /* 左回り */
return 2; /* 右回り */
}
この例では選択した頂点の後の２つ頂点が直線上にあったときの検査は行なっていません。また angle と rotation は以前に説明したものです。
人間の図形認識力は非常に優れたものです。複雑な図形でも一瞬のうちに認識することができるのです。プログラムを作るときにはできる限り人間のこうした能力を解析することも大切なことです。残念なのは人間は一瞬で図形の全貌を把握できるのに対し、コンピュータは、ピンホールのような小さい穴から図形の各部を順番に見ていかなければならないことです。
また、世間一般になっているアルゴリズムを鵜呑みにしないで、別の方法で実現できるか否かを検討することも大切なことです。
それではまた次回。
