以下手法です。
※自己交差をした多角形はできません。
交差している点を頂点に分割する必要があります。
この多角形を三角形に分割してみます。
1、どこでもいいので点を決める(原点がお勧め)
これは特に説明は要りませんね。
2、その点から一番遠い頂点を探す
これも問題ないですね。
ただ、ここで、ある点から一番遠い場所にある頂点の角度は180度以下であることを確認しておきましょう。
なぜなら180度よりも大きければ、もっと遠い頂点が存在するはずだからです。
簡単ですね。
3、その頂点と左右の頂点で三角形を作る
角度が180度以下なので、ちゃんと図形の内部で三角形が作れますね。
4、頂点を取り除く
作った三角形を記録し、さっきの頂点を図形から抹消します。
後は1から繰り返すだけです。
Stop!!
思いもよらぬ三角形ができてしまいました。
なんと三角形の中に他の頂点が入ってしまっています。
これでは当然三角形を構成できないので、
他の頂点を探しましょう。
その前に、この三角形の向きを記録しておきます。
なぜなら他の頂点を使うと、図形の内部で三角形が構成できないことがあるからです。
こうなったり、
こうなったり。
三角形の向きは外積の正負で記録できますので、
この場合、
この二つのベクトルの外積を求めておきましょう。
では、選ぶ頂点を一つ左に動かしてみましょう。
では三角形を構成しましょう。
運良く向きが一緒、内部に他の点が入っていません!
もしも向きが違ったり、内部に点が入っていたりした場合は、さらに別の頂点を選ぶ必要があります。
多角形である以上、
必ず条件を満たした三角形が構成できる頂点がありますので、大丈夫です。
後は、ひたすら同じ作業です。
※↑頂点が分かりにくいので印をつけています。
ついに頂点が3個になりました!
これで分割は完了です。
お疲れ様でした。
≪ ( ゚д゚) | HOME | タワーディフェンス完成! ≫
Author:saharan