点の内部判定(ポリゴン)

#define  MAX 256

typedef struct {
		double x, y;
	} Point;

typedef struct {
		int n;
		Point p[MAX];
	} Polygon;

int isCross(double y, Point p1, Point p2, Point *cp)
{
	if(p1.y > p2.y)
	{
		Point p;
		p = p1;
		p1 = p2;
		p2 = p;
	}
	cp->x = (p1.x * (p2.y - y) + p2.x * (y - p1.y)) / (p2.y - p1.y);
	cp->y = y;
	if(p1.y <= y && y < p2.y)
		return 1;
	else
		return 0;
}

int inPoly(Point p, Polygon poly)
{
	int i, j;
	int count = 0;
	Point cp;

	for(i = 0; i < poly.n; i++)
	{
		j = ( i + 1 ) % poly.n;
		if(isCross(p.y, poly.p[i], poly.p[j], &cp))
		{
			if(cp.x > p.x )
				count++;
		}
	}
	return count % 2;
}

int main()
{
	Polygon poly = {3, {{0.0, 0.0}, {0.0, 1.0}, {1.0, 0.0}}};
	Point p1 = {0.5, 0.0};
	Point p2 = {-0.2, 0.5};
	Point p3 = {0.2, 0.2};

	printf("%d\n", inPoly(p1, poly));
	printf("%d\n", inPoly(p2, poly));
	printf("%d\n", inPoly(p3, poly));

	return 0;
}