ホーム > プログラミング > グラフィックス プログラミング > 多角形のループの向き

多角形のループの向き

多角形のループの向き(時計回り/反時計回り)を求めるには?
要素は2次元空間内に存在するものとします。

解法1

解説

多角形の、端(左端や右端、上端、下端)の点を求め、その点とその点の前後の点を用いて、多角形のループの向きを求めることができます。
端の点を点B、点Bの一つ前の点を点A、点Bの一つ次の点を点Cとすると、
点Cが線分ABの右にあるとき、ループは、時計回り
点Cが線分ABの左にあるとき、ループは、反時計回り
です。
※端の点が複数あるときには、複数ある端の点の中のさらに一番端の点を求めます。(左端で処理するとしたときに、左端の点が複数あったならば、その左端の点の中の下端の点を求める。などをします。)

考察

多角形に自己交差があり、判定点が、自己交差部分にある場合には、ループの向きが反対に求まってしまいます。(下図は、ループの向きが反対に求まってしまう図形の例)

解法2

解説

ループの向き判定に備えて、負の値が返ってくることもあるように設計してある多角形の面積計算を用いて、多角形の面積計算を行い、
面積が、正の値なら、ループは反時計回り(もしくは、反時計回りの部分の方が時計回りの部分より大きい)
面積が、負の値なら、ループは時計回り((もしくは、時計回りの部分の方が反時計回りの部分より大きい)
面積が、ゼロなら、ループは潰れている(もしくは、時計回りの部分と反時計回りの部分の大きさが等しい)
と判定します。

考察

多角形に自己交差がある場合でも、適切なループの向きを求めることができます。
解法1よりも速度においては劣りますが、多角形に自己交差があるかもしれない場合には、解法2を使用すべきです。
(「自己交差があるかを判定し、自己交差を除去し、解法1を用いてループの向きを判定」するよりは、「解法2を用いてループの向きを判定する」方が、はるかに高速に処理できます。)

ダウンロード

サンプルプロジェクト


ご意見、ご感想、ご質問、ご要望等は、「コメントを投稿する」もしくは「ホーム > コンタクト」よりお願いいたします。
内容の誤り、誤字脱字、リンクミスなどの問題点を発見された場合には「コメントを投稿する」もしくは「ホーム > コンタクト」より連絡していただけると幸いです。


Copyright (c) 2005-2018 Nobuki HIRAMINE All rights reserved.