第27回 プログラミングについて 『直線の話』

『直線の話』

 
　今回は直線（以下、線と省略することもあります）について考えてみましょう。

以前 、点の話をしましたが線は２つの点の関係とほぼ似ていますが違っているところといえ ばその２つの点が結ばれているというところです。別の言い方をすれば長さを持ってい るということです。ですから短い線、長い線、長さがない線などの考え方は２つの点の 関係とほとんど変わりはありません。しかしながら線の場合には線と点、あるいは線と 線の関係など考慮しなければならない項目が点以上に増大してきます。
　例えば、直線がＸ軸に平行か否かを判断するときには厳密には直線の長さも考慮しな ければなりません。Ｘ軸に平行か否かを判断するには実数値には誤差が含まれています ので、直線の両端のＹ座標が同一のときの他、ほぼ同じ（この「ほぼ」というのが難し いのですが）ときに平行と判断します。
　間違いは「Ｙ座標の差の絶対値が０．００１以内に平行」と定義したところにありま す。差を０．０００１以内としたところで結局は同じことになります。直線の長さが考 慮されていないのが最大の問題なのです。そこで、「両端のＸ座標の差の絶対値または 直線の長さとＹ座標の差の絶対値の比率が０．００１以内のときがＸ軸と平行」と定義 しなければならないということになります。

　実は私も以前上記のように長さを考慮せずに平行か否かを判断する関数を作って使用 していました。アプリケーションが扱う直線が最大でも１０００で、最小のときでも０ ．１程度でしたからほとんどの場合には問題はありませんでした。それでもごくまれに 誤動作を起こすことがあったのです。その確率は終日アプリケーションを使用していて １年に数回程度のものでした。そこで差の範囲を小さくしたりしてなんとかごまかして しまったものでした（本当はいけないことです）。

　点の位置が直線のどちらかの端に一致するとき、どちらの端に一致しているかを判定 するときにも単純に一致する範囲を決めてしまってはいけません。上記のようにほとん どの場合では正しく認識できたとしても、直線の長さが一致するという範囲に近くなれ ば正しい答えは出せません。こういうときには点から、直線のそれぞれの端までの距離 を計算し、短い方を選択するようにしなければなりません。直線どうしのときももう少 し複雑になりますが同様な処理の仕方になります。

話は外れますが、以前どこかのネットワークで「２つの直線が交差するか否かの判定 」について議論しているものを見かけたことがあります。なかなか熱心に議論している ようでした。議論な内容そのものについて批評する気はありませんが、１つだけ気にな ったことがありました。２つの直線についての議論ですから、基本的には数学が必要に なるのは当然ですが、あまりにも数式上での処理に凝り過ぎているような気がするので す。また、概念的な議論でしたから仕方がないのかも知れませんが、誤差の問題とか、 ０での除算についての処理については例文では記述されていなかったことも気にかかり ました。
　私も、どうしても数式上での処理が必要なときにはそれに従いますが、「できるだけ 数式の計算を行なわないで処理できないか」と心がけるようにしています。以前にもお 話しましたが、円弧の最小最大を算出する話とか、回転する話なども実はその現れです 。数学上（代数）での解の算出法をそのままプログラムに置き換えようとすると、以外 に面倒なことがあります。誤算の問題とか、０での除算とか様々はことを考慮しなけれ ばなりません。ところが計算機で解を出すときには、数学も当然必要ですが、別にこれ にこだわる必要もないと思います。計算機には計算機でのやり方があるのです。実際に 数学にこだわるあまりにプログラムが複雑になって、後になって全然解読ができない関 数作ってしまったことがあります。
　例えば、３点を通る円の半径を求める関数を作るとします。多分数学上では、３つの 点を三角形の頂点として考え、２辺の中点からの垂線の交点を求め、その交点と１つの 頂点までの長さを計算をすると思います。これが一番素直なやりかたには違いありませ ん。
　しかしながら計算機ではそんなに正直に計算する必要はありません。

　（１）その三角形の一辺がＸ軸と水平になるように三角形を回転します。
　（２）Ｘ軸と水平にした辺の中点が原点になるように三角形を平行移動します。
　（３）Ｘ軸と水平でない他の一辺の中点の垂線のＸ座標が０になるＹ座標を求めます。
　（４）（３）でもとめた座標が円の中心位置ですから、あとは半径を求めます。

　今回は直線の話ですから実際のプログラムは紹介しませんが、ほとんど難しいい計算 はなくなってしまうのが分かると思います。

　さて、その２つの直線が交わるか否かの話ですが、これもできる限り数式を使わないで行なおうとすれば、回してみるのが一番簡単なような気がします。

　#include <math.h>

　#define RANGE ...　　　　 /* RANGE には任意の値を定義します */

　double angle(double x1,double y1,double x2,double y2);
　　　　　　　　　　　　　　/* 角度を求める関数は２０回目に説明しました */
　void rotation(double xc,double yc,double rot,
　　　　　　　　double xsrc,double ysrc,
　　　　　　　　double *xret,double *yret);
　　　　　　　　　　　　　　/* 点を回転させる関数は１６回目に説明しました */

