平面上、整数座標で与えられた点と多角形がある。
その点が、多角形の内部、あるいは、線分(エッジ)にある場合は 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は奇数個の例。
