２点の最短距離での移動

Question

以下のソースコードで実行すると、最短距離ではない移動になってしまいます。（詳細は画像参照）

if(X2 < X1){X1 --;}
if(X2 > X1){X1 ++;}
if(Y2 < Y1){Y1 --;}
if(Y2 > Y1){Y1 ++;}

どのように記述すれば最短距離で移動してくれるでしょうか？

Answer 1

(x1, y1) - (x2, y2) を結ぶ直線上を移動する点(x, y) を式で次のように表すことができます。
x = x1 + t * (x2 - x1)
y = y1 + t * (y2 - y1)
ここで tは 移動開始後の経過時間を表します。そして
t = 0 の時に (x1, y1) にいる
t = 1 の時に (x2, y2) にいる
ものとします。

点を (x1, x2) から 0.1 秒毎に移動させて、1秒後に (x2, y2)動作の擬似コードは次のようになります。

t = 0.0
dt = 0.01       // 0.01 秒毎に点を描画する (100 フレーム / １秒 の描画に対応)
dx = x2 - x1
dy = y2 - y1
move(x1, y1)    // スタート地点に点を移動させる

while (t < 1.0) {
   x = x1 + t * dx  // t 秒後の点の x 座標を計算
   y = y1 + t * dy  // t 秒後の点の y 座標を計算
   move(x, y)       // 点を (x, y) に移動させる。
   t += dt
   wait(dt)          // dt 秒間 スリープする。
}

↑では t を １秒で 0.0 〜 1.0 まで等間隔で変化させていますが、
t の変化量を変化させると、加速しながら移動したり、減速しながら移動させるようなこともできます。

↑では x, y を t を変数にした関数にしていますが、
この関数を工夫すると、円を描くようにさせたり、四角形を描くようにさせたりすることもできます。

Answer 2

直線を書くアルゴリズムというものがあります。
(コンピュータグラフックスの教科書なら触れられているトピックのはず)
以下に参考情報を紹介します。

参考情報：

• ブレゼンハムのアルゴリズム https://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AC%E3%82%BC%E3%83%B3%E3%83%8F%E3%83%A0%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

...
ブレゼンハムのアルゴリズム(Bresenham's line algorithm)は、与えられた始点と終点の間に連続した点を置き、近似的な直線を引くためのアルゴリズム。
ブレゼンハムの線分描画アルゴリズム、ブレゼンハムアルゴリズムとも。
コンピュータのディスプレイに直線を描画するのによく使われ、整数の加減算とビットシフトのみで実装できるので多くのコンピュータで使用可能である。
コンピュータグラフィックスの分野の最初期のアルゴリズムの1つである。これを若干拡張すると、円を描くことができる。
...

• ブレゼンハムの線分アルゴリズム http://unitylab.wiki.fc2.com/wiki/%E3%83%96%E3%83%AC%E3%82%BC%E3%83%B3%E3%83%8F%E3%83%A0%E3%81%AE%E7%B7%9A%E5%88%86%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

↑ には図解もあり、わかりやすいです。

• Bresenhamの線分描画アルゴリズムのサンプル http://www.geocities.co.jp/SiliconValley-Cupertino/3384/src_g1.html

• Bresenhamの直線描画 (Bresen.Java) http://nishitalab.org/user/nis/junk/sougou/document/javaKadai.htm

• Bresenham's line algorithm https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

↑は英語ですが、DDA, Xiaolin Wu's line algorithm へのリンクも含んだ解説があります。
DDA https://en.wikipedia.org/wiki/Digital_differential_analyzer_(graphics_algorithm)
Xiaolin Wu https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm

Comments

[OMDM1991]

丁寧な回答有難うございます。

Answer 3

点P(X1,Y1)と点Q(X2,Y2)を点P(X1,Y1)が原点に重なるように並行移動します。
原点に並行移動するのは、これから求める回転量(角度)の計算を簡単にするためです。

X軸あるいはY軸と平行になるように原点を中心に回転します。
ここではX軸と並行になるように回転したとします。
回転後の点Q'は(X2',０)となります。点P は(0,0)、原点にあるので変化しません。

移動する点をRとすると、点Rは、(0,0) から、(X2',0) まで移動させれば良いことが
わかります。移動させるときに先ほどの回転量(角度)を点Rに逆向きに回転して点R’を求めます。
さらに平行移動した分を元に戻して点R''を求めます。

点R''は、(X1,Y1)から(X2,Y2) への最短距離を移動します。

Comments

[OMDM1991]

丁寧な回答有難うございます。

Answer 4

n回ループでたどり着く、という発想で説明します。

X軸、Y軸の1ループあたりの移動量を求め、
毎ループ加算していけば直線で移動するようになります。

X軸は(X2-X1)/n、Y軸は(Y2-Y1)/n、になりますね。

なので、↓みたいな感じ。（数字は適当です）

// X2,Y2にたどり着くループ数
int n = 10;

// (X1,Y1)の座標
float X1 = 10, Y1 = 0;

// (X2,Y2)の座標
float X2 = 0,  Y2 = 6;

// X軸の1ループあたりの移動量
float Xn = (X2 - X1) / n;
System.out.println(String.format("X軸の移動量=%s", Xn));

// Y軸の1ループあたりの移動量
float Yn = (Y2 - Y1) / n;
System.out.println(String.format("Y軸の移動量=%s", Yn));

// 移動用変数
float posX = X1, posY = Y1;
System.out.println(String.format("(posX=%s,posY=%s)", posX, posY));

// 移動処理
for(int i = 0; i < n; i++) {
	posX += Xn;
	posY += Yn;
    System.out.println(String.format("(posX=%s,posY=%s)", posX, posY));
}

Comments

[OMDM1991]

丁寧で分かりやすい回答有難うございます。