外積の符号により、右か左かが判定できる

点 p=(px,py) , q=(qx,qy) を通る直線pq と、点r=(rx,ry)が与えられたとします。
q,rのpを起点とした相対的な位置ベクトルをQ=(qx-px,qy-py),R=(rx-px,ry-py)
としたとき、QとRの外積QRが

正ならば　rはpqの左側
負ならば　rはpqの右側

にあると言えます。

こんな簡単な式で判別できると言われても、にわかには信じられない
人も多いでしょう（私もそうでした）。
これは、以下のようにして証明することができます。

さて、ここで厄介なケースについて考えてみましょう。もし2つのベクトルが
同じ向き（あるいは正反対の向き）だったなら、それらの外積はどうなるでしょうか。
適当に値を入れてみれば分かるとおり、外積の値は0になります。
このような特殊なケースも、簡単に判別することができるのです。

また、外積は2回の乗算と1回の減算で求められるので、高速で計算誤差の入り込む余地が
少ないというのも重要な利点です。

凸包

それでは、外積を使って現実的な問題を解いてみましょう。
本日の問題は、凸包（convex hull）です。

凸包とは、点集合が与えられたとき、それらの点を全て含む最小の
凸多角形を求める問題です。
より直感的に、「板に釘をいくつか打ち込み、それらの釘を全て囲むように
輪ゴムをかける。縮んだ輪ゴムはどのような形になるか？」とも言い換えられます。
こちらの画像も参考にどうぞ。

凸包によって求められる多角形は、どの辺についても、その右側に点を持たない
という特徴を持ちます。これを使って凸包を求めることができます。
つまり、適当な点 a , b を点集合から取り出したとき、この図のように残りの点が全て
直線abの右側にあれば、線分abは求める多角形の辺だと言えるのです。
全ての2点についてこのチェックを行えば、凸包の全ての辺を洗い出すことができます。

このアルゴリズムは非常に単純なものの、計算量は大きくなってしまいます。
点集合の大きさをnとしたとき、そこから2点を取り出す組み合わせはn(n-1)通りあり、
それぞれについて残るn-2点が右側にあるかチェックするので、合計すると
O(n^3)のオーダになってしまいます。

もっと高速な（外積を利用した）凸包のアルゴリズムもあるのですが、
その話はまたいつか。

担当 : 田山