fc2ブログ

Javaゲーム制作記

いろいろ作ってます  FC2無料カウンターFC2無料カウンターFC2無料カウンターFC2無料カウンターFC2無料カウンターFC2無料カウンターFC2無料カウンターFC2無料カウンター

任意多角形の三角形分割

今日はゲームの更新ではありませんが、
物理ゲームを作る過程で生まれた問題の解決方法です。
「任意多角形の三角形分割」
です。

今使っている物理エンジンは、凸包(凹んでない多角形)しか扱えません。
とすると、多角形の作成に制限が出てしまいます。
前に、
ほんとは用意しないつもりだったけど、手が滑って(?)
「ぐりぐりポリゴンが書けるツールを用意する」
と言ってしまったので、せっかくなので作ります。

"任意多角形の三角形分割"などと書きましたが、
「適当な図形を全部三角形で作ってみよう」という事です。
すごく参考になったページがあります。
[お勉強] 非凸多角形の三角形分割
※勝手にリンク貼りました。すみません

手法とかはこのページを見れば大体分かるのだけど、
ちょっと難しくてわからないと言う人向けに詳しい解説を用意しました。
長くなるので続きからどーぞ

以下手法です。
※自己交差をした多角形はできません。
  交差している点を頂点に分割する必要があります。

この多角形を三角形に分割してみます。


1、どこでもいいので点を決める(原点がお勧め)

これは特に説明は要りませんね。

2、その点から一番遠い頂点を探す

これも問題ないですね。

ただ、ここで、ある点から一番遠い場所にある頂点の角度は180度以下であることを確認しておきましょう。

なぜなら180度よりも大きければ、もっと遠い頂点が存在するはずだからです。
簡単ですね。

3、その頂点と左右の頂点で三角形を作る

角度が180度以下なので、ちゃんと図形の内部で三角形が作れますね。

4、頂点を取り除く

作った三角形を記録し、さっきの頂点を図形から抹消します。

後は1から繰り返すだけです。




Stop!!
思いもよらぬ三角形ができてしまいました。

なんと三角形の中に他の頂点が入ってしまっています
これでは当然三角形を構成できないので、
他の頂点を探しましょう。
その前に、この三角形の向きを記録しておきます。
なぜなら他の頂点を使うと、図形の内部で三角形が構成できないことがあるからです。

こうなったり、

こうなったり。

三角形の向きは外積の正負で記録できますので、
この場合、

この二つのベクトルの外積を求めておきましょう。

では、選ぶ頂点を一つ左に動かしてみましょう。

では三角形を構成しましょう。

運良く向きが一緒、内部に他の点が入っていません!
もしも向きが違ったり、内部に点が入っていたりした場合は、さらに別の頂点を選ぶ必要があります。
多角形である以上、
必ず条件を満たした三角形が構成できる頂点がありますので、大丈夫です。
後は、ひたすら同じ作業です。

※↑頂点が分かりにくいので印をつけています。




ついに頂点が3個になりました
これで分割は完了です。
お疲れ様でした。

[ 2010/07/19 11:31 ] Java | Comment(2)
なるほどさっぱりわからん!
[ 2010/07/22 18:18 ] 名無しさん [ 編集 ]
承認待ちコメント
このコメントは管理者の承認待ちです
[ 2015/09/16 13:07 ] - [ 編集 ]
コメントの投稿




※URL記述の際はttp://としてください


プロフィール

saharan

Author:saharan

Twitter
検索フォーム