アルゴリズム
45度回転

45 度回転

キーワード

概要

(x,y)(x, y) 座標を (X,Y)=(xy,x+y)(X, Y) = (x - y, x + y) に座標変換する操作。

(x,y)(x, y)π4\frac{\pi}{4} の回転行列をかけると、

(12121212)(xy)=12(xyx+y)\begin{pmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \end{pmatrix} \begin{pmatrix} x \\ y \\ \end{pmatrix} = \frac{1}{\sqrt{2}} \begin{pmatrix} x - y\\ x + y \\ \end{pmatrix}

が得られる。

(x,y)(x, y) 座標上の 2 点 (x1,y1),(x2,y2)(x_1, y_1), (x_2, y_2) のマンハッタン距離は、

d=x1x2y1y2=max((x1x2)+(y1y2),(x1x2)+(y2y1),(x2x1)+(y1y2),(x2x1)+(y2y1))=max((x1+y1)(x2+y2),(x1y1)(x2y2),(x1y1)+(x2y2),(x1+y1)+(x2+y2))=max(X1X2,Y1Y2,Y2Y1,X2X1)=max(X1X2,Y1Y2)\begin{equation*} \begin{split} d &= |x_1 - x_2| - |y_1 - y_2| \\ &= \max((x_1 - x_2) + (y_1 - y_2), (x_1 - x_2) + (y_2 - y_1), (x_2 - x_1) + (y_1 - y_2), (x_2 - x_1) + (y_2 - y_1)) \\ &= \max((x_1 + y_1) - (x_2 + y_2), (x_1 - y_1) - (x_2 - y_2), -(x_1 - y_1) + (x_2 - y_2), -(x_1 + y_1) + (x_2 + y_2)) \\ &= \max(X_1 - X_2, Y_1 - Y_2, Y_2 - Y_1, X_2 - X_1) \\ &= \max(|X_1 - X_2|, |Y_1 - Y_2|) \end{split} \end{equation*}

が成り立つ。

上の等式からわかるように、 (X1,Y1)(X_1, Y_1) から等距離の点は、 (X1,Y1)(X_1, Y_1) を中心(対角線の交点)とする正方形上に存在する。

計算量

変形自体は O(1)\mathrm{O}(1)

応用例

  • 最大距離の点の取得
  • 等距離の点の取得

例題

引用