三角形と点～Project Euler Problem 102～ - みをつくしのひとりよがり

最近，Project Eulerなる数学の問題集サイトに出会いました．問題集といっても，数学とプログラミングを組合せて解くある種「力技」なものなので，純粋な数学の考え方＋効率の良いアルゴリズムを考えるという問題になっています．
問題によっては，高校数学でも十分解けるものがあり，今回はその 1つをちょこっとピックアップしてみようと思います．
ちなみに，わたしは Excelのマクロレベルぐらいしかできないレベルです．

ポイント(解答)だけを書けば，こんなに長くはならないのですが，いろいろ考えてみたことも書いたので長くなってます．

日本語訳されているサイトはこちら．
Project Euler - PukiWiki

問題(Problem 102)

元となるのはこちら．
Problem 102 - Project Euler

3つの異なる点が -1000 ≤ x, y ≤ 1000 かつ三角形となるように, デカルト平面上にランダムに与えられる.
以下の2つの三角形を考える.

A(-340,495), B(-153,-910), C(835,-947)
X(-175,41), Y(-421,-714), Z(574,-645)

三角形ABCが原点を内部に含み, XYZは原点を内部に含まないことが確かめられる.

27Kのテキストファイルにランダムな1000個の三角形が適当なフォーマットのもと含まれている.
内部に原点を含む三角形の数を答えよ.

この問題を参考に，以下のようなことを考えてみます．
$xy$ 平面上に適当に描かれた $\triangle ABC$ と点 $P$ について，点 $P$ が $\triangle ABC$ の内部にあるかどうかを判別する方法を考えよ．

試行錯誤

※今回この節に関する絵は載せません．頭の中でイメージしてみてください．こういうのもいい頭のトレーニングになるのではと．

どんな「道具」が使えるかを通勤がてら考えてみました．
もし頭の中で考えてることがふき出しのように見られたら引かれそうですが．

内接円(内心)との位置関係
外接円(外心)との位置関係
点と直線の距離

1や 2は明らかにダメ(カバーしきれない部分があったり，余計にカバーする部分があったりするから)です．
ただ，1で内接円の中心から辺に垂線を下す(＝内接円の半径)というイメージから，3が出てきました．
ある 1つの辺と対向する頂点との距離( $= d_{BC}(A)$ )とその辺と点 $P$ との距離( $= d_{BC}(P)$ )の大小関係で示せるのではないか？という発想までいきました．が，距離を考えてしまうと，三角形の外側にも同じ距離の点が現れてしまうので NGだということになりました．*1

でも，この NGのおかげで「同じ側にあればいい」という発想にたどり着きました．あとから考えれば，非常に当たり前のことなんですが，このときはいろいろと寄り道してしまいました．そして，この「同じ側」ということを高校数学の言葉で表現すると，「正領域・負領域」の考え方を使うということになります．

正領域・負領域

単純に言えば，「直線の上側にあるか下側にあるか」という話です．直線の方程式を $ax+by+c=0$ の形に変形しておき，さらにその式を $f(x,y)$ と置いたとき，
　 $f(x,y)>0$ なる領域を正領域， $f(x,y)<0$ なる領域を負領域とよぶ．

となります．上側と下側と書いていますが，係数 $a$ や $b$ の正負によって( $f(x,y)$ の選び方によって)上側にもなり，下側にもなります．ただ，同じ $f(x,y)$ について，符号が同じであれば同じ側にあるということがいえるのです．

これが基本的な考え方になります．
つまり，
　点 $A$ の対向となる直線 $BC$ について，点 $A$ と点 $P$ が同じ側にある．
　点 $B$ の対向となる直線 $CA$ について，点 $B$ と点 $P$ が同じ側にある．
　点 $C$ の対向となる直線 $AB$ について，点 $C$ と点 $P$ が同じ側にある．

これらが同時に満たされていれば，点 $P$ は $\triangle ABC$ の内部にあるといえるわけです．

アルゴリズム

AIとかになれば，このような処理を使わなくても判断できるのかもしれませんが，コンピューターには数値で判断させなければなりません．あと，人間が思っている以上にコンピューターへの指示は細かく分けてあげないといけません．
たとえば，「飲む」という動作をするにしても，

