私はDelaunay 三角形分割を研究しており(宿題ではありません)、次の問題について考えました:S平面上の点のセット (濃度がn) と三角形のセットT(濃度n-2が三角形のセットTは Delaunay 三角形分割を形成しDT(S)ますか?
最初の問題は、ドロネー三角形分割が一意ではないことです。そのため、ポイント セットを再構築して三角形セットと比較しても、答えが得られません。さらに、最適な Delaunay 三角形分割アルゴリズムを実装するのはかなり困難です (ただし、CGAL などのライブラリを使用することは問題ありませんでした)。
三角形集合が三角形分割であるかどうかをチェックする方法を知っていると仮定します (必ずしも Delaunay である必要はありません)。次に、Delanuay 三角形分割の定義を使用する必要があります。三角形分割のすべての三角形についてt、 の点はSの円周内に厳密にはありませんt。これにより、次の方法が得られます。
- 些細なアプローチ。を反復し
T、円周を計算して を反復しS、点が円周の内側にあるかどうかを確認します。ただし、これにはO(n^2)時間がかかり、最適とは言えません。 - 魅惑のアプローチ。繰り返し、
T円周を計算します。円周の内側にある点sは、円周の中心までの距離が半径よりも小さいことを意味します。上の最近傍探索構造を使用Sして、アルゴリズムを高速化します。たとえば、単純なkd ツリー構造からO(n log n)、平均的なアルゴリズムとO(n sqrt(n))最悪のケースのアルゴリズムが導き出されます。 - もっと簡単なことを考えている人はいますか？
Tが三角形分割かどうかをチェックする問題に戻りましょう。の等価性や三角形の頂点のセットなどの些細な事前要件はS、 よりも速く実行できませんO(n log n)。残っていること — の 2 つの三角形ごとにT共通の面で交差するか、まったく交差しないかを確認します。
- 繰り返しますが、交差をチェックして
Tを何度も反復することでこれを行うことができますが、これはアルゴリズムです。TO(n^2) t1«三角形とt2交差» の意味を考えてみましょう。それらのエッジが交差する場合、または 1 つの三角形が完全に別の三角形の中にある場合、それらは交差します。すべてのエッジを交差させる問題は、Bentley-Ottmann アルゴリズムO(n log n)を使用して一度に解決できます(最悪の場合は、は交差の数ですが、最初の交差が見つかった時点でアルゴリズムを停止できます)。また、ある三角形が別の三角形を完全に含む場合も認識していませんでしたが、Bentley-Ottmann アルゴリズムを修正して、セグメントではなくスイープ ラインと交差する三角形を維持できると信じています。ただし、実装は非常に複雑です。O((n + k) log n)kO(n log n)- 私は反復アルゴリズムについて考えました — 交差しない (またはエッジでのみ交差する) 三角形の構造を維持しましょう (kd-tree に非常に似たものにする必要があります)。次に、次の三角形 を追加しようとします
t。まず、tの頂点のいずれかが既に三角形の 1 つに含まれているかどうかを確認します。次に、交点が得られます。それ以外の場合は、構造に追加tします。ただし、検索してクエリを追加する時間が必要な場合はO(log n)、O(sqrt(n))この構造の高さのバランスを取る必要があります。これは、kd ツリーの場合でも困難です。
では、この問題の簡単な解決策を知っている人はいますか?