第31回 プログラミングについて 『ポリゴンの話1』

『ポリゴンの話1』

　私が始めてポリゴンという言葉を耳にしたのはかれこれ１５年程前のことでした。その頃は英語の勉強が不足だったせいか自分が認識できる単語数も少なかったので、この言葉を聞いたときに、ウルトラマンななにかに出てくる怪獣のことだろうと最初は思ったのです。それにしては仕事の最中にポリゴンポリゴンと怪獣の名前を回りで言っているので、ウルトラマンと怪獣が仕事の邪魔でもしているかなあ、などと頭の中が混乱したのを覚えています。そしてその怪獣ポリゴンが多角形のことだと分かったのはそれから１年以上も経過した後のことでした。私はただの馬鹿かもしれません。

　さて、そのポリゴンを考えてみましょう。多角形は折れ線の最初と最後の位置が同じもので、折れ線に似ていますがそれが閉じられた図形か否かでそこに潜在する問題は格段に多くなります。閉じられた図形になると、その図形の内側外側、回転方向、塗りつぶし、ポリゴンどうしの演算（ＡＮＤとかＯＲとか）など、ただの折れ線では考慮しなかった問題が発生します。

　ポリゴンをプログラム内部でどのようにデータ表現すればいいのでしょうか。まず最初に考えなければならないのが、データの最後の位置をどうするかです。いま次のように一辺が１の正方形のポリゴンがあったとします。

（０、０）（１、０）（１、１）（０、１）（０、０）

このとき最初の（０、０）と最後の（０、０）が同じ位置になります。同じ位置でないと図形は閉じないで当然のことです。しかしながらこれをプログラム内でデータとして保持させるときに、最後の（０、０）を持っていた方がいいのか、それとも最後の位置は持たず、４つの頂点のみで保持するかが迷うところです。

　プログラムがポリゴンの外周を描画する程度の処理しか行なわないときには５つの頂点で、そうでないときには４つの頂点で表現した方がいいようです。これはあくまでも私個人の経験から得たことですので、違った意見の方もいるかと思います。５つの頂点でデータを表現したときには、１つのポリゴンに同一の座標を持った頂点が２つあることになり、４つの頂点で表現したときには辺が１つ足りないことになりますので、これはプログラムで対処しなければなりません。

　ここでは最後の頂点は持たない形式（上の例では４つの頂点を保持する方式）で考えてみます。

　ポリゴンをプログラム内で保持するためのデータの構造には色々なものが考えられます。配列の形式で表現するのが最も簡単かも知れません。

　#define MAX_POLY 100

　double xpoly[MAX_POLY];
　double ypoly[MAX_POLY];
　int　　lpoly;

簡単ですが、ポリゴンの頂点の数の最大値をいくつにするかの制限が発生することと、ポリゴンの頂点の数が少ないときにはメモリーの無駄が生じますので得策ではありません。やはりリスト形式で保持するのがいいように思われます。

　struct poly_strct{
　　double x,y;
　　struct poly_strct *next;
　};

　struct poly_strct *poly;

実際にはポリゴンが１つしかないことがありませんので次のようになります。

　struct xy_strct{
　　double x,y;
　　struct xy_strct *next;
　};

　struct poly_strct{
　　struct xy_strct *xy;
　　struct poly_strct *next;
　};

　struct poly_strct *poly;

それでは、実際にポリゴンをこの構造で表現するプログラムを作ってみましょう。

　#include <malloc.h>

　struct xy_strct{
　　double x,y;
　　struct xy_strct *next;
　};

　struct poly_strct{
　　struct xy_strct *xy;
　　struct poly_strct *next;
　};

　struct poly_strct *poly_top=NULL;　　/* リストの先頭のポリゴンを指し示す */
　struct poly_strct *poly_end=NULL;　　/* リストの最後のポリゴンを指し示す */

　add_poly(xary,yary,lary)
　double xary[],yary[];
　int　　lary;
　{
　　struct poly_strct *poly;
　　sturct　 xy_strct *xyp,*xyc;　　　 /* xyp は前の頂点を示しす */
　　　　　　　　　　　　　　　　　　　 /* xyc は追加する頂点を示す */
　　int i;
　/*
　*　" ポリゴンをリストに追加 "
　*/
　　poly=(struct poly_strct *)malloc(sizeof(struct poly_strct));
　　poly->xy　=NULL;
　　poly->next=NULL;

　　if(poly_end==NULL)poly_top　　　=poly;
　　else　　　　　　　poly_end->next=poly;

　　poly_end=poly;
　/*
　*　" ポリゴンに頂点を追加 "
　*/
　　xyp=NULL;

　　for(i=0;i<lary;i++){
　　　xyc=(struct xy_strct *)malloc(sizeof(struct xy_strct));
　　　xyc->x　 =xary[i];
　　　xyc->y　 =yary[i];
　　　xyc->next=NULL;

　　　if(xyp==NULL) poly->xy=xyc;
　　　else　　　　 xyp->next=xyc;

　　　xyp=xyc;
　　}
　}

これで配列形式で渡されたポリゴンの頂点をめでたく構造体の表現にすることができました。がしかし、ここでも１つ問題があります。ポリゴンに頂点を追加するときに最後の頂点の次のポインタ（next）をNULLにしましたがそれでいいのでしょうか。
例えばこの場合ポリゴンの各辺を表示するには、

　struct xy_strct *xyc,*xyn;

　xyc=poly_top;
　while(xyc){
　　if(xyc->next)xyn=xyc->next;
　　else　　　　 xyn=poly_top ;

　 printf("%f %f %f %f\n",xyc->x,xyc->y,xyn->x,xyn->y);

　 xyc=xyc->next;
　}

のようにして、最後の辺のときには最初の頂点の位置を表示するようにしなければなりません。

それではポリゴンに頂点を追加する部分を、

　/*
　*　" ポリゴンに頂点を追加 "
　*/
　　xyp=NULL;

　　for(i=0;i<lary;i++){
　　　xyc=(struct xy_strct *)malloc(sizeof(struct xy_strct));
　　　xyc->x=xary[i];
　　　xyc->y=yary[i];

　　　if(xyp==NULL){
　　　　xyc->next=xyc;
　　　　poly->xy =xyc;
　　　}
　　　else{
　　　　xyc->next=xyp->next;
　　　　xyp->next=xyc;
　　　}

　　　xyp=xyc;
　　}

として最後の頂点が先頭の頂点を指し示すようにします。この場合ポリゴンの各辺を表示するには、

　struct xy_strct *xyc,*xyn;

　xyc=poly_top;
　do{
　 printf("%f %f %f %f\n",xyc->x,xyc->y,xyc->next->x,xyc->next->y);
　}while((xyc=xyc->next)!=poly_top);

とすることができます。

　このようにポリゴンは頂点の最後にいけば先頭に戻るので、最後の頂点の次は先頭と表現してもいい訳です。これもどちらが良いのかは決められませんが好みの問題とも言い切れないような気もします。

　それではまた次回。