平面上の点集合と不完全点triangulation of the convex hull of the points（いくつかの辺のみが与えられます）が与えられると、私は三角形分割を完了するアルゴリズムを探しています固定されたままである）。部分的な三角測量を完了することは可能だと仮定することができますが、それを確認するためのアルゴリズムも提案できれば素晴らしいでしょう。部分三角形分割を完了するアルゴリズム（制約付き三角形分割）
UPDATE "点R^2の集合の凸包を与えました。基本的には内部にいくつかの点があるポリゴンです。点集合を三角形分割したいのですが、それは簡単な問題ですが、あなたはまた、あなたが思いつく三角測量がそれらのエッジを使用するべきであるいくつかのエッジを与えられています。
おそらくこれは単純な答えですが、拘束されたdelaunay三角測量を使うことはできませんか？既知のエッジを制約として追加します。
CGALはnice implementationです。ツールtriangleには同様の機能があり、使い始めるのは簡単ですが、多少柔軟性があります（おそらく）。
「Computational Geometry：An Introduction」という本は、擬似コードを実装する準備ができていないけれども、対象の詳細な扱いをしていることが分かりました。
最も簡単なアルゴリズムは、すべての可能な辺を列挙し、それらを1つずつ追加して、以前に追加された齢との交差を回避する欲張りなアルゴリズムです。実行時間をO（n^2 log n）に減らす方法については、この本で長い議論があります。
次に、O（n log n）アルゴリズムがあります。このアルゴリズムでは、最初に、指定されたエッジで凸包を正規化し、次に各単調ポリゴンを個別に三角形分割します。
どのようにして1つのエッジで三角測量を実行できますか？無限の空間ではないですか？ –
「更新」の表現は宿題のように聞こえるでしょうか？ – Damon
いいえ、それ以上の計算のためにグリッドを初期化するアルゴリズムが必要です。 – user972432