この記事は、 Calculating the Distance Between Points in “Wrap Around” (Toroidal) Space を自分用に翻訳したものを 許可を得て 公開するものである。
ソース中にコメントの形で原文を残している。 誤字や誤訳などを見つけたら今すぐ Pull requestだ!
2次元上の2点間の距離を求めたいとしましょう、ただし点は古いテレビゲームのような“ラップアラウンド”の世界にあります – スクリーンの上下左右から出ると、反対側から現れるのです。
この世界は、ドーナツとしても知られるトロイドのような形をしています。 空洞のドーナツの面にいることを想像すると、ちょうど同じ振る舞いをするでしょう。 あなたが“下“に行くと、先ほど”上“だと考えていたところに着きます。 あなたが“上“に行くと、先ほど”下“だと考えていたところに着きます。
このような世界で、どのように2点間の距離を求めればいいのでしょうか？
下の状況で赤い地点と緑の地点の距離を求めようとしているとしましょう:
1つの方法として、点を1つ選んで(今回は赤にします)、下のようにセルを囲むよう8回クローンする、というのがあります。 緑の点からの距離を9つの赤い点でそれぞれ計算し、最も小さいものが答えになります。
最短距離を計算するために9回の計算をするというのは望ましいものではありません。 平方根の計算を避けるために距離の二乗を用いて計算することができますが、効果は微々たるものです。
次元が上がるとより悪いことになります。 3次元では最短距離を求めるのに27回の距離計算が必要になり、4次元では距離計算は81回になります！
幸運にもよりよい方法があります。
世界(画像)の大きさが1単位だと(言い換えると、テクスチャUVを扱っていると)しましょう。 画像の赤い点の9つのコピーを見ると、それらは各座標軸に -1、+0、+1 を足した9つの組み合わせであることがわかります。 -1、+0、+1 をx、y座標に足す全ての可能な組み合わせが赤い点の正しい座標になります。
距離の公式を見ると、各座標軸の値を別々に最小化すれば、それが全体で最小距離にもなることがわかります。
\( d = \sqrt{(x_2-x_1)^2+(y_2-y_1)^2} \)
よって、各座標を別々に最小化するのがより良い方法です。
x座標から1を引いた、そのままにした、足したときに赤と緑の点のx座標の距離が最小になるなら、それが求めるx座標です。
x座標の1次元距離が最小の赤い点のx座標が目的の位置になります。
y座標でも同じように目的の位置を探します(さらに高次元の他の座標軸でも同様にします)。
これがラップアラウンド空間の点の距離を得るために距離公式に当てはめる点になります。
実はさらに良くできます。
各座標軸を別々に処理するため、2点間の1次元距離の絶対値を計算できます。 距離が0.5より大きい場合、その座標の実際の距離は 1 - 距離 です。
直感的に、1次元の繰り返し空間にいる場合、AからBへの道のりが半分より長いなら間違った道を進んでいるということであり、もう一方の道の方が短いということになります。 もう一方の道の距離は、ある点からそこに戻ってくるまでの距離が1であるため、1から先ほど計算した距離を差し引いたものです！
以上を各軸に対して行い、実際の距離を得るために距離公式でそれらの1次元距離を使います。
これによりどの組み合わせが最も近い点かを明示的に把握することなく距離を最小化できます。
さらに重要なことに、トロイダル空間(ドーナツ空間)における2点間の距離を効率的に計算することができます！
計算量は非常に改善されます。 次元の数に対して\(O(3^N)\)だったものが線形\(O(N)\)になります。
こちらが2次元で動作するC++の例です。
float ToroidalDistance (float x1, float y1, float x2, float y2)
{
float dx = std::abs(x2 - x1);
float dy = std::abs(y2 - y1);
if (dx > 0.5f)
dx = 1.0f - dx;
if (dy > 0.5f)
dy = 1.0f - dy;
return std::sqrt(dx*dx + dy*dy);
}
私はタイル状に並べられるテクスチャを作るときにこの問題を思いつきました。 私はタイル状に並べても円が他の円と近づきすぎないように円を配置する必要がありました。
上記の計算から点の距離を計算するための基礎的なツールが得られました。 点のトロイダルな距離から円の半径を引いて、それぞれが近づきすぎないようにしました。
そうして、タイル状に並べても距離の制約を維持し続ける画像ができました。
こちらが画像の例です:
こちらは並べたものです:
