プログラマーが使う高校数学（その３）

平面上に重ならない2点 ${\displaystyle P_1=(x_1,y_1)}$ と ${\displaystyle P_2=(x_2,y_2)}$ をとり、水平線 ${\displaystyle L_h:y=h}$ の上を動く注目点 ${\displaystyle Q=(x,h)}$ からどちらが近いかを求めます。具体的なイメージとしては、ラスタ画像で横一列のピクセルを順番に調べながら近い方の点に応じた処理をする（そしてそれを全行で繰り返す）ような感じです。単純に距離を都度比較して判定するだけでも目的は達成できますが、効率が悪すぎるのでもっといい方法を模索してみましょう。

固定された2点に対して任意の座標からどちらが近いかは、2点間の垂直二等分線 ${\displaystyle L_{12}}$ で分かれるどちらの半平面にあるかに還元できます。

${\displaystyle L_{12}:(y_2-<!--\; -\; -->y_1)y+(x_2-<!--\; -\; -->x_1)x+\frac{1}{2}(x_1^2-<!--\; -\; -->x_2^2+y_1^2-<!--\; -\; -->y_2^2)=0}$   ...   Eq.1

さらに水平線 ${\displaystyle L_h}$ 上に限定すると、 ${\displaystyle L_{12}}$ と ${\displaystyle L_h}$ の交点X座標 ${\displaystyle x_{12}}$ を境にどちらの半直線にあるか、ということになります。Eq.1に ${\displaystyle y=h}$ を代入して ${\displaystyle x}$ について解けば ${\displaystyle x_{12}}$ が求まります（※ ${\displaystyle x_2=x_1}$ のときは ${\displaystyle L_{12}}$ も水平線になるので交点がありません）。

${\displaystyle x_{12}=\frac{x_2^2-<!--\; -\; -->x_1^2+y_2^2-<!--\; -\; -->y_1^2-<!--\; -\; -->2(y_2-<!--\; -\; -->y_1)h}{2(x_2-<!--\; -\; -->x_1)}}$   ...   Eq.2

では、もう1点 ${\displaystyle P_3=(x_3,y_3)}$ を追加した場合はどうなるでしょうか。

考えなければならない垂直二等分線が3本（ ${\displaystyle L_{12}}$ 、 ${\displaystyle L_{13}}$ 、 ${\displaystyle L_{23}}$ ）に増え、水平線 ${\displaystyle L_h}$ 上の交差X座標（ ${\displaystyle x_{12}}$ 、 ${\displaystyle x_{13}}$ 、 ${\displaystyle x_{23}}$ ）の関係も複雑になります。点の数が ${\displaystyle n}$ 個なら組み合わせとして ${\displaystyle n(n-<!--\; -\; -->1)/2}$ 本になり簡単には扱いきれません。そこで、少し視点を変えて距離に着目してみましょう。点 ${\displaystyle P_i(i=1,2,\dots <!--\; \dots \; -->,n)}$ から水平線 ${\displaystyle L_h}$ 上の任意の点 ${\displaystyle Q=(x,h)}$ までの距離は ${\displaystyle \sqrt{(x_i-<!--\; -\; -->x{)}^2+(y_i-<!--\; -\; -->h{)}^2}}$ と表せます。今 ${\displaystyle h}$ は定数なので変数 ${\displaystyle x}$ の二次関数として次を定義してみます。

${\displaystyle F_i(x):=(x_i-<!--\; -\; -->x{)}^2+(y_i-<!--\; -\; -->h{)}^2}$   ...   Eq.3

加えて、 ${\displaystyle P_i}$ は ${\displaystyle x_i}$ が互いに異なり小さい順に並んでいると仮定します。つまり ${\displaystyle x_1<<!--\; <\; -->x_2<<!--\; <\; -->\cdots <!--\; \cdots \; --><<!--\; <\; -->x_n}$ です（※X座標が同じ点はY座標が水平線に近い方しか関与しないのであらかじめ除外しておき、小さい順になるよう番号を振り直す感じです）。この関数の集合 ${\displaystyle \{F_i(x)|i=1,2,\dots <!--\; \dots \; -->,n\}}$ を使うと、水平線 ${\displaystyle L_h}$ 上の任意の点 ${\displaystyle Q=(x,h)}$ から最も距離が近い点 ${\displaystyle P_k}$ を探す問題が、入力 ${\displaystyle x}$ において最も下側にある関数 ${\displaystyle F_k(x)}$ を見つける問題に読み換えることができます。とは言え ${\displaystyle x}$ が与えられるたびに都度すべての ${\displaystyle F_i(x)}$ を比べようとすると ${\displaystyle n(n-<!--\; -\; -->1)/2}$ 回かかってしまうので、水平線上で各点 ${\displaystyle P_i}$ が最も近くなる区間の集合として先に計算することにします。

