ポリゴンの三角形分割

3Dモデルで使用するポリゴンを三角形分割しようとしています。私は、点を下に点を持つポリゴンで耳のメソッドを使用してみると、私は赤い線がある三角形を取得します。これらの三角形の中に他の点がないので、これはおそらく正しいでしょう。しかし、私はそれが黒い線の中だけの領域を三角測量したい。誰でもこれを行うアルゴリズムを知っていますか？あなたはモノトーンポリゴンにポリゴンを分割ポリゴンの三角形分割

enter image description here

出典

2012-01-16 user978281

図を凸部分にカットして三角形分割できます。しかし、大規模な複雑な数字のために乱雑になる。 –

あなたの三角測量にはどのような制約（Delaunay？）がありますか、時間的制約はありますか？さもなければ答えはかなり広範囲になるでしょう。 – pmr

制約はありません。モデルは一度生成されるため、時間は大きな問題ではありません。 – user978281

モノトーンポリゴンに最初に分割する必要のないポリゴンを三角形分割するアルゴリズムは多数あります。 1つは私の教科書Computational Geometry in Cに記述されています。このコードには、そのリンク（CまたはJava）から自由にダウンロードできるコードがあります。まず、境界トラバーサルに対応する点を順番に並べる必要があります。私のコードは反時計回りを前提としていますが、もちろん変更するのは簡単です。 Wikipedia articleも参照してください。おそらくそれはあなたの問題です、あなたは境界点が一貫して組織されていないのでしょうか？

出典

2012-01-17 01:23:15

あなたの本を愛しているジョセフは、私の後ろの棚の上に座っているそれのいくつかのエディションを持っています。 Edelsbrunner、Shamos＆Perparata、Hjelle＆Daehlenの間で誇りを持って座っています。 TINを使って作業する人にとっては本当に必要です。 –

@Shane：おいしい言葉をありがとう！ :-) –

答えに上記のコードを含めることはできますか？ – Jonny

Wikipedia suggest。ポリゴンがすべての角度が180度未満であることを確認するだけで、ポリゴンが凹んでいないかどうかをチェックします.180度を超えるコーナーは凹形であり、そのコーナーで折る必要があります。

出典

2012-01-16 22:44:32 Soren

通常の方法は、単純ポリゴンを台形分解を使ってモノトーンポリゴンに分割し、次にモノトーンポリゴンを三角形分割することです。最初の部分はスイープラインアルゴリズムで実現できます。また、適切なデータ構造（例えば、二重に接続されたエッジリスト）によってスピードアップが可能である。私が知っているこれの最も良い説明はComputational Geometryにあります。 Thisとthisも役に立ちます。

出典

2012-01-16 23:38:05 pmr

C++を使用できる場合は、CGALを使用できます。特に、交差していないポリゴンのセットを三角形分割できるhereの例を使用できます。この例は、黒い部分がすでに分かっている場合にのみ機能します。

出典

2012-01-17 07:37:50 sloriot

DelaunayではなくEarClippingアルゴリズムを使用する必要があります。次のホワイトペーパーを参照してください。http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

出典

2012-01-18 07:39:04 abenci

答えて

関連する問題