皆さん、こんにちは。システム商品開発グループの入澤です。
暖かな日差しで満開に咲いた桜が、強風と雨で儚く散っていきました。暦の上では春が終わりを告げて夏に向かっていきます。着る服に困る今日この頃です。
さて、本題に進みまして今回も数学のお話に少々お付き合いください。グラフィクスの処理に不可欠な計算の一つに「注目している位置から最も近い対象を探す」というものがあります（ベクタ／ラスタの種類に限らず）。人間は画像をぱっと見ただけで全体の位置関係を瞬時に把握しておおよその近さを無意識に比較できます。しかし、すべてが数値だけで表現されたプログラムの世界ではそうもいきません。例えば、次のような状況を考えてみましょう。
平面上に重ならない2点 と をとり、水平線 の上を動く注目点 からどちらが近いかを求めます。具体的なイメージとしては、ラスタ画像で横一列のピクセルを順番に調べながら近い方の点に応じた処理をする（そしてそれを全行で繰り返す）ような感じです。単純に距離を都度比較して判定するだけでも目的は達成できますが、効率が悪すぎるのでもっといい方法を模索してみましょう。
固定された2点に対して任意の座標からどちらが近いかは、2点間の垂直二等分線 で分かれるどちらの半平面にあるかに還元できます。
... Eq.1
さらに水平線 上に限定すると、 と の交点X座標 を境にどちらの半直線にあるか、ということになります。Eq.1に を代入して について解けば が求まります（※ のときは も水平線になるので交点がありません）。
... Eq.2
では、もう1点 を追加した場合はどうなるでしょうか。
考えなければならない垂直二等分線が3本（ 、 、 ）に増え、水平線 上の交差X座標（ 、 、 ）の関係も複雑になります。点の数が 個なら組み合わせとして 本になり簡単には扱いきれません。そこで、少し視点を変えて距離に着目してみましょう。点 から水平線 上の任意の点 までの距離は と表せます。今 は定数なので変数 の二次関数として次を定義してみます。
... Eq.3
加えて、 は が互いに異なり小さい順に並んでいると仮定します。つまり です（※X座標が同じ点はY座標が水平線に近い方しか関与しないのであらかじめ除外しておき、小さい順になるよう番号を振り直す感じです）。この関数の集合 を使うと、水平線 上の任意の点 から最も距離が近い点 を探す問題が、入力 において最も下側にある関数 を見つける問題に読み換えることができます。とは言え が与えられるたびに都度すべての を比べようとすると 回かかってしまうので、水平線上で各点 が最も近くなる区間の集合として先に計算することにします。
最初の2点 に対しては、Eq.2で求めた で2つの区間 に分かれます。ここに を追加することを考えましょう。 が とどのように交差するか（ の関係性）は、次のような手順で調べることができます。
とくにケース2を見ると が区間を持たなくなり、水平線 と点 が最も近くなる位置は存在しなくなります。しかも を追加したとしても変わることはありません。次々と点を追加していって作られた分割済みの区間 に点 を追加するたびに、 がどこの区間をより細かく分割するのかを右から順に一対一で比較して探すことになります。上記のケース2のように が入り込む位置によって、それより値の大きい区間は消えて紐付けられていた点も以降は考慮する必要がありません。
このように、右から比較して一度でも通り過ぎた区間に対応する点は考慮する必要がない、という性質から に対して 上の区間を求める処理は比較と交差X座標の計算を合わせても の定数倍程度の回数で済みます。ラスタ画像では の入力を扱うことも多く、 と の違いは歴然です。使われている数学自体は簡単なはずなのに、この手法に初めて触れたとき衝撃を覚えました。
今回は少しプログラミング（アルゴリズム）寄りの内容になりました。テーマとして扱った「注目している位置から最も近い対象を探す」という処理はなかなか奥が深く、対象が多くなったとしても如何に効率良く探索できるかが常に問われているのです。以上、お付き合いいただきありがとうございました。プログラマーが日々何に取り組んでいるのか、一端だけでも知っていただけたら幸いです。