C言語 格子点が多角形の中にあるかどうか？

こんにちは.
私はプログラミングを勉強しはじめて3ヵ月くらいです.
今、与えられた多角形（例えば、（0,0）,(3,7),(5,7),(8,3),(4,1),(1,0)の五点からなる多角形)の内部に格子点が存在するかどうかをチェックする（存在すれば1を返す等）ということをプログラミングを利用して,解決したいと思っています.最終的にはそれを利用して与えられた多角形をビットマップ表示にすることが目的です.

現在ある一つの自分の決めた点に関しては与えられた多角形を打ち込むことによって中か外かを判定する関数はできているのですが、１００×１００個の計１００００個分の格子点に関してすべて中にあるか外にあるかを判定したいのですが、なかなか上手くいきません.
分かる方いらっしゃいましたら、アドバイスやプログラムの方よろしくお願いします.

今できているプログラムをのせておきます.

#include <stdio.h>
#include <stdlib.h>

/* #define JUST_ON 2 */
#define JUST_ON 1

int insidePolygon(int x, int y, int pn, int *px, int *py);

int insidePolygon(int x, int y, int pn, int *px, int *py)
/* x and y are the vertex I want to know in polygon.
pn is the number of vertex of polygon
*px and *py are the vertex of polygon */
{
int i, j;
int inside;
double yy;

if (pn < 1) return 0;
if (pn == 1) return x==px[0] && y==py[0];

/* Point (x,y) just lies on the edge or vertex of polygon */
for (i = 0, j = pn-1; i < pn; j = i++) {
if (py[i] == py[j] && y == py[i] &&
((px[i]<=x && x<=px[j]) || (px[j]<=x && x<=px[i])))
return JUST_ON;
else if (py[i] != py[j] &&
((py[i]<=y && y<=py[j]) || (py[j]<=y && y<=py[i])) &&
x == (double)(px[j]-px[i])*(y-py[i])/(py[j]-py[i])+px[i])
return JUST_ON;
}

/* Point (x,y) is inside/outside polygon */
inside = 0;
yy = y + 0.5; /* shift y to avoid acrossing the poly's edges or vertices */
for (i = 0, j = pn-1; i < pn; j = i++) {
if (((py[i]<=y && y<py[j]) || (py[j]<=y && y<py[i])) &&
x < (double)(px[j]-px[i])*(yy-py[i])/(py[j]-py[i])+px[i])
inside = !inside;
}
return inside;
}


int main()
{
int ii;
int xx, yy;
int pnpn;
int pxpx[100], pypy[100];
int ret;

printf("Enter (x,y) of a point -> ");
scanf("%d %d", &xx, &yy);

printf("Enter the number of vertics of the polygons -> ");
scanf("%d", &pnpn);

for (ii= 0; ii < pnpn; ii++) {
printf("Enter %d-th vertics's (x, y) -> ", ii+1);
scanf("%d %d", &pxpx[ii], &pypy[ii]);
}

ret = insidePolygon(xx, yy, pnpn, pxpx, pypy);

if (ret == 0) printf("The point is outside the polygon.\n");
else printf("The point is inside the polygon\n");
}

No.5 回答者： ki073 回答日時： 2012/07/11 17:57

No.4です。

泥臭いプログラムを載せたのですが、もっとエレガントな方法があります。
凸多角形（全ての内角が180度以下）に限定したものですが、
x,yが多角形の内側かどうかを判定するのに、まず最初の辺(0,0)→(3,7)を考えます、内側の時は進行方向に向かってみると必ず右側にあります。
次の辺の進行方向に向かってみても右側、一周してみると全部右側になるはずです。
数学的には外積を計算し符号で判定できます。
判定する点を(x,y)とし辺(x1,y1)→(x2, y2)の場合の外積は
(y2-y1)*(x-x1)-(y-y1)*(x2-x1)
になります。線上にあれば0になりますので、全部の辺について０または正（あるいは負）なることを調べればよいわけです。
辺の回る方向によっては正負が変わりますが、外側の場合には必ず正の辺と負の辺の両方があらわれます。
回る方向を気にせずに、全部の辺に対して外積が正負の両方が現れた時には外側、正負の一方と０の場合は内側（あるいは線上）判断できるはずです。
ただし、凸多角形でないとできませんので、最初に凸多角形か判断し、そうでなければ凸多角形になるように分割する必要があります。
凸多角形かどうかも外積の符号で判断できます。

