minkowski sumを使用した衝突予測

Question

minkowski sumを使用して、2つの凸形状間の衝突の正確なポイントを予測したいとします。私の理解では、速度ベクトルがミンコフスキーの合計と交差する点は、ベクトルに沿ってオブジェクトを移動させなければならない量であり、それらはタッチするだけです（私はすでに衝突することを知っています）。ここで私が何を意味するか（簡単の理由から、私はちょうど使用の長方形）の例です：私はちょうど凸包のすべての行との交点を計算し、ちょうど最も近い使用することができます意味

はそれは恐ろしく思えます非効率的な。私の考えはベクトルに最も近いシンプレックスを計算することでしたが、どのようにするのが最善かわかりません。私はオブジェクトとの間の最小距離を計算するか、またはミンコフスキー和から原点までの最小距離（http://www.codezealot.org/archives/153）をより正確に計算するアルゴリズムを見つけました。アルゴリズムの1つの部分は、私がやりたいことである原点に最も近い単体を見つけようとします。私はそれを私のニーズに変えようとしましたが、成功しませんでした。私にとっては、非常に単純な解があるはずですが、ベクトル計算ではそれほど良いとは言えません。

は、私は私の英語があまり良くないので、私は明らかに私の問題を作ることを願っています：D

Answer 1

次のようにあなたが問題を変換することができます：速度ベクトルが水平になるように

1）は平面を回転

2）ポリゴンの輪郭線が互いに向かい合っている部分を考慮してください（2つの凸ポリラインです）。今、あなたは、水平線を描画し、ポリラインの1のすべての頂点を介してこれらの2つのポリライン

3）との間の最短水平距離を見つける必要があり、これは、水平移動によりY軸方向にそれを規定する2つの頂点をもたらす剪断変換を使用してすべてのスライスを変換）水平スライス

4のセットに平面をparitionう。この変換は最初のポリラインを直線（Y軸）に変換されるが、他のポリラインが別のポリラインに変換された水平距離

5）を保持し; Y軸に最も近い頂点を見つける。これにより、衝突ベクトルの長さが求められます。

Y値の範囲が重なっている場合は、副産物として、ステップ2）でポリゴンが衝突するかどうかがわかります。