　int check_line_cross(
　　　　x11,y11,x12,y12,　　/* 直線１ */
　　　　x21,y21,x22,y22)　　/* 直線２ */
　double x11,y11,x12,y12;
　double x21,y21,x22,y22;
　{
　　double agl;
　　double xt,yt1,yt2;

　　agl=angle(x11,y11,x12,y12);　　　　　　　　 /* 直線１の角度を求める */
　　　　　　　　　　　　　　　　　　　　　　　　/* 直線１がＸ軸と平行になるよう
　　　　　　　　　　　　　　　　　　　　　　　　　 に直線２を回転させる */
　　rotation(x11,y11,-agl,x21,y21,&xt,&yt1);
　　rotation(x11,y11,-agl,x22,y22,&xt,&yt2);
　　　　　　　　　　　　　　　　　　　　　　　　/* 回転した直線２の両端のＹ座標
　　　　　　　　　　　　　　　　　　　　　　　　　 が回転させたときの原点が
　　　　　　　　　　　　　　　　　　　　　　　　　 RANGE外のときには交差しない
　　　　　　　　　　　　　　　　　　　　　　　　*/
　　if(yt1>y11+RANGE && yt2>y11+RANGE)return 0;
　　if(yt1<y11-RANGE && yt2<y11-RANGE)return 0;
　　　　　　　　　　　　　　　　　　　　　　　　/* 次は上と同じように直線２がＸ
　　　　　　　　　　　　　　　　　　　　　　　　　 軸と変更になるように直線１を
　　　　　　　　　　　　　　　　　　　　　　　　　 回転させてチェックする */
　　agl=angle(x21,y21,x22,y22);
　　rotation(x21,y21,-agl,x11,y11,&xt,&yt1);
　　rotation(x21,y21,-agl,x12,y12,&xt,&yt2);

　　if(yt1>y21+RANGE && yt2>y21+RANGE)return 0;
　　if(yt1<y21-RANGE && yt2<y21-RANGE)return 0;

　　return 1;
　}

　多分こんなふうにするのが誰が見ても簡単に理解できると思います。この例ではまどろっこしい表現をしていますが、引数を工夫したり、ループにすることでもう少しスッキリしますので考えてみて下さい。また複素数も利用できるはずですので、そちらの方法も検討してみる価値があるかも知れません。

　ペンプロッタなどに図形を描画すると、機種によっては円や円弧の描画が遅いものがあります。現在のものでは改善されているのかもしれませんが、全般的にはその傾向はあるようです。ペンプロッタでは円であっても円弧であっても最終的には直線の集まりで描画しますので、これをきれいに描画するには短い直線に近似する際にかなり小さく分割していることに起因していると思われます。またＣＡＤのエディタなどで表示領域内にのみ円や円弧を描画するときにも、円や円弧のままでクリッピングさせようとするとかなり面倒な計算をしなければなりません。
　このようなときには円や円弧を直線に近似するのが解決の近道になることがあります。

　例えば円をプロッタに描画するときには、

　#include <math.h>
　#define PAI 3.141592653589793　/* 円周率 */
　#define DIV 10　　　　　　　　 /* 円の分割数 */

　void draw_circle(xc,yc,r)
　double xc,yc,r;
　{
　　double a,d,x,y;
　　int　　mode;

　　a=0.0;　　　　　　　　　 /* 角度 */
　　d=(PAI*2)/DIV;　　　　　 /* 分割数に応じた角度の変化量 */

　　mode=1;　　　　　　　　　/* 描画モード
　　　　　　　　　　　　　　　　1:ペンをアップして移動
　　　　　　　　　　　　　　　　2:ペンをダウンして移動
　　　　　　　　　　　　　　　　0:ペンをダウンして移動し終了
　　　　　　　　　　　　　　 */
　　while(1){
　　　x=r*cos(a)+xc;　　　　 /* 円周上の座標を求めます */
　　　y=r*sin(a)+yc;

　　　if(mode==1)move(x,y);　/* ペンをアップして移動する命令を出力する関数 */
　　　else　　　 line(x,y);　/* ペンをダウンして移動する命令を出力する関数 */

　　　if(mode==0)return;

　　　a+=d;　　　　　　　　　/* 次の位置の角度を求めます */
　　　if(a>=PAI*2){　　　　　/* 角度が３６０度以上のときには角度を３６０度ちょ
　　　　　　　　　　　　　　　　うどにしてモードを０にします */
　　　　a=PAI*2;
　　　　mode=0;
　　　}
　　　else{　　　　　　　　　/* それ以外のときにはモードを２にします */
　　　　mode=2;
　　　}
　　}
　}

　この例では分割数を１０に固定していますが、通常ペンプロッタなどに描画するときには、円の半径に応じて分割数が変化するようにします。分割数を設定するには何種類か考えられますが、最も簡単で実用的な方法は半径とそれに応じた分割数を数段階用意することです。どのように範囲を設定するかは、実際に描画してみるのが一番です。ここまでくるとプログラミングは理論でもなんでもなく、やってみてだめだったら変えてみようといった泥臭い世界になってしまいますが...

　それではまた次回。