第48回 プログラミングについて『直線のバインド』

　分かってしまえば簡単なことですが、最近面白い（面白くもないかな）処理を行なったことがありました。

　[処理内容]　複数の線分があったとき、重複している線分を削除する。

　問題は簡単ですがもう少し分かりやすく説明すると、

　　　　　　　　　　　　　・Ｄ　　　　　　　　・Ｈ　　　　　　　　 ・Ｊ
　　　　　　　　　　　　／　　　　　　　　　／　　　　　　　　　 ／
　　　　　　　　　　　／　　　　　　　　　／　　　　　　　　　 ／
　　　　　　　　　　／　　　　　　　　　／　　　　　　　　　 ／
　　　　　　　　　・Ｂ　　　　　　　　／　　　　　　　　　 ・Ｌ
　　　　　　　　／　　　　　　　　　／　　　　　　　　　 ／
　　　　　　　／　　　　　　　　　・Ｆ、Ｇ　　　　　　 ／
　　　　　　／　　　　　　　　　／　　　　　　　　　 ／
　　　　　・Ｃ　　　　　　　　／　　　　　　　　　 ・Ｋ
　　　　／　　　　　　　　　／　　　　　　　　　 ／
　　　／　　　　　　　　　／　　　　　　　　　 ／
　　／　　　　　　　　　／　　　　　　　　　 ／
　・Ａ　　　　　　　　・Ｅ　　　　　　　　 ・Ｉ

　　　　　　　　　　　　　　図１


　上図のように、直線Ａ－Ｂと直線Ｃ－Ｄが重なり合っているときにはこの２つの直線の代わりに直線Ａ－Ｄを生成し、直線Ｅ－Ｆの端点Ｆと直線Ｇ－Ｈの端点Ｇが一致していているときにはこの２つの直線の代わりに直線Ｅ－Ｈを生成し、直線Ｉ－Ｊと直線Ｋ－Ｌのような関係のときにはこの２つの直線の代わりに直線Ｉ－Ｊを生成するというものです。（このときのそれぞれの直線は同じ角度です。）

　人間ならば幼稚園の子供でも簡単に答えを出してしまいます。ところがいざこれを計算機にやらせようとすると以外に難しいものです。単純の考えると、同じ角度か否かの判断、直線どうしが重なり合っているかどうかの判断など面倒な計算をしなければならなくなります。

　ところが、ちょっとした工夫で意外と簡単になるのです。図１の直線Ａ－Ｂと直線Ｃ－Ｄを考えてみましょう。処理を簡単にするためには直線を回転させることです。まず、直線Ａ－Ｂが０度（Ｘ軸と平行）になるように２つの直線を回転させます。

　・－－－・－－－・－－－・
　Ａ　　　Ｃ　　　Ｂ　　　Ｄ

　　　　　　図２

　２つの直線を回転させると、当然のことですが点Ａと点ＢのＹ座標は同じになります。もし点Ｃまたは点ＤのＹ座標が点ＡのＹ座標と違っているときには２つの直線は重なり合っていないので処理する必要はありません。Ｙ座標が同じときには重なり合っている可能性がありますので次はＸ座標をチェックします。

　図２の直線ＡーＢのＡの点は０度になるように回転していますので、点ＡのＸ座標は必ず点ＢのＸ座標よりも小さくなっていますが、直線Ｃ－Ｄでは点ＣのＸ座標がが点ＤのＸ座標よりも小さいとは限らないので、点ＣのＸ座標の方が大きいときには点ＤのＸ座標値と交換します。すなわちＸ座標に注目すると、Ａ＜Ｂ、Ｃ＜Ｄになるようにします。

　ここで、

　　Ｂ＜Ｃ または Ｄ＜Ａ

　のときには２つの直線は重なっていませんので処理する必要はありません。それ以外のときには重なっていますので、

　Ｃ＜Ａ のときには 点ＡのＸ座標を点ＣのＸ座標とします。
　Ｂ＜Ｄ のときには 点ＢのＸ座標を点ＤのＸ座標とします。

とすると、点Ａと点ＢのＸ座標は２つの直線の端から端までのＸ座標となりますので、再び点Ａと点Ｂを元の直線Ａ－Ｂの角度になるように回転すると目的の直線が得られることになります。「なーんだ簡単だ」ということになります。

　では、具体的にプログラムで書いてみましょう。いま直線は次の構造体で表現されるとします。

