3

2D平面内の2つの三角形間のオーバーラップ領域の面積を計算する必要があります。奇妙なことに、私は三角形の円の問題のコードを作成しました。これは非常にうまく機能しますが、三角形の三角形の問題に問題があります。

私はすでに、一方がもう一方を完全に含んでいるかどうか、またはもう一方が最初のものを含んでいるかどうかを確認し、すべてのエッジ方向の交点を取得します。これらの交点（ダビデの星のように最大6）は、他の三角形内に含まれる三角形の頂点と組み合わされて、交点領域の頂点になります。これらの点は凸多角形を形成する必要があります。

私が求める解決策は、次のいずれかの質問に対する答えです。

  1. すべての人が知っている点のセットが点集合の凸包上にあるとすると、凸包の面積を計算します。それらはランダムな順序であることに注意してください。
  2. 半平面のセットが与えられた場合、交差する領域を決定します。これは、両方の三角形を3つの半平面の交点として記述し、この記述の直接の交点として解を計算することと同じです。

質問1では、考えられるすべての三角形のすべての領域を単純に合計し、次にカウントの多重度で割ることを検討しましたが、それはばかげているようで、正しいかどうかはわかりません。トリックを行うある種のスイープラインアルゴリズムがあるように感じます。ただし、ソリューションは比較的数値的に堅牢でなければなりません。

質問2を解決する方法がわからないだけですが、一般的な答えは非常に役立ち、コードを提供することで1日を過ごすことができます。これにより、凸多角形で三角形分解を実行する代わりに、凸多角形の交差領域を直接計算できます。

編集：2つの凸多角形の交差多角形を見つけるための一般的なケースを説明するこの記事を知っています。三角形だけに関係しているように見えます。さらに、結果のポリゴン自体は実際には必要ありません。したがって、この質問は、この時点で怠惰に行われている可能性があります。

4

1 に答える 1

3

質問1：ポイントがランダムな順序になっているのはなぜですか？そうである場合は、連続する点を直線で結ぶと凸多角形になるように並べ替える必要があります。それらを注文する方法-たとえば、凸包アルゴリズムを実行することによって（おそらくもっと簡単な方法もありますが）。それらを注文したら、ここで説明されているように面積を計算します。

-

質問2はもっと簡単です。半空間は、暗黙の方程式を持つ1本の線で定義されa*x+b*y+c=0ます。a*x+b*y+c <= 0（不等式に注意）半平面の「後ろ」にあるすべての点（x、y） 。ここで、負の半空間の交点を閉じるために、少なくとも3つの平面が必要です（これは必要ですが、十分条件ではありません）。交差点が閉じている場合は、凸多角形になります。

頂点のリンクリストを維持することをお勧めします。アルゴリズムは3行で初期化されます。線が交差する3つの点（一般的な場合）を計算します。これらは、リージョン（三角形）の開始頂点です。また、各頂点が、他の2つの頂点を通る線によって定義される半平面の「後ろ」にあることを確認する必要があります。これにより、交差点が実際に閉じた領域であることが保証されます。

これらの3つの頂点は、三角形の3つのエッジも定義します。新しい半平面と交差するときは、半平面を定義する線と現在の領域の各エッジとの交差を確認するだけです。通常、2つの交点が得られますが、線が領域の頂点を通過する縮退した場合に注意する必要があります。（空のセットになることもあります！）

新しい交差頂点は、現在の領域を2つの領域に分割する線を定義します。ここでも、新しい半平面の方向を使用して、2つの新しい領域のどちらを新しい「現在の領域」に割り当て、どちらを破棄するかを決定します。

現在の領域のエッジを定義するリスト内のポイントは正しく順序付けられるため、上記のリンクの式を適用してその面積を計算できます。

この説明が詳細/理解できない場合、私があなたに与えることができる次善のアドバイスは、計算幾何学と線形代数に関する本に投資することです。

于 2010-06-19T05:30:19.503 に答える