第18回 プログラミングについて 『点の話』

『点の話』

  点の話。図形をコンピュータで処理をしようとすると、点、線、面、角度など様々な要素があります。今回はその要素の中の点について考えてみましょう。

　といっても、実のところ私にも点のすべてが分っていはいないのです。新しい発見がプログラムを作れば作るほどあるのです。そこで自分の分っている範囲で話を進めていきます。

　２次元の座標系では点は２つのパラメータで表現されます。３次元では当然３つになります。ここでは２次元について考えてゆきましょう。直交座標系では点はＸ座標とＹ座標の２つのパラメータで、極座標系では角度と距離の２つパラメータで表現されます。それでは、この点を表現するときそのどちらで表現すればいいのでしょうか。多分、通常ではＸとＹの座標で表現すると思います。私もプログラムの中では１００％近くはそうしています。しかしながら極座標で表現した方が都合の良いこともあるのです。というよりもＸＹ座標で表現するととんでもなく面倒なことになる場面も存在するのです。

　以前作ったプログラムでこんな機能を作ったことがありました。『可変形状図形を任意に定義する』というものです。むずかしい言葉ですが、かいつまんで言うと指定された複数個の点の関係をもとにして生成される図形を論理的に定義することです。
　例えば、

　/macro abc
　　.line　1.0/p1x,p1-p2　1.0/p1y,p1-p2　0.0/p2x,p1-p2　0.0/p2y,p1-p2
　/end

と定義されたとします。 /macro は論理図形マクロのこれから定義するぞという意味とし、abc がそのマクロ名とします。.line は線分を引くという意味で問題はその次です。
　.line のパラメータを基本的に　x1 y1 x2 y2 であるとします。これに上記のパラメータを対応させると、

　x1 ： 1.0/p1x,p1-p2
　y1 ： 1.0/p1y,p1-p2
　x2 ： 0.0/p2x,p1-p2
　y2 ： 0.0/p2y,p1-p2

となります。２つのポイント p1 と p2 が指定されたとき、x1 の 1.0/p1x,p1-p2 の意味は、p1 の x 座標を基準として p1 から p2 の方向に 1.0 の位置と解釈します。 同じように他の点も解釈すると、２つのポイントが与えられればそれに応じて図形が生成されるわけです。
　このような表現をプログラム内で表現するときには、直交座標系では困難というよりも無理に近いでしょう。このように場合によっては扱う座標系の選択を誤ると、とんでもなく変なプログラムになってしまいますので気を付けて下さい。

　さて、座標系の話はそれくらいとして、点とは一体何者なのでしょうか。代数的には最初に話した通りなのですが、これをプログラムで扱うとなると事情が変わってくるのです。

　いま、２つの点が与えられたときその２つの点が同じ位置であるか否かを検査するとしましょう。Ｐ１の座標を（x1、y1）とし、Ｐ２の座標を（x2、y2）としたとき、

　int is_same_point(x1,y1,x2,y2)
　double x1,y1,x2,y2;
　{
　　if(x1!=x2)return 0;
　　if(y1!=y2)return 0;

　　return 1;
　}

と記述すれば、確かに代数的には正解なのですが以前にもお話しましたように実数値の誤差の問題があります。もう１つの問題がむずかしいのです。

　『同じ位置というのはどういうことなのか？』これが最大の障壁なのです。地球規模の座標を扱っているときには、２つの点の距離が１００メートルでも同じと言えるかもしれません。原子程度の大きさのものを扱っているときには１ミクロンでも同じ位置とは言えないかもしれません。このように考えてみると『位置が同じ』は範囲が一意には決定できないのです。
　プログラムがどの程度の大きさの座標を扱うかによって、『同じ』の範囲が違ってきますので注意が必要です。ですから、たかだか１メートル程度のデータを扱うプログラムで『点の位置が同じか否か』を検査する関数を、原子の世界の座標を扱うプログラムにそのまま流用することはできないのです。

　点は点であって、点でないもののようにプログラム上では扱うしかありません。点から点に線を引くときには点は点として扱っても、上記のような場合にはある大きさを持ったものとして扱うのです。

　『同じ位置』の話をもう少し続けます。いま０．１の範囲内であれば同じと判断するとしましょう。このとき上の関数を次のように書いたとします。

　int is_same_point(x1,y1,x2,y2)
　double x1,y1,x2,y2;
　{
　　if(x1<x2-0.1)return 0;
　　if(x1>x2+0.1)return 0;
　　if(y1<y2-0.1)return 0;
　　if(y1>y2+0.1)return 0;

　　return 1;
　}

本当にこれでいいのでしょうか。自分でもよくこの書き方で済ましてしまうのですが、厳密には間違いです。

　（x1、y1）が（0.0、0.0）のとき、 （x2、y2）が（0.09、0.0）であればこの関数は正しく動作をしますが（0.09、0.09）のときでも同じと答えを出してしまいます。このときには２点の距離は 0.127279.... となるので範囲外です。本当ならば、

　int is_same_point(x1,y1,x2,y2)
　double x1,y1,x2,y2;
　{
　　double dx,dy;

　　dx=x2-x1;
　　dy=y2-y1;

　　if(dx*dx+dy*dy>0.01)return 0;

　　return 1;
　}

とするべきなのです。計算の無駄を省くため sqrt(x1*x1+y1*y1)>0.1 とはしない方がいいでしょう。

　回転のときに円弧の最小最大を求める話をしましたが、このときは円弧の中の注目すべき点のみを扱うことで、円弧の計算をせずに結果を導き出しました。これも点を使うことで問題を簡潔に処理する面白い例ではないでしょうか。

　余談ですが、物理の世界では物を点として扱って問題を簡単にすることがよくあります。ニュートンが万有引力の法則を発見した話は有名で皆さんも御存知かと思います。
リンゴが木からおっこちるのを見てあの法則や数式を一瞬で導きだした訳ではありません。もしそうだとすれば、犬の脱糞をみても導き出せたはずです。ニュートンはケプラーの膨大な観測データと、それから導きだされた法則をもとに血の滲む苦労の末にあの法則を発見したのですが、ニュートンが苦労したのは地球は点ではなく球（厳密には球ではありませんが....）であるというこのなのです。コンピュータなどのない時代のことですから球体と球体の計算を行なうにはあまりにも問題がむずかしくなるため、紙の上で計算するには別の手法が必要でした。
　そこで彼は球体と球体の引力の問題を、質量を持った点と点の問題として考えられないかと知恵をしぼることになりました。球が小さい球の集まりとして、そしてその球をどんどん小さくし、さらに球を点として扱ってもいいことを証明する努力をするのです。ここでニュートンは数学上の大きな発見をします。いまでは微分積分として当たり前な存在ですが、万有引力の発見以上の大発見かも知れません。彼のすごいのは引力の問題を解決するのに新しい数学をその手段として作ってしまったことです。結果、球は点として扱っても問題がないことが分ったのです。

　またまた余談ですが、現在のビデオテープは値段が安いので残り時間など気にもせずに新しいものに録画してしまいます。しかし、私が初めてビデオデッキを買った頃はテープ１本が５千円もしましたので、残りの部分にコマーシャルをカットしたり涙ぐましい努力をして録画したものです。あと数分というところでテープがなくなり、悲惨な経験をよくしたものです。今ではテープの残り時間が分るデッキがあるようですが、そのような機能のないデッキのときにはなんらかの手段でそれを算出しなければなりません（もっともテープには目盛がついていておおよその時間はわかりますが）。

　そこで、テープの使用した時間の計算方法を考えてみましょう。いまテープのリールの半径をＲ１、リールにテープを全部巻き取ったときの全体の半径をＲ２、テープの録画時間をＴとします。このとき全体の半径がｒのときのテープを使用した時間を求めてみましょう。

　テープの厚さをｔとすると、リールにテープを一回巻いたときのテープの長さは（厳密ではありませんが）、

　２πＲ１

２回目は、

　２π（Ｒ１＋ｔ）

ｎ回目は、

　２π（Ｒ１＋ｎｔ）

となるので、ｎ回全部巻いたときの総長は

　２π（Ｒ１＋Ｒ１＋ｔ＋Ｒ１＋２ｔ＋ ... ＋ｎｔ）

ですので、

　２π（ｎＲ１＋ｎ（ｎ＋１）ｔ／２）

となります。半径がｒのときの巻き数をｎ´とすると、

　２π（ｎ´Ｒ１＋ｎ´（ｎ´＋１）ｔ／２）

となります。全体の時間がＴですので、半径がｒのときの時間をＴ´とすると、