最初の2点 ${\displaystyle P_1,P_2}$ に対しては、Eq.2で求めた ${\displaystyle x_{12}}$ で2つの区間 ${\displaystyle (-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->},x_{12}],[x_{12},\mathrm{\infty <!--\; \infty \; -->})}$ に分かれます。ここに ${\displaystyle P_i}$ を追加することを考えましょう。 ${\displaystyle F_3(x)}$ が ${\displaystyle F_1(x),F_2(x)}$ とどのように交差するか（ ${\displaystyle x_{12},x_{23},x_{13}}$ の関係性）は、次のような手順で調べることができます。

1. ${\displaystyle F_3(x_{12})><!--\; >\; -->F_2(x_{12})\to <!--\; \to \; -->x_{23}><!--\; >\; -->x_{12}\to <!--\; \to \; -->(-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->},x_{12}],[x_{12},x_{23}],[x_{23},\mathrm{\infty <!--\; \infty \; -->})}$
2. ${\displaystyle F_3(x_{12})\le <!--\; \le \; -->F_2(x_{12})\to <!--\; \to \; -->x_{13}\le <!--\; \le \; -->x_{12}\to <!--\; \to \; -->(-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->},x_{13}],[x_{13},\mathrm{\infty <!--\; \infty \; -->})}$

とくにケース2を見ると ${\displaystyle F_2(x)}$ が区間を持たなくなり、水平線 ${\displaystyle L_h}$ と点 ${\displaystyle P_2}$ が最も近くなる位置は存在しなくなります。しかも ${\displaystyle P_4,P_5,\cdots <!--\; \cdots \; -->,P_n}$ を追加したとしても変わることはありません。次々と点を追加していって作られた分割済みの区間 ${\displaystyle (-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->},x_{i_1{i}_2}],[x_{i_2{i}_3},x_{i_3{i}_4}],\dots <!--\; \dots \; -->,[x_{i_{m-<!--\; -\; -->2}{i}_{m-<!--\; -\; -->1}},x_{i_{m-<!--\; -\; -->1}{i}_m}],[x_{i_{m-<!--\; -\; -->1}{i}_m},\mathrm{\infty <!--\; \infty \; -->})}$ に点 ${\displaystyle P_j}$ を追加するたびに、 ${\displaystyle F_j(x)}$ がどこの区間をより細かく分割するのかを右から順に一対一で比較して探すことになります。上記のケース2のように ${\displaystyle F_j(x)}$ が入り込む位置によって、それより値の大きい区間は消えて紐付けられていた点も以降は考慮する必要がありません。

このように、右から比較して一度でも通り過ぎた区間に対応する点は考慮する必要がない、という性質から ${\displaystyle P_1,P_2,\cdots <!--\; \cdots \; -->,P_n}$ に対して ${\displaystyle L_h}$ 上の区間を求める処理は比較と交差X座標の計算を合わせても ${\displaystyle n}$ の定数倍程度の回数で済みます。ラスタ画像では ${\displaystyle n\sim <!--\; \sim \; -->{10}^4}$ の入力を扱うことも多く、 ${\displaystyle n(n-<!--\; -\; -->1)/2\sim <!--\; \sim \; -->{10}^8}$ と ${\displaystyle nc\sim <!--\; \sim \; -->{10}^{4}c(c\ll <!--\; \ll \; -->n)}$ の違いは歴然です。使われている数学自体は簡単なはずなのに、この手法に初めて触れたとき衝撃を覚えました。

今回は少しプログラミング（アルゴリズム）寄りの内容になりました。テーマとして扱った「注目している位置から最も近い対象を探す」という処理はなかなか奥が深く、対象が多くなったとしても如何に効率良く探索できるかが常に問われているのです。以上、お付き合いいただきありがとうございました。プログラマーが日々何に取り組んでいるのか、一端だけでも知っていただけたら幸いです。