重複する可能性のある三角形のセットが K 個ある場合、新しい重複しない三角形のセットを計算する計算効率の良い方法は何ですか?
たとえば、次の問題を考えてみましょう。
ここでは、3 つの三角形の集合 A、B、C があり、相互に重なりがあり、重なりのない集合 A'、B'、C'、AB、AC、BC、ABC を取得したいと考えています。たとえば、AC の三角形A と C の間に排他的なオーバーラップがあるサーフェスが含まれます。および A' には、他のセットと重ならない A のサーフェスが含まれます。
1618 次
5 に答える
3
私は（また）2段階のアプローチを提案します。
1. すべての三角形の辺の交点を見つけます。
コメントで指摘されているように、これは十分に研究された問題であり、通常はライン スイープ メソッドでアプローチされます。これは非常に優れた概要です。特に、Bentley-Ottmann アルゴリズムを見てください。
2. 制約付き Delaunay で三角測量します。
@Claudiu が提案する Polygon Triangulation は、元のエッジがすべて含まれていることを保証できないため、問題を解決できないと思います。したがって、 Constrained Delaunay triangulationsを参照することをお勧めします。これらを使用すると、制約のない Delaunay またはポリゴンの三角形分割に含まれない場合でも、三角形分割に含める必要があるエッジを指定できます。さらに、三角形が生成されない三角形分割の非凸境界を指定できる実装があります。これもあなたの場合の要件のようです。
Constrained Delaunay の実装は簡単ではありません。ただし、 CMU の研究者 (コマンド ライン ツールを含む) から入手できる、やや古いが非常に優れた C 実装があります。この特定のアルゴリズムの理論については、こちらを参照してください。このアルゴリズムは、境界の指定もサポートしています。リンクされたアルゴリズムは、制約付きドローネ (高品質のメッシュ生成) だけでなく、新しいポイントを追加しないように構成できることに注意してください。これは、制約付きドローネに相当します。
編集別の実装についてはコメントを参照してください。
于 2013-03-15T16:05:51.110 に答える
2
もう少し簡単で、実装が速く、コードが大幅に少ないものが必要な場合...古いソフトウェアレンダリングアルゴリズムのように、単純なポリゴンクリッピングを行うことをお勧めします（特に、三角形のみを扱っているため）あなたの入力として）。他の数人が簡単に述べたように、他のすべてのセグメントが交差するポイントで各三角形を分割する必要があります。
三角形を特定の平面で分割すると、常に 1 つまたは 2 つの新しい三角形 (合計で 2 つまたは 3 つ) が生成されるため、三角形は簡単です。データ セットがかなり大きい場合は、四分木またはその他の形式の空間構成を導入して、新しい三角形が追加されたときに交差する三角形をより速く見つけることができます。
確かに、これは提案されたConstrained Delaunayアルゴリズムよりも多くのポリゴンを生成します。しかし、これらのアルゴリズムの多くは重なり合う形状ではうまく機能せず、シルエット セグメントを知る必要があるため、とにかく同じ作業の多くを行うことになります。
結果の三角形を少なくする必要がある場合は、いつでも最後にマージ パスを実行できます (クリッピング中に隣接情報を追加して、その部分を高速化します)。
とにかく、頑張ってください！
于 2013-06-05T05:47:26.717 に答える
1
あなたの例は、計算幾何学者が「配置」と呼ぶ特別なケースです。CGAL ライブラリには、広範かつ効率的な配置処理ルーチンがあります。ドキュメントのこの部分を確認すると、空の配置を宣言してから、三角形を挿入して 2 次元平面をばらばらの面に分割できることがわかります。他の人が言ったように、まだ三角形ではない面を三角測量する必要があります。幸いなことに、CGAL には、これを行うためのルーチンも用意されています。 この制約付き Delaunay 三角形分割の例は、開始するのに適した場所です。
CGAL は、実装が実用的で利用可能な最も効率的なアルゴリズムを使用しようとします。この場合、O((n + k) log n) を n 個のエッジ (この場合は三角形の数の 3 倍) と k 個の交差点を持つ配置で達成できるように見えます。アルゴリズムは「スイープライン」と呼ばれる一般的な手法を用いています。垂直線は、途中で計算および処理された「イベント」で左から右にスイープされます。イベントは、エッジの端点と交差点です。各イベントが処理されると、配置のセルが更新されます。
Delaunay アルゴリズムは通常、n 個の頂点に対して O(n log n) です。いくつかの一般的なアルゴリズムがあり、簡単に調べたり、CGAL リファレンスで見つけることができます。
仕事で CGAL を使用できない場合でも (たとえば、ライセンス上の理由で)、ドキュメンテーションには基礎となるアルゴリズムに関する情報源がたくさんあります: アレンジメントと制約付き Delaunay アルゴリズムです。
ただし、配列と三角測量の両方が、浮動小数点エラーのために正しく実装するのが難しいことで知られていることに注意してください。堅牢なバージョンは、有理数演算 (CGAL で利用可能) に依存することがよくあります。
于 2013-03-19T00:35:57.717 に答える
0
Ted Hoppからのコメントを少し拡張するには、最初に、出力の各境界面がセットA'、B'、C'、AB、AC、BCのいずれかに関連付けられている平面細分割を計算することでこれが可能になるはずです。 、ABC、または「なし」。次に、2番目のフェーズは、各セットの（おそらく非凸の）面を三角形分割することです。
ステップ1は、現在のセットがアルゴリズムの状態の一部として維持されるBentley-Ottmannスイープラインアルゴリズムのバリエーションを使用して、O（（N + K）log N）時間で実行できます。これは、すでに交差している線分とその方向から判断できます。
それが完了すると、各セットの互いに素なポリゴンは、O（N log N）時間で単調な断片に分割され、O（N）時間で三角形分割されます。
まだお持ちでない場合は、de Berg et al。による「ComputationalGeometry：AlgorithmsandApplications」のコピーを入手してください。
于 2013-03-15T16:11:54.940 に答える
0
2つのアプローチが考えられます。
より一般的なアプローチは、入力を一連の行として扱い、問題を 2 つに分割することです。
- ポリゴン検出。最初の三角形が作成する線のセットを取り、重複しないポリゴンのセットを取得します。この論文では、O((N + M)^4) アプローチを提供しています。N は線分の数、M は交点の数であり、残念ながら少し遅いように見えます...
- ポリゴン三角形分割。ステップ 1 から各ポリゴンを取得し、三角形に分割します。これには、実質的に O(n) である O(n log* n) が必要です。
別のアプローチは、カスタム アルゴリズムを実行することです。2 つの三角形が交差する問題を解き、それを最初の 2 つの入力三角形に適用します。次に、新しい三角形ごとに、現在のすべての三角形と新しい三角形にアルゴリズムを適用します。ただし、2 つの三角形の場合でも、いくつかのケースがあるため (網羅的ではない可能性があります)、これはそれほど単純ではないようです。
- 三角形のどの点も他の三角形にはありません。
- 交差点なし
- ユダヤ人の星
- 2 つの垂直スパイク
- 1 つの三角形の 1 つの点が他の三角形に含まれている
- 各三角形には、他の三角形の 1 つのポイントが含まれています
- 一方の三角形の 2 点がもう一方の三角形の中にある
- 一方の 3 点が他方の中にある - 1 つは完全に含まれている
など...いいえ、それは正しいアプローチではないようです。とにかく後世のためにここに残します。
于 2013-03-15T15:57:02.887 に答える