単純な2Dポリゴンのセットを三角測量しようとすると、次のアルゴリズムが思い浮かびます。
テストしたところ、非常に大きくて複雑な単純な2Dポリゴンでも機能することがわかりました（穴のあるポリゴンや自己交差するポリゴンでは機能しません）。
退化した結果を生み出すコーナーケースはありますか？
このアルゴリズムは既知のものですか？
そうでない場合は、このアルゴリズムが堅実であることを確認したいと思いますが、それを証明する数学的背景はありません。
どうもありがとう。
三角測量に対して「耳のクリッピング」アプローチのバージョンを実行しています。http： //en.wikipedia.org/wiki/Polygon_triangulationを参照してください。
別のポリゴン頂点（たとえば、ポリゴンの反対側から）が、形成する三角形の「耳」の内側にある場合、アルゴリズムは失敗します。この例を考えてみましょう。
アルゴリズムは最初にAを選択し、2つの隣接するエッジ（破線で接続）で三角形を作成します。しかし、この三角形には別の頂点（B）が含まれており、明らかに正しくありません。
一般化された耳のクリッピングアプローチは、頂点が含まれていない、クリップできる耳を見つけることに依存します。
これは、長方形、五角形、六角形などの単純なポリゴンを処理する場合です。ここでは、開始点を取り、それを他のすべての頂点に接続します。このアルゴリズムは簡単で、私が本当に望んでいたのは、凹面と穴のあるポリゴンを処理できる、より一般的なソリューションでした。
Payneが提供したようなより複雑なポリゴンを処理するために...
より高速に実行されるアルゴリズムもありますが、より高速なアルゴリズムは非常に複雑になります。Kirkpatricketal。O（n log log n）で実行するアルゴリズムを見つけ、ChazelleはO（n）でそれを実行しました。ただし、実装するのが最も簡単なのは、おそらくO（n log n）で実行されるSeidelアルゴリズムです。
アルゴリズムは3ステップのプロセスです
Cソースに興味がある場合は、ノースカロライナ大学チャペルヒル校から入手できます。一般に、コードの品質は良好で、穴を処理しますが、おそらくニーズに合わせてマッサージする必要があります。
私があなたを正しく理解しているなら、あなたは最小の内角から始めて三角形を切り刻んでいます。ポリゴンが凸面でない場合、これは失敗する可能性があります。（0,0）（10,9）（9,9）（9,10）に頂点が（順番に）あるポリゴンを考えてみましょう。最小の角度は原点の角度ですが、その三角形を安全に切り取ることができません。
（ポリゴンが凸面の場合は、任意の頂点を選択し、そこで三角形を削除して繰り返すことができます。したがって、非凸多角形でもアルゴリズムを機能させたいと思います。）
耳のクリッピングはかなりうまく機能しますが、各耳を折りたたむときにポリゴン全体をチェックするのがますます遅くなるため、ポリゴンの複雑さが増すにつれて、単純な方法は遅くなります。
からの耳のクリッピングアルゴリズムlibgdxは、非常に堅牢であるため、開始するのに適しています-FIST （Fast Industrial-Strength Triangulation of Polygons）を使用します。
O(n log n)これをポリゴンテッセレーションの基礎として使用し、次に（の代わりに）ポイントイントライアングルテストの空間最適化を追加しましたO(n^2)。
見る：
アルゴリズムは明示的に穴をサポートしていませんが、別々の島の間で鍵穴のエッジを使用できます。これにより、正しく三角形分割されます。