c# - 三角形を凸多角形にメッシュするにはどうすればよいですか?

Question

三角形のメッシュがあります。三角形にはさまざまな「色」があります。このような：

私が取得する必要があるのは、最適化されたメッシュです。ここでは、過剰な三角形が凸面ポリゴンにマージされます。このような：

それを達成するためのいくつかのアルゴリズムのリンクを教えてもらえますか? 前もって感謝します！

PS私はC＃を使用しています。

Answer 1

Hertel-Mehlhorn アルゴリズムは、これを行うための標準的なアプローチです。次のように要約できます。

1. 多角形 P の三角形分割から始めます。
2. 不要な対角線を削除する
3. 繰り返す。

( http://www.philvaz.com/compgeom/より)

これは多項式時間で機能し、最適性には限界がありますが、必ずしも最適であるとは限りません。

あなたの場合、異なる色の三角形間の対角線を考慮しないことで、ステップ 2 を変更します。

一般に「見栄えの良い」ピースを生成するヒューリスティックの 1 つは、各ステップで最長の対角線をマージすることです。

それが役立つことを願っています。

Answer 2

この問題を解決するためのアルゴリズムへのリンクはありませんが、凸多角形を一度に三角形に構築するよりも良いアプローチは、最初に三角形を最大の単純な多角形にマージすることです (つまり、それらは凹型になる可能性があります)。 、ただし穴はありません)、これらの大きなポリゴンを凸状の構成要素に分割できます。

内角が 180 度を超えているため、これらの分割が発生する頂点がわかっている場合は、分割する入射エッジを選択するだけです。分割するのに最適なエッジを選択する正確な方法は単純な問題ではありませんが、合理的なヒューリスティックは、分割後に <180 度の内角の数を最大化することです。