ホーム > プログラミング > グラフィックス プログラミング > 点の多角形に対する内外判定

点の多角形に対する内外判定

点が多角形ループの内側にあるか外側にあるかを判定するには?
要素は2次元空間内に存在するものとします。

解説

内外判定の基本的な考え方として、「内外を判定したい点から発するレイ(ray:一条の光)を仮定し、レイが多角形の辺を何回横切るかを数え、偶数回横切るとき、点は多角形の外側、奇数回横切るとき、点は多角形の内側と判定することができる」という考え方があります。

ただ、この考え方に従って実装を行うと、レイに対して点接触になる点のある多角形や、レイに対して線接触になる辺のある多角形の場合に判定を誤ってしまう実装になることがあります。

下に示す実装では、レイをXプラス方向に発して、多角形の辺がレイを、「上から下に横切るときには横切り回数を1引き、下から上に横切るときには横切り回数を1足すこととする」ことや、「レイの線上にある点はレイより上にあることとする」ことにより、レイに対して点接触になる点のある多角形や、レイに対して線接触になる辺のある多角形の場合でも正しく内外判定できるようになっています。

ダウンロード

サンプルプロジェクト

参考

Graphics Gems Ⅳ:Point in Polygon Strategies


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


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