ある点(x,y)が多角形の内部にあるかどうかを判定するアルゴリズム

ある点(x,y)が多角形の内部にあるかどうかを判定するアルゴリズム
An algorithm to determine if a point (x, y) is inside a polygon

ある点(x,y)が多角形の内部にあるかどうかを判定する
判定のアルゴリズムは以下3ステップ

・判定対象としたい多角形の、最も大きいx座標を求める(xp)。
・判定対象とした点から、x軸並行で上記で求めたxpまでの線分を作成する(lxp)
・線分lxpと多角形を構成するエッジとの交点の数をカウントする(cross num)。
 →交点の数が・・
  奇数なら、点(x,y)は多角形の内部にある。
  偶数なら、点(x,y)は多角形の外部にある。

polygon max x coordinate
cross count

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.

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です