点とバウンディングボックス（超長方形hyper rectangle）との距離を求める

超次元点と超次元長方形の距離を求めるメモ．

距離の考え方としては以下になる．

バウンディングボックスの外に点がある場合は，その最短距離の求め方
バウンディングボックス内に点がある場合は，距離0とする．
逆に，最長距離の求め方

これはクラスタリングなどの最近傍を求めるような，とくにk-d treeを使った近傍探索に使える．

最短距離を求める

ある1次元で考えると距離を考えやすい．

バウンディングボックス左側に対象データがある場合

つまり，以下の数直線の状況，データとバウンディングボックスの位置関係が$x_i < \text{BB_min}_i$の場合を考える．

差の絶対値でなく符号付きの差を考える．以下4パターンが考えられる．

$x_{i} - \text{BB_max}_{i}$ : -（負）
$\text{BB_max}_{i} - x_{i}$: +(正)
$x_{i} - \text{BB_min}_{i}$ : -（負）
$\text{BB_min}_{i} - x_{i}$: +(正)

最短距離を考えるとバウンディングボックスの最大値との差を見ている，上1,2番目は対象外になり以下2パターンになる．

$x_{i} - \text{BB_min}_{i}$ : -（負）
$\text{BB_min}_{i} - x_{i}$: +(正)（最短距離）

符号込みで考えると最後のパターンが正しい．

$\text{BB_min}_{i} - x_{i}$

※位置関係が，バウンディングボックスの最小値が正にあり，データがその左側の正にあってもこの関係は変わらない．（$x_{i} < \text{BB_min}_{i}$は常に成立）

バウンディングボックス右側に対象データがある場合

次に，バウンディングボックス右側に対象デ-タがある場合を考える．つまり，データとバウンディングボックスの位置関係が$ \text{BB_max}_{i} < x_{i} $の場合を考える．

これも同様に，距離関係になり得るペアは4パターンある．

$\text{BB_min}_{i} - x_{i}$: -(負)
$x_{i} - \text{BB_min}_{i}$ : +（正）
$\text{BB_max}_{i} - x_{i}$: -(負)
$x_{i} - \text{BB_max}_{i}$ : +（正）

最短距離を考えると，今度はバウンディングボックスの最小値との差を見ている，上1,2番目は対象外になり以下2パターンになる．

$\text{BB_max}_{i} - x_{i}$: -(負)
$x_{i} - \text{BB_max}_{i}$ : +（正）（最短距離）

符号込みで考えると最後のパターンが正しい．

$x_i - \text{BB_max}_i$

※バウンディングボックスの最大値が負にあり，データがその右側の負にあってもこの関係は変わらない．（$\text{BB_max} < x_{i}$は常に成立）

2つのパターンをまとめる

データがバウンディングボックスの左側または右側，この2つの状況をまとめて考える．クロス表のようなものを考えると以下の関係になる．

\	左側	右側
$\text{BB_min}_{i} - x_{i}$	正	負
$x_{i} - \text{BB_max}_{i}$	負	正

つまり，2つの差を計算して正になるものが距離として正しい値になる． ifチェックでも判定できるがmaxを使えば数式で1つにまとめられる． 1つの軸の差を$\mathrm{sd}_{i}$とすると

$\mathrm{sd}_{i} = \mathrm{max}(\text{BB_min}_{i} - x_{i}, x_{i} - \text{BB_max}_{i}), (\text{for } i = 1, \cdots , d)$

ここまでくればp-ノルム距離（ミンコスキー距離）を簡単に求められる．

$D = \left( \sum_{i}^{d} \mathrm{sd}_{i}^{p} \right)^{1/p}, (p >0, \neq \infty)$

バウンディングボックス内部にあるかを判定する

この符号付き距離を使って中にあるかどうかを判定できればいい．

このときバウンディングボックスの上限下限との符号付き距離は以下のようになる．

\	sign
$\text{BB_min}_{i} - x_{i}$	負
$x_{i} - \text{BB_max}_{i}$	負

もし上限下限上にある場合は0となる．

\	sign
$\text{BB_min}_{i} - x_{i}$	0
$x_{i} - \text{BB_max}_{i}$	0

つまり， $\text{BB_min}_{i} - x_{i}$, $x_{i} - \text{BB_max}_{i}$ の両者が0以下になれば内部にあり距離0と返せばいい．

これは外にある場合の距離$\mathrm{sd}_{i}$と０の最大値をみることで計算可能．

$\begin{eqnarray} \text{sd}_{i} &=& \mathrm{max}( x_{i} - \text{BB_max}_{i}, \text{BB_min}_{i} - x_{i})\\ \hat{\text{sd}}_{i} &=& \mathrm{max}(0,\mathrm{sd}_{i})\\ D &=& \left( \sum_{i}^{d} \hat{\mathrm{sd}}_{i}^{p} \right)^{1/p}, (p >0, \neq \infty) \end{eqnarray}$

もしデータ点$\vec{x}$がバウンディングボックス内であると $\hat{\text{sd}}_{i}$が全て0となり距離$D$も0となる．

python codeで実装

import numpy as np

point = [-1, -1]
class BB():
    def __init__(self, lower, upper):
        self.mins = np.minimum(lower,upper)
        self.maxes = np.maximum(lower,upper)

sd_hat = np.maximum(0,np.maximum(self.mins-x,x-self.maxes))
p = 2
D = sp.sum(sd_hat**p)**(1/p)

ちなみにこのコードは，scipy.spatial.kdtree.py中のmin_distance_point関数で定義されている．

scipy/kdtree.py at v0.14.0 · scipy/scipy · GitHub

最長距離を求める

最短距離同様に最長距離を考える．バウンディングボックスの左側に点がある場合，以下2パターンになる．

$x_{i}-\text{BB_min}_{i}$: -（負）
$\text{BB_max}_{i} - x_{i}$: +(正)（最長距離）

反対の右側にある場合を考える．以下2パターンにある．

$\text{BB_max}_{i} - x_{i}$: -（負）
$x_{i} − \text{BB_min}_{i}$ : +（正）（最長距離）

以上のパターンをまとめると

\	左側	右側
$ \text{BB_max}_{i}-x_{i} $	正	負
$ x_{i} - \text{BB_min}_{i}$	負	正

各軸の最長距離を求める式は次になる．

$\mathrm{sd}_{i} = \mathrm{max}(\text{BB_max}_{i} - x_{i} , x_{i} - \text{BB_min}_{i}), (\text{for } i = 1, \cdots , d)$

この距離の式のときに，バウンディングボックス内部に点がある場合の符号付き距離がどうなるか調べる．

\	sign
$\text{BB_max}_{i} - x_{i}$	正
$x_{i} - \text{BB_min}_{i}$	正

バウンディングボックス内部のときを距離0とすると式は，以下の条件で分けられる．

$\begin{eqnarray} \hat{\mathrm{sd}}_{i} &=& \left\{ \begin{array}{ll} 0 & (\text{BB_max}_i - x_i>0 \cap x_i - \text{BB_min}_i>0)\\ \mathrm{sd}_{i} & (\text{others}) \end{array} \right.\\ D &=& \left( \sum_{i}^{d} \hat{\mathrm{sd}}_{i}^{p} \right)^{1/p}, (p >0, \neq \infty) \end{eqnarray}$