1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

【考え方】図形の中に点があるか。内外判定。

Last updated at Posted at 2020-07-18

図形の中に点があるかどうかの判断のやり方。
#前提条件
以下のように図形の中にあるかどうか判断したい点__P(x,y)__を図形の中にあるものとした時の図形を考える。
triangle.jpg

__O(0,0)__は__原点__を表している。また、__A(2,2)、B(3,1)、C(3,3)は図形の__頂点__を表している。P(x,y)__は__任意の点__である。

#図形の内外判定→外積を使う
__P(x,y)__が__三角形ABC__の中にあるかどうかを外積を使って考える。
以下の図のような図を考える。
triangle2.jpg

この図は$\vec{BP}$と$\vec{BA}$の外積を表している。

これを以下の図のように__外積の矢印が同じ向き__になるように三角形PBC、三角形PCAでも同様にして外積を計算する。
triangle3.jpg

上図は$\vec{BP}$と$\vec{BA}$の外積、$\vec{BC}$と$\vec{BP}$の外積、$\vec{CA}$と$\vec{CP}$の外積を表している。
#計算結果
以上のように計算した__外積がすべて同じ向き(符号)__なら、図形の中にあるかどうか判断したい点__P(x,y)__は図形の中にある。

もしそうでない場合は点__P(x,y)__は図形の外側にある。

#点が図形の外側の時
もし計算した外積が__同じ向き(符号)でない__ときは、図形は以下のようになっている。
triangle4.jpg

これは、$\vec{BP}$と$\vec{BA}$の外積だけ、$\vec{BC}$と$\vec{BP}$の外積、$\vec{CA}$と$\vec{CP}$の外積とは__違う向き(符号)__を表している。

このように点が図形の外側にあると外積の向き(符号)がすべて揃わない。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?