閉じた多角形を形成する 2D ポイントの座標セットがあります。ポリゴンを完全に分散する 2D 三角形のセットを生成する必要があります。
三角形がポリゴンの領域を完全に埋める必要があることを除いて、それ自体には制約はありません。それが私が実装できる標準的なアルゴリズムであれば、さらに役に立ちます。
質問する
2356 次
3 に答える
3
前述のように、ドロネー三角形分割は、このタスクのかなり複雑なアルゴリズムです。O(n^2) の実行時間を受け入れる場合は、理解とコーディングがはるかに簡単な Ear Clipping アルゴリズムを試すことができます。基本的な考え方は次のとおりです。頂点が 4 つ以上あり、穴のないすべてのポリゴン (つまり、境界が自己交差と自己接線のない 1 つのポリライン) には、少なくとも 1 つの「耳」があります。耳は 3 つの連続する頂点であり、それらの上に構築された三角形はポリゴンの内側にあり、内側にポリゴンの他のポイントは含まれません。「耳を切る」(答えに三角形を追加し、これらの 3 点の中間点を削除して置き換える) 場合は、タスクを頂点の少ない多角形に減らします。耳は (定義により) O(n^2) で簡単に見つかり、O(n^3) 三角測量アルゴリズムになります。
さらに、より高速なアルゴリズムが必要な場合は、モノトーン ポリゴンの三角形分割とポリゴンのモノトーンへの分割について検討する必要があります。線形時間の三角形分割アルゴリズムも存在しますが、ドローネ三角形分割と同じくらい複雑です。
ウィキペディアの記事を検討して、そこにある既存の方法の簡単な概要を確認してください。
于 2013-07-22T16:30:09.137 に答える
3
三角形の頂点がポリゴンの頂点である必要がない場合は、ザイデルのアルゴリズムに基づく高速ポリゴン三角形分割のように、台形分解に基づく三角形分割を試してください。
于 2013-07-23T12:40:22.840 に答える