9

三角形のほぼ均一なタイリングを使用して、任意のポリゴンを塗りつぶす必要があります。どうすればいいですか？既存のアルゴリズムへの参照を提供することも、単に独自のアイデアやヒントを提供することもできます。

次のことが推測されます。

  • 多角形は凸面である可能性があります (ただし、凹面形状で機能するアルゴリズムを思いついた場合はボーナス ポイント)
  • 多角形に任意の数のエッジ (3 つ以上) がある
  • テッセレーションの量 (できれば、アルゴリズムによって追加される頂点の数) をパラメーター化する必要があります。
  • ポリゴンのエッジはアルゴリズムによって分割される場合があります
  • 三角形はサイズと形状がほぼ均一である必要があります (つまり、角は 60 度に近づく傾向があります)。
  • 頂点のエッジの数は、多くするよりも少なくする必要があります。これは、前のポイントから続く可能性があります (つまり、アルゴリズムは「クリーン メッシュ」を生成する必要があります)。

これは簡単に解決できる問題ではなく、「ヒューリスティック」な解決策が最も効率的であると期待しています... (そうですか?)

4

4 に答える 4

5

トライアングルはあなたが望むことをしますか?

(そのサイトのアルゴリズムの説明は、私が思いついたものよりも優れています。)

于 2010-01-04T14:42:27.627 に答える
4

アルゴリズム的には、実際にはそれほど複雑に聞こえません。または、何か不足していますか？

擬似コード:

  • ポリゴンの周りに、軸に沿って囲まれた四角形をしっかりと配置します。
  • 各正方形を 4 つの子 (quad-tree のようなもの) に細分し、反復回数によって「テッセレーションの量」が決まります。
  • 結果として得られる各正方形は、ポリゴンの外側 (=無視)、ポリゴンの内側 (= 対角線に沿って結果のテッセレーションの 2 つの三角形に分割)、またはポリゴンと交差します。
  • 交差点の正方形の正確なケースは、読者への演習として残されています。;-) [現時点では、少なくとも。]

ただし、角度が 45°/45°/90° の三角形が得られます。できるだけ 60° に近づけたい場合は、多角形の表面を六角形でテッセレーションすることから始めて (六角形のサイズが「テッセレーションの量」になります)、次に 6 つの 60°/60° のそれぞれをチェックする必要があります。これらの六角形を構成する/60°の三角形。これらの三角形については、上記の疑似コードの正方形と同じことを行いますが、多角形の内側にある三角形は既に三角形であるため、きれいに分割する必要はありません。

これは何か役に立ちますか？交差する正方形/三角形に対して正確に何をするかがそのようなポリゴンを処理することを考えると、任意のポリゴン（凸/凹/穴付き）で機能するはずです。

于 2010-01-04T13:34:26.470 に答える
3

Jason Orendorff が指摘したように、三角形を使用して高品質のメッシュを生成するようにしてください。等方性メッシュを取得するために使用できる多くのオプションがあります。次に、反復アルゴリズムを使用して、中心にある三角形分割を作成することを試みることができます。詳細については、この出版物ページに記載されています. 私は 2007 年の論文「Well-Centered Planar Triangulation -- an Iterative Approach」を実装しており、中サイズのメッシュでまともな結果が得られます。中心の良い三角形分割とは、三角形のすべての外心がそれぞれの三角形の内側にある三角形分割です。わずかに異なるものが必要なため、関連するエラー メトリックを変更してみることもできます。三角形の間で「不一致」の尺度を見つけて、そのエラーを最小限に抑えることができます。ほとんどの場合、このようなエラー関数は非凸になるため、説明されている非線形共役勾配の最適化は、あなたができることと同じです。

于 2010-01-04T22:27:48.263 に答える