3Dモデルで使用するためにポリゴンを三角測量しようとしています。下に点線の点があるポリゴンで耳の方法を使用しようとすると、赤い線がある三角形が表示されます。これらの三角形の内側には他の点がないので、これはおそらく正しいでしょう。ただし、黒い線の内側の領域のみを三角測量する必要があります。これを行うアルゴリズムを知っている人はいますか？
3666 次
5 に答える
8
最初にモノトーン ポリゴンに分割する必要のないポリゴンを三角形化するアルゴリズムは多数あります。1 つは私の教科書Computational Geometry in Cで説明されており、そのリンクから (C または Java で) 自由にダウンロードできるコードが関連付けられています。最初に、境界トラバーサルに対応する順序でポイントを取得する必要があります。私のコードは反時計回りを想定していますが、もちろんそれは簡単に変更できます。ウィキペディアの記事も参照してください。境界点が一貫して整理されていないことが、おそらくあなたの問題ですか?
于 2012-01-17T01:23:15.270 に答える
2
通常のアプローチは、台形分解を使用して単純なポリゴンをモノトーン ポリゴンに分割し、モノトーン ポリゴンを三角形分割することです。最初の部分は、スイープ ライン アルゴリズムで実現できます。また、適切なデータ構造 (二重接続エッジ リストなど) を使用すると、高速化が可能です。私が知っているこれの最良の説明は、Computational Geometryにあります。これとこれも役に立ちそうです。
于 2012-01-16T23:38:05.167 に答える
1
C++ を使用できる場合は、CGALを使用できます。特に、交差していないポリゴンのセットを三角形分割できるここに示す例を使用できます。この例は、黒のセグメントが既にわかっている場合にのみ機能します。
于 2012-01-17T07:37:50.393 に答える
1
ウィキペディアは、ポリゴンを単調なポリゴンに分割することを提案しています。すべての角度が 180 度未満であることを確認するだけで、多角形が凹面でないことを確認します。角度が 180 度を超える角は凹面であり、その角で分割する必要があります。
于 2012-01-16T22:44:32.423 に答える
0
Delaunay アルゴリズムではなく、EarClipping アルゴリズムを使用する必要があります。次のホワイト ペーパーを参照してください。 http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
于 2012-01-18T07:39:04.653 に答える