　struct line_strct{
　　double x1,y1,x2,y2;
　　struct line_strct *next;
　};

そして不要な線分を削除する関数を bind_line としましょう。

　bind_line(line_top)
　struct line_strct *line_top;
　{
　　struct line_strct *l1,*l2,*lt;
　　int binded;

　　binded=1;
　　while(binded){
　　　 binded=0;

　　　 for(l1=line_top;l1;l1=l1->next){
　　　　 for(l2=l1->next,lt=l1;l2;lt=l2,l2=l2->next){
　　　　　 if(is_bind(l1,l2)){
　　　　　　 lt->next=l2->next;　　　　　　　 /* ポインタのつなぎ変え */
　　　　　　 free(l2);　　　　　　　　　　　　/* 不要になった直線を削除 */
　　　　　　 l2=lt;
　　　　　　 binded=1;
　　　　　 }
　　　　 }
　　　 }
　　}
　}

　関数 is_bind は ２つの直線を上で説明した処理を行い、１つの直線にまとめることができるときには、最初の直線の座標を変更し真の値を返し、そうでないときには偽を返すものとします。上の bind_lineはすべての線分を総当たりで計算するループの組み方で、２つの線分が１つにまとめなくなるまでくりかえします。線分の数が多くなるとループの回数がベキ乗に比例して増えますので遅くなりますが、最も簡単なやり方です。

　次に is_bind 関数を作りましょう。

　is_bind(l1,l2)
　struct line_strct *l1,*l2;
　{
　　double agl;
　　double x12,y12,x22,y22;
　　double t;

　　angle(l1->x1,l1->y1,l1->x2,l1->y2,&agl);

　　rotation(l1->x1,l1->y1,agl,l1->x2,l1->y2,&x12,&y12);
　　rotation(l1->x1,l1->y1,agl,l2->x1,l2->y1,&x21,&y21);
　　rotation(l1->x1,l1->y1,agl,l2->x2,l2->y2,&x22,&y22);

　　if(y21!=y12)return 0;
　　if(y22!=y12)return 0;

　　if(x22<x21){ t=x21; x21=x22; x22=t; }

　　if(x22<l1->x1)return 0;
　　if(x21>x12　 )return 0;

　　if(x21<l1->x1)l1->x1=x21;
　　if(x22>x12　 )x12　 =x22;

　　rotation(l1->x1,x12,-agl,y12,&l1->y1,x12,y12,&l1->x2);

　　return 1;
　}

　この関数は説明したやり方をそのまま表現しています。関数 angle　と rotation は以前に説明しているものです。また座標値を判定するときにはプログラムの例を簡単にするために実数値の誤差は考慮していません。

　線分の数が多くなるとこの方法（関数 bind_line）ループの回数が増えますので、安定して処理速度を向上させるには、あらかじめ次のようなことを行ないます。

　（１）各線分のＸ方向とＹ方向の最小値と最大値を線分のデータに持たせる。
　（２）線分をＸ方向の最小値の小さい順でソートする。Ｘ方向の最小値が同じときにはＹ方向の最小値の小さい順でソートします。

　最小最大を持たせるために線分の構造を次のようにしたとします。

　struct line_strct2{
　　double x1,y1,x2,y2;
　　double xmin,ymin,xmax,ymax;
　　struct line_strct2 *next;
　};

ソートをする部分は今回の本題ではないので、ソートされているものとし、bind_line2を作ってみます。

　bind_line2(line_top)
　struct line_strct2 *line_top;
　{
　　struct line_strct2 *l1,*l2,*lt;

　　for(l1=line_top;l1;l1=l1->next){
　　　for(l2=l1->next,lt=l1;l2;lt=l2,l2=l2->next){
　　　　if(l2->xmin>l1->xmax)break;
　　　　if(l2->ymin>l1->ymax)continue;
　　　　if(l2->ymax<l1->ymin)continue;

　　　　if(is_bind2(l1,l2)){
　　　　　lt->next=l2->next;
　　　　　free(l2);
　　　　　l2=lt;
　　　　}
　　　}
　　}
　}

　関数 is_bind2 は is_bind とほぼ同じですが、１つにまとめたときには l1 の最小最大も正しく設定するようにします。
　関数 bind_line2 と bind_line はあまり違いがないようですが、線分の数が多くなると処理速度に強烈な差がでますので、この違いを検討してみて下さい。

　それではまた次回。