ユークリッド距離

euclidean-distance.png

ユークリッド距離とか難しく言ってるけど、フツーの距離だから安心せよ。
マンハッタン距離との区別をつけるためだけにこんなかっこつけた言い方をしてるとしか思えません。
ただし特別なのは、何次元でもいいってこと。
ふつーは3次元までしか考えられないよね?
2次元の場合

(1)
\begin{align} d=\sqrt{(x_a-x_b)^2+(y_a-y_b)^2} \end{align}

3次元の場合

(2)
\begin{align} d=\sqrt{(x_a-x_b)^2+(y_a-y_b)^2+(z_a-z_b)^2} \end{align}

つまりn次元の場合
点が2つあるとする
$p=\{x_{1p},x_{2p},....,x_{np}\}$
$q=\{x_{1q},x_{2q},....,x_{nq}\}$

(3)
\begin{align} d=(\sum_{i}^{n}|x_{ip}-x_{iq}|^m)^{\frac{1}{n}} \end{align}

3次元の距離を高速に見積もる方法

もしx,y,zの各成分ベクトルがのゼロでない成分を1個だけ持ってるようなベクトルだったら
ユークリッド距離とマンハッタン距離は完全に一致します。
これがこの見積もりの最もラッキーだった場合です。
最もラッキーじゃなかった場合は
x,y,zの各ベクトルの長さがすべて同じだった場合です。
マンハッタン距離は

d+d+d=3d

なのに、実際のユークリッド距離は

(4)
\begin{align} \sqrt{3}d \end{align}

です。
つまり最悪の場合$3/\sqrt{3}=1.7$倍、見積もりが外れてる場合があるってことです。

やり方★

  1. abs(dx),abs(dy),abs(dz)の3つの値を求める
  2. その3つの値をソートする
  3. 距離を見積もる 距離=max+med/4+min/4

この方法で見積もると、プラスマイナス13%の誤差になります
ここから更に精度を上げるならばというかまとめると

(5)
\begin{align} max+\frac{1}{4}med+\frac{1}{4}min\{ has \pm 13 \% \}\\ max+\frac{5}{16}med+\frac{1}{4}min \{ has \pm 9 \% \}\\ max+\frac{11}{32}med+\frac{1}{4}min \{ has \pm 8 \% \} \end{align}

どの係数も分母が2のべき乗です。
ということはビットシフト演算が使えるので割り算しなくて済みます。
分子については加算とシフトで掛け算も防げます
もし扱うベクトルがfloat型の小さい値ならば、何十倍かしてint型にしましょう。
もし扱うベクトルの長さが100より大きかったら十分です。この手法を使っても大して誤差がでないでしょう。
given that we are only accurateto ±8% to begin with.
If the span is, say, 1.0, then we need to scale up.
More generally, this algorithm is an alternative to finding the square root of the sum of three squares, which need not mean distance,
or anything spatial at all.
次のコードは±13%のバージョンのコードです。
where scaling is needed. A
scale of 1024 is used, which can be accomplished by shifting by 10.
10シフトしているのは1024倍にスケーリングしているだけです。
This means that the code contains no multiplies, divides, or square roots, and
is all in fixed point.

double approxLength3D(double dx,double  dy,double  dz){
int maxc, medc, minc;
//1024倍してfloatのちっさい値をint型に変える
maxc = abs(dx<<10);
medc = abs(dy<<10);
minc = abs(dz<<10);
//ソートします. Need only find max.
if( maxc < medc){
 swap(maxc, medc);
}
if( maxc < minc){
  swap(maxc, minc);
}
//Compute 1/4 of med & min in 1 step.
medc = medc + minc;
maxc = maxc + medc>>2;//1/4する
//スケーリングしたのを元に戻します
return ( (float)maxc>>10 );
}

より高速に★距離を見積もる方法

3DCGの計算において、距離の計算は頻繁に発生するし、大体においてそこまで正確でなくてもいい場合が多い。
平方根の関数(C++だったらsqrt())にはdoubleの引数を必要とする。
スピードアップするためには、int⇔doubleの型変換をやめることだ。
2次元の場合
cは未知の係数とする

(6)
\begin{equation} d=c_1・|x_a-x_b|+c_2・|y_a-y_b| \end{equation}

distance euclid graphic_gems

サポートサイト Wikidot.com distanceeuclidgraphic_gems