同一直線上の3点

久野君たちの努力により, Beautiful Codeの翻訳がでた. 以前 三省堂の洋書の棚にあるのを見たことはあったが, その時はパスした.

翻訳をみると, なにしろ多くの人がそれぞれのプログラム言語で書いた自分のプログラムを(それもかなり大きい部分を)自讚しているから, 読むのが大変そうである.

短くて面白かったのは, 33章「『本』のためにプログラムを書く」であった. 要するに平面上の3点A, B, Cの座標が与えられた時, その3点が同一直線上にあるかを判定するプログラムを書くのだ.

私がやっても多分こういうアプローチになるであろうという風に話は展開していく.

まずA,Bの2点を通る直線の式を決め, 点Cがそれに乗っているかを問うもの. これは最初の2点がy軸と平行な線上にあるときの始末が面倒.

次はABを通る直線の勾配と, ACを通る直線の勾配を計算し, それらが一致するかを見るもの. 勾配が無限大になるときはnilを返すようにすると, nil同士もeqで比べればtになるので便利なようだが, 気持は悪い.

3番目はBCの距離a, CAの距離b, ABの距離cを計算し, a,b,cを大きさの順にソートし, 最大の距離が残りの2つの距離の和になるかどうかを見る. この難点はPythagorasの定理で距離を求めるのに関数sqrtを使うことだ. 誤差は避けられない.

このようにして, 最後に辿り着いたのは, 3点で構成する三角形の面積を求め, それが0なら三角形はつぶれて3点は同一直線上にあることが分かるというもの.

たしかに高校生のとき, 三角形 ABC の面積は行列式

|Ax Ay 1|
|Bx By 1|
|Cx Cy 1|

の1/2と習った. 面積が0かとうかを見るのだから, 1/2はいらない, 正負も問題にならないから, A,B,Cを反時計まわりにおくことにこだわることもない.

(Ax*By+Bx*Cy+Cx*Ay)-(Ax*Cy+Bx*Ay+Cx*By)

の計算だから誤差も何もない. これで決りだ.

今年の夏のプロシンのテーマは「プログラムの品格」のようなものだ. 本書もひとしきり話題になりそうな予感.