平面上、整数座標で与えられた点と多角形がある。

その点が、多角形の内部、あるいは、線分(エッジ)にある場合は 1と返事、多角形の外部にある場合は0と返事する。

点は整数座標で与えられるものとする。

多角形は頂点数Nが3以上であり(当たり前)、頂点の座標を表す整数の配列 Xk, Yk (ただし、 0<=k<=N-1) が与えられるものとする。

k番目の頂点 (xk, yk) は k+1番目の頂点 (xk+1, yk+1) と腺分でつなぐ。最後のN番目の頂点は最初の1番目の頂点と線分で結ぶ。線分同士は頂点でしかぶつからない。1つの頂点から線分3本以上出ることはないものとする。

<関数名>
  insidePolygon —- 点が多角形の内部にあるかどうかを判定する

<形式>
  int insidePolygon(int x, int y, int pn, int *px, int *py);

<引数>
  x, y  入力 点の座標
  pn   入力 多角形の頂点数
  px, py 入力 多角形の頂点の座標配列

<関数値>
  1  点が多角形の内部、あるいは、ちょうど多角形の線分上にある。
  0  点が多角形の外部にある。

<注意事項>
  多角形の頂点数N は3以上でないといけないが、誤って入力された場合では以下のように処理する。
  N < 1  無条件に 関数値=0 とする。
  N = 1  点の座標と比較し、一致すれば 関数値=1、一致しなければ 関数値=0 とする。
  N = 2  点の座標と線分と比較し、線分上にあれば 関数値=1、線分上になければ 関数値=0 とする。

  関数内の定数 JUST_ONの値をほかのもの(例えば2)にすれば、多角形の線分や頂点に点が乗っかっている場合には、関数値が2として正しく検出される。

  本関数の計算量はO(N)。

用例

<C言語関数本体>
  insidePolygon.c

<説明>
  判定の方法ですが、与えられた点 P から右の水平方向に直線 L を引き、多角形との交点の数を数える。交点の数が偶数(下図1のような、交点のないケースを 0、つまり、偶数とする)なら外部、奇数なら内部と判定する。下図の1,2,4は交点が偶数個、3は奇数個の例。
 

Comments are closed.

Post Navigation