ランダムな内側の点を使わずにポリゴンを三角形分割する方法は？

Question

定義済みのポリゴンを三角形で作成したいと思います。私の要件は、Delaunay Triangulationアルゴリズムでこのポリゴンを処理するために、このポリゴンの内側にランダムな点を作成したくないということです。
ポリゴンは、凹形または凸形にすることができます。

私はDelaunay三角測量を使用するのは大丈夫ですが、多角形内にランダムな点を作成したくありません。このポリゴンの内部にできるだけ少ないポイントを作成できればもっと良いでしょう。
使用する三角形の数を最小限に抑えたいと思います。

どうすれば設定できますか？

コメント：これは言語にとらわれないものです。私はこれを自分で実装する方法を知りたいのです。

Answer 1

非常に有用なライブラリPoly2Triが見つかりました。このライブラリのJavaブランチは、まさに私が必要とするものです。

これを正しく使用するだけです。ポリゴンにポイントを追加しません。

Answer 2

Ear Clipping or monotone polygonsを使用できます。いずれのアルゴリズムも余分なポイントを導入しません。

（あなたが単調多角形を形成することを選択した場合、単調多角形が凸であり、直接三角形のファンに分けることができます。）

Answer 3

多角形が凸である場合には、それだけで境界を使用して、ポイントを使用して三角測量するのは簡単です境界に沿って。それが凸でない場合は、凸の境界線を作成し、挿入された点を挿入点にマークします。次に、他のすべてを実行したら、挿入されたポイントを削除します。

長く細い三角形がある場合は、メッシュリファインメントアルゴリズムを使用してメッシュを細かく調整することもできます。 Delaunayを使うと、定義によっては三角形が「薄い」かどうかをチェックすることができます。「薄い」の場合は、その三角形の外接円に点を挿入します。したがって、あなたがしなければならないのは、Delaunay理論を使うことだけです。