0

スタックオーバーフローにリストされている同様の質問に対する多くの密接で役立つ回答がありますが、私の特定のケースに一致するものはまだ見つかりません.

バウンディング ボックスと、その中心点から発するライン セグメントとの交点を計算するためのパフォーマンス効率の高いアルゴリズムが必要です。各バウンディング ボックスには、複数のライン セグメントの放射がある場合があります。

私の問題の定義によると、各線分は、バウンディング ボックス エッジ セグメントの 1 つ (および 4 つの点のみを除く) と交差します。

これがイラストです。

中心点から発する線分で接続された 4 つの境界ボックス

迅速かつ計算的に「安価に」計算したい：

  1. 線分が交差するバウンディング ボックスのエッジはどれか?

  2. 稜線と線分が交わる点は何ですか?

ありがとう。

4

2 に答える 2

0

中心が (0,0) で辺の長さが 2 の正方形のボックスがあるとします。ボックスの中心から放射状に広がるベクトル (dx,dy) があるとします。次に、光線がエッジと交差するポイント (xp,yp) を計算します。

2 回fabs、2 回の比較、1 回の除算、および 2 回の代入を実行します。次に、それを特定の正方形に変換してスケーリングするだけです。

if (fabs(dx) > fabs(dy)){
  if (dx > 0){
    xp = 1;     // right side
    yp = dy/dx;
  } else {
    xp = -1;     // left side
    yp = -dy/dx
  }
} else {
  if (dy > 0){
    yp = 1;     // top side
    xp = dx/dy;
  } else {
    yp = -1;     // bottom side
    xp = -dx/dy
  }
}
于 2013-05-21T23:11:05.487 に答える
0

C をバウンディング ボックスの中心とし、P をセグメントのもう一方の端点とします。V = (Vx, Vy) = P - C を C から P を指すベクトルとします。

バウンディング ボックスの高さ = 2 * H、幅 = 2 * W とします。W と H は通常の高さと幅の半分であり、以下の計算が簡単になります。

考え方は次のとおりです。V が最初の象限にあり、Vx > 0 および Vy > 0 である場合を考えてみましょう。セグメントは、上側または右側と交差します。V の傾きと、ボックスの中心から右上隅までのセグメントの傾きを比較することで、どちらであるかがわかります。傾斜が大きい場合は上部と交差し、そうでない場合は側面と交差します。

したがって、V が第 1 象限にあり、Vy / Vx > H / W の場合、セグメントは上部と交差します。Vy / Vx < H / Wの場合、辺と交差します。それらが等しい場合、コーナーと交差します。

交差する辺がわかったら、相似三角形を使用して交点を計算できます。点 I = (Ix, H) で頂点と交差する場合、Vx / Vy = Ix / H または Ix = H * Vx / Vy となります。点 I = (W, Iy) で辺と交差する場合、Vy / Vx = Iy / W または Iy = W * Vy / Vx となります。

他の象限でも同じ方法が機能します。Vx と Vy の兆候を追跡する必要があるだけです。戻り値が sign(Ix) == sign(Vx) および sign(Iy) == sign(Vy) を満たすことをアサートすることで、作業が少し楽になります。

また、符号に注意すれば、除算を避けることができます。Vy / Vx > H / W は、Vx > 0 と仮定して、Vy * W > Vx * H と同等です。

于 2013-05-21T20:58:29.417 に答える