コップを見つける．
コップ(の持ち手)まで手を動かす．
コップをつかむ．
その手を持ち上げる．
コップが口に当たるように手を動かす．
コップを傾ける．
コップの傾きを戻す．
コップを口から離すように手を動かす．

…(1～4の逆の動作をする)

のように分解してコンピューター(機械)には指示しなければなりません*2．このように処理させる手順を考えることがポイントで，アルゴリズムを作るという作業になります．

ただ，アルゴリズムは必ずしも前から順番に作る必要はありません．途中の作業をパーツとして作っておいて，それらを組み合わせるということも可能です．これは普通に問題を解くときにもやっていることかもしれません．

上の節の最後で符号が同じであれば同じ側にあると書きましたが，これは点 $A(A_x, A_y)$ と点 $P(P_x,P_y)$ のそれぞれに対する値の積で正であること．すなわち，
　 $f(A_x,A_y) \cdot f(P_x,P_y) > 0$

を条件式として与えることができます．

ここまでくると， $f(x,y)$ に相当する直線の方程式を書き下せさえすればよさそうです．通常，2点を通る直線の方程式(ここでは直線 $BC$ を考えると)といえば，
　 $\displaystyle{ y - B_y = \frac{C_y - B_y}{C_x - B_x} (x - B_x) }$

という形ですが，これを変形して，
　 $(C_x - B_x)(y - B_y) - (C_y - B_y)(x - B_x) = 0$

としてしまいます．展開してもいいのですが，正領域・負領域を判断するだけであれば，この式までで十分です．さらに，この形は $ax+by+c=0$ の形になっているので， $a=0$ や $b=0$ のような式にも対応できます．人間と同じで，機械も「0で割る」という操作は無理なのです．
　
そして，残りの 1点が対向にある頂点ということになるので，
　 $f_{BC}(A_x,A_y) = (C_x - B_x)(A_y - B_y) - (C_y - B_y)(A_x - B_x)$

と
　 $f_{BC}(P_x,P_y) = (C_x - B_x)(P_y - B_y) - (C_y - B_y)(P_x - B_x)$

の積を考えればよいわけです．あとは，3点 $A, \ B, \ C$ を順次入れ替えて，すべての式で積が正になることが確認できれば，点 $P$ は内部にあると判定できます．
上で問うていた「判別法」としては，これが 1つの解となります．

アルゴリズムと計算量

1つ目や 2つ目の判定で負という結果がでれば，その時点でこの組み合わせは NGと判断できる(残り 2つの判定はするだけムダ)ようになります．こうすると，全体の計算量を抑えることができます．
ただし，その分(1つ目の分岐，2つ目の分岐というように分けていく)だけ，同じような処理(コード)をくり返し書くことになります．なので，敢えて 3つ全部を繰り返してから判断するというアルゴリズムをとるという場合もあります．

アルゴリズムの正解は 1つとは限りませんし，上で記したような解法も 1つとは限らない(この解法が最適とも限らない)わけです．

上で書いた内容は今回の問題の本筋であり処理の本筋でもありますが，まだ「与えられたデータを読み込む」「読み込んだ 3点のデータを一度クリアする(次のデータを読み込ますために)」「判定した結果(内部にあると判定された数)を記憶(カウント)する」といった処理も組み合わせなければなりません．

アルゴリズムという点では，過去のコレが該当しますね．
2014年センタ試験数学IIB第6問の解説もどき～その１～ - 理系男子の独り善がり
 2014年センタ試験数学IIB第6問の解説もどき～その２～ - 理系男子の独り善がり

いまは小学生でもアルゴリズムを勉強する時代になってきたので，大人も少しは触れておかないとダメですね．Project Eulerの問題は，またいいのがあれば取り扱ってみようと思います．

*1:その辺が垂直二等分線となるような 2点が同じ距離をもつ点となるから

*2:さらに指の動きなど細かい指示が必要になることも考えられます．また，実はこれだけの指示では，口の中に液体を入れる．液体を飲み込むという動作がないので，「飲む」という動作には完全になっていないって気づきましたか？笑