図形の問題
ある閉じた曲線で描かれた任意の図形があります(2次元)。ある点がその図形の内部に含まれるか否かを判定するにはどのようにすれば良いでしょうか?
図形はN-1個の点から成っていて、(x_i,y_i) (i=1,N; x_N=x_1,y_N=y_1)はデータとして蓄えられています。この時、ある点(x,y)がこの図形の内側にあるかどうかを判定したいのです。データ点が多いため、できるだけ効率的な判定法を探しています。
問題の図形はほぼ長方形ですが、所々でこぼこしていたり、大局的に辺が歪曲していたりするため、長方形で近似はできません。