　Ｔ´２π（ｎ´Ｒ１＋ｎ´（ｎ´＋１）ｔ／２）
　―＝―――――――――――――――――――
　Ｔ　２π（ｎ　Ｒ１＋ｎ　（ｎ　＋１）ｔ／２）


　　　ｎ´Ｒ１＋（ｎ´＋１）ｔ／２
　　＝―＊――――――――――――
　　　ｎ　Ｒ１＋（ｎ　＋１）ｔ／２

ここで、ｎ＝（Ｒ２－Ｒ１）／ｔ、ｎ´＝（ｒ－Ｒ１）／ｔですので、上の式に代入す
ると、
　　　（ｒ　－Ｒ１）／ｔ　Ｒ１＋（（ｒ　－Ｒ１）／ｔ＋１）ｔ／２
　　＝―――――――――＊―――――――――――――――――――
　　　（Ｒ２－Ｒ１）／ｔ　Ｒ１＋（（Ｒ２－Ｒ１）／ｔ＋１）ｔ／２

　　　（ｒ　―Ｒ１）　Ｒ１＋（ｒ　－Ｒ１＋ｔ）／２
　　＝―――――――＊――――――――――――――
　　　（Ｒ２－Ｒ１）　Ｒ１＋（Ｒ２－Ｒ１＋ｔ）／２

分母、分子に２をかけて整理すると、

　　　（ｒ　―Ｒ１）　Ｒ１＋ｒ　＋ｔ
　　＝―――――――＊―――――――
　　　（Ｒ２－Ｒ１）　Ｒ１＋Ｒ２＋ｔ

　　　Ｒ１ｒ ＋ｒｒ　　 ＋ｒｔ　－Ｒ１Ｒ１－Ｒ１ｒ　－Ｒ１ｔ
　　＝―――――――――――――――――――――――――――
　　　Ｒ１Ｒ２＋Ｒ２Ｒ２＋Ｒ２ｔ－Ｒ１Ｒ１－Ｒ１Ｒ２－Ｒ１ｔ

　　　ｒｒ　　－Ｒ１Ｒ１＋ｒｔ　－Ｒ１ｔ
　　＝―――――――――――――――――
　　　Ｒ２Ｒ２－Ｒ１Ｒ１＋Ｒ２ｔ－Ｒ１ｔ


　　　　　ｒｒ（１＋ｔ／ｒ　）－Ｒ１Ｒ１（１＋ｔ／Ｒ１）
　　＝―――――――――――――――――――――――――
　　　Ｒ２Ｒ２（１＋ｔ／Ｒ２）－Ｒ１Ｒ１（１＋ｔ／Ｒ１）

ここでｔはＲ１、Ｒ２、ｒよりも小さいのでｔ／□の部分を無視すると、

　　　ｒｒ　　－Ｒ１Ｒ１
　　＝―――――――――
　　　Ｒ２Ｒ２－Ｒ１Ｒ１

となり、結果として、

　　　　　　ｒｒ　　－Ｒ１Ｒ１
　Ｔ´＝Ｔ＊―――――――――
　　　　　　Ｒ２Ｒ２－Ｒ１Ｒ１

となります。これでは読むのも面倒ですね。真面目に計算するとこうなるのですが、数列などを知らなくても簡単に同じ答えが導けるのです。円の面積が時間に比例しますので、全体のテープの厚みの面積Ｓは、

　Ｓ＝πＲ２Ｒ２－πＲ１Ｒ１

半径ｒのときの面積Ｓ´は、

　Ｓ´＝πｒｒ－πＲ１Ｒ１

となりますので、

　Ｔ´　Ｓ´ πｒｒ　　－πＲ１Ｒ１
　― ＝ ― ＝―――――――――――
　Ｔ　　Ｓ　 πＲ２Ｒ２－πＲ１Ｒ１

　　　　　　 ｒｒ　　－Ｒ１Ｒ１
　　　　　 ＝―――――――――
　　　　　　 Ｒ２Ｒ２－Ｒ１Ｒ１

となってめちゃくちゃ簡単になってしまうのです。

　話はかなりそれてしまいましたが、問題を解決するときに面を線に、あるいは線を点に、要するに別の角度から考えてみると以外と簡単なアルゴリズムが発見できることがあるものです。プログラミングを行なうときの要素には、記述の技法も大切な要素ですが、発想を転換できる柔軟な思考も大きな部分を占めています。

　それではまた次回。