<模板><计算几何>点与多边形的位置关系

//参数：点P、多边形顶点（顺时针或逆时针）Pt[](下标从0开始)、多边形顶点数n.
//返回：1：外面；
//     -1：里面；
//     0：边上或顶点上

const int INF=0x7fffffff;
const double STD=1e-10;

struct Point
{
	double x,y;
};

struct Segment
{
	Point s,e;
};

int dblcmp (double d)
{
	if (fabs(d) < STD)
		return 0;
	return d>0?1:-1;
}

double cross (Point a,Point b,Point c)
{
	return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

int xyCmp (double p,double min,double max) 
{
	return dblcmp(p-min)*dblcmp(p-max);
}

int BetweenCmp (Point A,Point B,Point C)
{
	if (fabs(B.x-C.x)>fabs(B.y-C.y))
		return xyCmp(A.x,min(B.x,C.x),max(B.x,C.x));
	else
		return xyCmp(A.y,min(B.y,C.y),max(B.y,C.y));
}

int SegmentCross (Segment a,Segment b)
{
	double x1,x2,x3,x4;
	x1=cross(a.s,a.e,b.s);
	x2=cross(a.s,a.e,b.e);
	x3=cross(b.s,b.e,a.s);
	x4=cross(b.s,b.e,a.e);
	if (dblcmp(x1*x2)<0 && dblcmp(x3*x4)<0) 
		return 1;
	else if (dblcmp(x1)==0 && BetweenCmp(b.s,a.s,a.e)<=0 ||
		dblcmp(x2)==0 && BetweenCmp(b.e,a.s,a.e)<=0 ||
		dblcmp(x3)==0 && BetweenCmp(a.s,b.s,b.e)<=0 ||
		dblcmp(x4)==0 && BetweenCmp(a.e,b.s,b.e)<=0)
		return 2;
	return 0;
}

int PointOnSegment (Point P,Segment a) 
{
	if (dblcmp(cross(a.s,a.e,P)) == 0)
		return BetweenCmp(P,a.s,a.e);
	return 1;
}

int PointInPolygon (Point P,Point Pt[],int n)          //点与多边形关系判断函数
{
	int i,count;
	Segment L,S;
	Point Max,temp;

	for(Max.x=INF,Max.y=P.y,L.s=P,L.e=Max,count=0,i=1;i<=n;i++)
	{
		if (i==n)
			S.s=Pt[n-1],S.e=Pt[0];
		else S.s=Pt[i-1],S.e=Pt[i];
		if (PointOnSegment (P,S)<=0)
			return 0;
		else if (S.s.y==S.e.y)
			continue;
		else
		{
			if (S.s.y>S.e.y)
				temp=S.s;
			else
				temp=S.e;
			if (PointOnSegment(temp,L) == -1)
				count++;
			else if (SegmentCross(L,S) == 1)
				count++;
		}
	}
	if (count%2 == 1)
		return -1;
	return 1;
}

最后

以上就是舒心向日葵为你收集整理的<模板><计算几何>点与多边形的位置关系的全部内容，希望文章能够帮你解决<模板><计算几何>点与多边形的位置关系所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。