ある点(x,y)が多角形の内部にあるかどうかを判定するアルゴリズム
An algorithm to determine if a point (x, y) is inside a polygon
ある点(x,y)が多角形の内部にあるかどうかを判定する
判定のアルゴリズムは以下３ステップ
・判定対象としたい多角形の、最も大きいx座標を求める(xp)。
・判定対象とした点から、x軸並行で上記で求めたxpまでの線分を作成する(lxp)
・線分lxpと多角形を構成するエッジとの交点の数をカウントする(cross num)。
→交点の数が・・
奇数なら、点(x,y)は多角形の内部にある。
偶数なら、点(x,y)は多角形の外部にある。
It is judged whether or not a certain point (x, y) is inside the polygon
The algorithm of the judgment consists of three steps
· Find the largest x coordinate of the polygon you want to judge (xp).
· Create a line segment up to xp obtained in parallel on the x axis from the point to be judged (lxp)
· Count the number of intersection points between the line segment lxp and the edge constituting the polygon (cross num).
→ Number of intersection points
If it is odd, the point (x, y) is inside the polygon.
If it is an even number, the point (x, y) is outside the polygon.