たゆんだ糸をピンと張るような数式

質問

識者の方々、どうか知恵をお借りさせてください。

２次元のxz平面で、
ぐにゃぐにゃした壁をまっすぐ切断したときの切断点をそれぞれ始点、終点とし、
始点から終点へ移動するまでの最短ルートを求める（画像の下）ことが目的です。

とりあえず画像の上のように、壁を沿った線上の座標は特定できるものとします。

これを求めるには他にどのような情報が必要で、それを踏まえてどう計算するかを教えてください。
ではよろしくお願いします。

回答No.2

nag0720 · ベストアンサー

まだ締め切っていないようなので、考えたことを回答します。

簡単にするために、下側の壁だけで考えます。

壁の座標を、W(i)=(x(i),z(i))[t=0→n]、（nは十分大きい値とします）
点(x,z)が壁の内側か外側かを判定する関数を、F(x,y)
ルートの座標をR(i)=(X(i),Z(i))[i=0→n]で表し、
ルートの初期値をR(0)=W(0)、R(n)=W(n)とし、
W(0)→W(n)とします。（→は直線を表します）
つまり、ルートの初期値は、始点と終点を結んだ直線です。

(a)
始めに、F(X(1),Z(1))を判定し、壁の外側ならなにもせず、
壁の内側なら、ルートを変更して、R(1)=W(1)とし、
W(0)→W(1)→W(n)

(b)
つぎに、F(X(2),Z(2))を判定し、壁の外側ならなにもせず、
壁の内側なら、ルートを変更して、R(2)=W(2)とし、
W(0)→W(1)→W(2)→W(n)
（ただし、(a)の判定で壁の外側だった場合は、W(0)→W(2)→W(n)）

(c)
つぎに、F(X(3),Z(3))を判定し、壁の外側ならなにもせず、
壁の内側なら、ルートを変更して、R(3)=W(3)とし、
W(0)→W(1)→W(2)→W(3)→W(n)
（ただし、(a),(b)の判定によっては、W(0)→W(3)→W(n)　または　W(0)→W(2)→W(3)→W(n)　または　W(0)→W(1)→W(3)→W(n)）

このようにしていけば、ルートは壁に沿ったものになるはずです。

と思ったのですが、壁がえぐれている場合は、そうはならないことに気付きました。
それに対応するために、ルートを変更したときに下記の処理をします。

変更した点とその２つ前のノード（直線の結合点）とを直線で結んだときに、その直線が壁の外側になるかを調べます。
直線が壁の内側になる場合は、処理を終了します。
直線が壁の外側になる場合は、１つ前のノードを消去し、さらにその２つ前のノードについても同様に調べ、これを繰り返します。

以上のことをすれば、最短ルートが決定できるはずです。

壁が上にもある場合はもう少し工夫が必要ですが、同じ考え方でなんとかなるかなと思います。

お礼

大変詳しい説明ありがとうございます。
自分も未だ、いろんなアルゴリズムを考え中です。
せひ参考にさせていただきます。

回答No.1

sono0315

壁の座標がわかるならば、それぞれの突起部分間での接線を
うまく求めるといいのではないでしょうか

お礼

回答ありがとうございます。

そういう発想も考えているのですが、
実際に「うまく求める方法」が分からずに困っております。