No.4 回答者： ki073 回答日時： 2012/07/10 22:25

見てもよく分からないので、ちょっと作ってみました。

その方が早いので。
なぜ整数型になっているのかなと不思議に思っていたのですが、理由が分かりました。私が作ったのは実数型なので答えは違いますが、実数で計算して判定だけ丸めを考えれば簡単なように思います。（プログラムはそうしているのかな？）

多角形の場合、全部の角度が180度より小さい場合と大きいものが混ざっている場合で考え方を変えないといけません（多分）
質問者さんの例が全部180度より小さいかったので安直にそちらの場合だけにしました。その場合には各辺を伸ばしていっても、図形の内側は必ず他の頂点の存在する側にあります。ということは各辺を通る直線より上か下かで図形の内側かどうか判断できます。例は六角形ですので、直線6本分の判定をしています。
それとy軸に平行な辺があると、y=ax＋bじゃなしにxの値で判断しないといけませんが、ここではサボッています。傾きが無限大になりますので私の書いたプログラムではエラーになります。

180度以上の角度がある場合には、補助線を引いて三角形なり、180度以下になる四角形に分解してやれば簡単にできます。
プログラムが読む気力がなかったので、もしそのように考えているのでしたら、ごめんなさい。

Rubyで書いてましたので一応載せておきます。
points=[[0.0,0.0], [3.0,7.0], [5.0,7.0], [8.0,3.0], [4.0,1.0], [1.0,0.0]]
insidepolygon_funcs=(points+points[0..1]).each_cons(3).collect{|xy1, xy2, xy3|
a=(xy1[1]-xy2[1])/(xy1[0]-xy2[0])
b=xy1[1]-a*xy1[0]
# 直線の上か下かによって判定する関数を作成
xy3[0]*a+b>xy3[1] ? lambda{|x, y| x*a+b>=y} : lambda{|x, y| x*a+b<=y}
}
# test
[[1.0, 1.0], [-1.0, 0.0], [10.0, 0.0]].each do |x, y|
p insidepolygon_funcs.all?{|f| f[x, y]}
end

No.3 回答者： kmee 回答日時： 2012/07/10 21:55

とりあえず、insidePolygonが正しいと仮定します(検証が面倒なので)

10000個の点について判定したいのなら、一番単純な方法は10000回書くことです。

ret = insidePolygon(0, 0, pnpn, pxpx, pypy);
if (ret == 0) printf("The point(0,0) is outside the polygon.\n");
else printf("The point(0,0) is inside the polygon\n");

ret = insidePolygon(0, 1, pnpn, pxpx, pypy);
if (ret == 0) printf("The point(0,1) is outside the polygon.\n");
else printf("The point(0,1) is inside the polygon\n");
(以下略。合計10000個)


そんなのやってられないから、for等でループにするわけです。
for(i=0;i<10000;i++){
xx=i番目のx座標;
yy=i番目のy座標;
ret = insidePolygon(xx, yy, pnpn, pxpx, pypy);
if (ret == 0) 略
}

100x100なら、二重ループにするのがいいかもしれません。

あとは、結果を文字で出力する代りに、配列に入れたり、対応する座標の色を変えたりすればよいでしょう。

No.2 回答者： Tacosan 回答日時： 2012/07/10 17:06

「insidepolygonの関数のなかの変更が上手くできない」とか「mainの中でforループまわすだけではうまくいってくれなくて」っていわれても, 何のことやらさっぱりわかりません. もっと具体的に, 何がどうダメなのか説明できませんか (ただし説明があったとしても私が答えるとは限りません. 念のため)?

ああ, この関数で本当にうまく動くかどうか私は確認していません. めんどくさいし, 厳密に考えだすと難しそうなので.

No.1 回答者： Tacosan 回答日時： 2012/07/10 01:33

1つの点に対して判定できるなら 10000個の点でも同じことでしょ?

単にループするだけ.

この回答への補足

insidepolygonの関数のなかの変更が上手くできないんです・・・
mainの中でforループまわすだけではうまくいってくれなくて困っています。

補足日時：2012/07/10 03:27