5

平面内の一連の点と点の凸包の不完全な三角形分割(一部のエッジのみが指定されている) が与えられた場合、三角形分割を完了するアルゴリズムを探しています (最初に指定されたエッジは固定されたままにする必要があります)。部分的な三角形分割を完了することは可能であると想定できますが、それをチェックするためのアルゴリズムも提案できれば幸いです。

更新」 ポイントのセット R^2 の凸包が与えられます。これは基本的に、内部にいくつかのポイントを持つ多角形です。ポイントのセットを三角測量したいのですが、それ自体は簡単なことですが、あなたも思いつく三角形分割でそれらのエッジを使用する必要があるいくつかのエッジが与えられます。」

4

2 に答える 2

4

おそらくこれは単純な答えですが、制約付きのドローネ三角形分割を使用することはできませんか? 既知のエッジを制約として追加します。

CGAL には優れた実装があります。ツールトライアングルには同様の機能があり、簡単に使い始めることができますが、(おそらく) 柔軟性が少し劣ります。

于 2011-10-16T11:10:22.737 に答える
0

「Computational Geometry: An Introduction」という本には、疑似コードを実装する準備が整っていませんが、この主題が詳細に扱われていることがわかりました。

最も簡単なアルゴリズムは、すべての可能なエッジを列挙し、以前に追加された年齢との交差を避けてそれらを 1 つずつ追加する貪欲なアルゴリズムです。この本には、実行時間を O(n^2 log n) に短縮する方法についての長い議論があります。

次に、最初に指定されたエッジで凸包を正則化し、次に各単調ポリゴンを個別に三角形分割する O(n log n) アルゴリズムがあります。

于 2011-10-18T06:06:48.057 に答える