2

任意の寸法、平行移動、および回転を持つ 3D ボックスのセットがあります。ボックスを 3 次元コンポーネントで単一の定数でスケーリングして、ボックスが交差しないようにする必要があります。

現時点では、交差点をチェックしてから、交差点がなくなるまで繰り返しスケーリングを減らすことで、これを繰り返し行っています。ただし、これは実行に時間がかかりすぎて、何度も実行する必要があります。

1回のヒットで必要なスケーリングを見つける方法を知っている人はいますか? おおよその解決策は大歓迎です。

すべてに感謝します。

ロブ。

4

1 に答える 1

0

利用できるボックスに関する追加情報がない限り、何らかの検索を実行する必要があります。ただし、一般的なケースでは、検索を2値化することができます。これにより、線形検索を使用するよりも迅速に、許容可能な回答に繰り返し近づくことができます。

これを行うには、満足できる許容誤差εを定義し、次のようなものを使用します。

lower_bound <- 0
upper_bound <- 1

while (scaling with upper_bound results in no collisions)
    lower_bound <- upper_bound
    upper_bound <- 2 * upper_bound

while (|upper_bound - lower_bound| > ε)
    mid_point <- (upper_bound + lower_bound) / 2
    if (scaling with mid_point results in collisions)
        upper_bound <- mid_point
    else
        lower_bound <- mid_point

return lower_bound
于 2010-08-19T16:26:12.363 に答える