3

それぞれ法線ベクトル、中心座標、および半径で表される 3 つの空間に 2 つのリングがあります。リングがリンクされているかどうかを確認する方法を教えてください。つまり、一方の円上の点はもう一方の円盤にあります。

これはタイトなループで実装されるため、パフォーマンスが心配です。クローズドフォームのソリューションが必要だと思います。これまでのところ、反復的な解決策しか考えていませんでした。

何か助けはありますか？

4

4 に答える 4

3

アルゴリズムの概要：

  1. 円の平面が平行または同時である場合を処理します。
  2. 円の平面の交線を見つけます。
  3. この線と円の交点を見つけます。
  4. 線とのすべての円の交点は両方の平面上にあります。これで、距離チェックを実行して、円がリンクされているかどうかを確認できます。

詳細：

円C1とC2は、中心点（p1、p2）、単位法線ベクトル（n1、n2）、および半径（r1、r2）によって与えられると仮定します。

あるスカラーkに対してn1==k n2の場合、平面は平行または並行です。それらが同時に発生する場合、これは些細な2次元の問題になります。dist（p1、p2）<r1+r2かどうかを確認してください。

それ以外の場合、平面は線Lで交差します。円がリンクされている場合、リンクは相互に互いの定義平面を通過することを意味するため、両方がLと交差する必要があります。これはあなたにあなたの最初の些細な拒絶テストを与えます。

Lは点qとベクトルvで与えられます。vを見つけるのは簡単です。これはn1とn2の外積にすぎません。qは少しトリッキーですが、線の最も近いアプローチのポイントを選択できます

l1(s) = p1 + s (v X n1)
l2(t) = p2 + t (v X n2)

これらの線はv、n1、およびn2に垂直であり、C1およびC2の平面上にあります。最も近いアプローチのポイントはL上にある必要があります。

この投稿を参照して、最も近いアプローチのポイントを見つける方法を確認できます。

最後に、円が交差できる唯一の方法は、両方がLに点を持っている場合です。ある場合は、C2に関連するC1とLの交点を考慮してください。C1とLの交点q11とq12が2つあり、そのうちの1つがC2の内側にある場合、円はリンクされます。LはC2の平面上にあるため、これは平面の円内点テストになります。

IF dist(p1, q11) < r1 THEN
    linked = (dist(p1, q12) > r1)
ELSE
    linked = (dist(p1, q11) < r1)
ENDIF

もちろん、この擬似コードは、円が実際に交差する場合の処理​​については少しずさんですが、それをどのように処理するかは、アプリケーションによって異なります。

于 2012-08-22T19:33:22.530 に答える
1

コーディングが比較的簡単な簡単な解決策: 2 つの平面の交線を計算し、すべて (私の場合は 2 つの円を定義する 6 つの点) を一緒に回転および平行移動して、線が Z 軸 (x=y= 0)。次に、最初の円 C1 が XZ 平面上にあり、C2 が YZ 平面上にあるように、平面を Z を中心に個別に回転させることができます。これで、中心と半径を簡単に見つけることができます (私の状況では、最初はそれらを持っていません)。これらの回転は、リンク/リンクなしのプロパティを変更せず、リンクまたはリンクの欠如は、円と Z 軸との 4 つの交点の順序から簡単に判断できます。(いずれかの円が x=y=0 と交差しない場合、リンクはありません。) (軸を混乱させた可能性がありますが、これでうまくいくと思います。) ありがとうございます。

于 2014-04-26T06:02:12.910 に答える
0

計算幾何学の教科書に良い解があるかもしれません!

しかし、現時点では計算幾何学の教科書が手元にありません。私自身の (非常に限られた) 直感に基づいて、今すぐ自分で作成する場合は、3D 軸に沿ったバウンディング ボックスから始めると思います。

たとえば、「円のすぐ内側」の境界ボックスと「円のすぐ外側」の境界ボックスを作成します。2 つの軸に沿ったボックスが重なり合っているかどうかを判断するのは簡単だと思います (私がかつて行った宿題のセクション 2.1 では、2D の状況で関連する問題について話しています --- ポイントに最も近い四角形を見つける: http://juliusdavies. ca/uvic/report.html )。

次の主張が当てはまると思います (ただし、間違っている可能性があります)。

  • 内箱が重なっている場合、リングは確実に接続されています。(今思うとこれはダメだった…)

  • 外側のボックスが重ならない場合、それらは間違いなく接続されていません --- 私はこの主張が成り立つと確信しています! :-) :-)

  • 外側のボックスが重なり合っているが、内側のボックスが重なり合っていない場合、それらは接続されている可能性があります。

自分で転がすなら、そこから始めます。

結論: うーん、他の回答でうまくいくことを願っています。:-)

于 2012-08-22T19:49:04.277 に答える