各辺の内側判定による内外判定 前回の所で、外積を用いて直線の左側・右側を判定する手法を紹介しました。 これを利用して点の内外判定を行います。 例えば、下のような例を考えるとわかりやすいかと思います。 左の三角形の辺を、AB、BC、CAと右回りになるように辺を見ていきます。 三角形の中の点Pは、各辺の常に右側にあることがわかります。 点QはBC、CAの右側になってはいますが、ABの左側にあります。 逆にAC、CB、BAと左向きに回ったときは点Pは常に左側にあります。 要は、「辺をぐるっと回った時、常に点が同じ側にある→多角形の内側にある」と言うことが出来ます。 左の図の例では、点Pは右回りに辺を回った時常に右側にあります。 右回りに回った時に常に左側にある、と言う事はありえません。 上の図を見て、右回りに回った時常に左側に来るという領域は存在しない事がわかります。 そのため、実際は辺を左回り