凸包算法-判断凸多边形是否相交

《凸包算法-判断凸多边形是否相交》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、/*凸包算法判断凸多边形是否相交*/#include#include#include#defineMaxNode100015#defineINF99999999intstack[MaxNode];inttop;typedefstructTPoint{doublex;doubley;}TPoint;TPointblack[2005],white[2005];TPointp0;typedefstructTPloygon{TPointp[2005];intn;}TPolygon;TPolygoncovt

2、exb,covtexw;typedefstructTSegment{TPointp1;TPointp2;}TSegment;voidswap(TPointpoint[],inti,intj){TPointtmp;tmp=point[i];point[i]=point[j];point[j]=tmp;}doublemax(doublex,doubley){//比较两个数的大小，返回大的数if(x>y)returnx;elsereturny;}doublemin(doublex,doubley){//比较两个数的大小，返回小的数if(x

3、x;elsereturny;}doublemulti(TPointp1,TPointp2,TPointp0){return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}doubledistanc(TPointp1,TPointp2){returnsqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}intcmp(constvoid*a,constvoid*b){TPoint*c=(TPoint*)a;TPoint*d=(TPoint*)b;do

4、ublek=multi(*c,*d,p0);if(k<0)return1;elseif(k==0&&distanc(*c,p0)>=distanc(*d,p0))return1;elsereturn-1;}voidgrahamScan(TPointpoint[],intn){//Graham扫描求凸包inti,u;//将最左下的点调整到p[0]的位置u=0;for(i=1;i<=n-1;i++){if((point[i].y

5、

6、(point[i].y==point[u].y&&point[i].x

7、i;}swap(point,0,u);p0=point[0];//将平p[1]到p[n-1]按按极角排序，可采用快速排序qsort(point+1,n-1,sizeof(point[0]),cmp);for(i=0;i<=2;i++)stack[i]=i;top=2;for(i=3;i<=n-1;i++){while(multi(point[i],point[stack[top]],point[stack[top-1]])>=0){if(top==0)break;top--;}top++;stack[top]=i;}}boolisIntersecte

8、d(TPoints1,TPointe1,TPoints2,TPointe2){//判断线段是否相交//1.快速排斥试验判断以两条线段为对角线的两个矩形是否相交//2.跨立试验if((max(s1.x,e1.x)>=min(s2.x,e2.x))&&(max(s2.x,e2.x)>=min(s1.x,e1.x))&&(max(s1.y,e1.y)>=min(s2.y,e2.y))&&(max(s2.y,e2.y)>=min(s1.y,e1.y))&&(multi(s2,e1,s1)*multi(e1,e2,s1)>=0)&&(multi(s1,e2,s

9、2)*multi(e2,e1,s2)>=0))returntrue;returnfalse;}boolIntersect(TSegmentL1,TSegmentL2){//线段l1与l2相交而且不在端点上时，返回true//判断线段是否相交//1.快速排斥试验判断以两条线段为对角线的两个矩形是否相交TPoints1=L1.p1;TPointe1=L1.p2;TPoints2=L2.p1;TPointe2=L2.p2;//2.跨立试验if((max(s1.x,e1.x)>=min(s2.x,e2.x))&&(max(s2.x,e2.x)>=min(s1

10、.x,e1.x))&&(max(s1.y,e1.y)>=min(s2.y,e2.y))&&(max(s2.y