C言語 格子点が多角形の中にあるかどうか?
こんにちは.
私はプログラミングを勉強しはじめて3ヵ月くらいです.
今、与えられた多角形(例えば、(0,0),(3,7),(5,7),(8,3),(4,1),(1,0)の五点からなる多角形)の内部に格子点が存在するかどうかをチェックする(存在すれば1を返す等)ということをプログラミングを利用して,解決したいと思っています.最終的にはそれを利用して与えられた多角形をビットマップ表示にすることが目的です.
現在ある一つの自分の決めた点に関しては与えられた多角形を打ち込むことによって中か外かを判定する関数はできているのですが、100×100個の計10000個分の格子点に関してすべて中にあるか外にあるかを判定したいのですが、なかなか上手くいきません.
分かる方いらっしゃいましたら、アドバイスやプログラムの方よろしくお願いします.
今できているプログラムをのせておきます.
#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");
}
お礼
早速の回答ありがとうございます。 試してみます^^
補足
あれから、ソ-スコードをいわれたとおり、修正したら無事できました。 小数点のところで、誤差が出ていたなんて思いもよらなかったです。 本当にありがとうございました。