点の集合で囲まれた領域の内外判定

2012/05/29に全面的に書き直されました。

任意の点Aが、任意の多角形（各頂点をP1〜Pnとする）の内部にあるかどうかを判別するには。
もっとも高速な判定アルゴリズムは既に判明している。任意の点Aから、任意の方向に向かって線を引く。その線と、多角形の辺とが交差した回数が奇数であれば任意の点Aは内部になり、偶数であれば外部になる。
なのでプログラム的には、ある方向は任意の点Aのx座標かy座標かどちらかを増加させることで直線の判定を行う。
また、多角形は頂点の集合として捉える。
仮に、x座標を増加させることで解決を図るとする。
1.頂点を取捨選択する。
x座標を増加させるので、x座標が任意の点Aのx座標よりも小さい頂点は、判定の対象にならない。これらの頂点を一旦取り除く。
2.判定の対象になる辺のリストを作る。
1で残った頂点を含む辺のみをリストアップする。（辺は頂点の対として表現できる）
3.交差判定
2でリストアップされた辺と、任意の点Aから伸ばした線との交差を判定する。ここは他の記事を参照すること。
任意の点Aと、それとy座標を同じくしx座標を交差判定の線分のx座標の最大値とするのがよいだろう。
4.偶数奇数判定
3で交差すると判定された線分が何本あるかで、内外が判定できる。