链接：https://pan.baidu.com/s/1uP09vxAg4WVS0El5Y7QHEg
提取码：DyZ2 复制这段内容后打开百度网盘手机App，操作更方便哦参考：#include"time.h&quo；#include<iostream>；usingnamespacestd；//{:多边形相交判断Begin；#defineLINEINTERSECT_CRO；#defineMAX(a,b)(((a)>；#defineMIN(a,b)(((a)<；typedefst下面代码可直接执行。#include "time.h "#include <iostream>using namespace std //{:多边形相交判断 Begin#define LINEINTERSECT_CROSS(ps,pe,p ((pe->x-ps->x)*(p->y-ps->y)-(p->x-ps->x)*(pe->y-ps->y))#define MAX(a,b) ( ((a)>(b))?(a):(b) )#define MIN(a,b) ( ((a) <(b))?(a):(b) )typedef struct XPOINT32Ftag{float xfloat y}POINT32F//返回true 为相交，false为不相交bool cxLineIntersect32F(POINT32F *p1, POINT32F *p2 , POINT32F *p3, POINT32F *p4){if(MAX(p1->x,p2->x)>=MIN(p3->x,p4->x) &&MAX(p3->x,p4->x)>=MIN(p1->x,p2->x) &&MAX(p1->y,p2->y)>=MIN(p3->y,p4->y) &&MAX(p3->y,p4->y)>=MIN(p1->y,p2->y) &&LINEINTERSECT_CROSS(p1,p2,p3)*LINEINTERSECT_CROSS(p1,p2,p4) <=0 &&LINEINTERSECT_CROSS(p3,p4,p1)*LINEINTERSECT_CROSS(p3,p4,p2) <=0)return trueelsereturn false}//判断两个多边形是否交叉，返回值0,1//0为不相交,1为相交int cxPolyCross2_32F( POINT32F *p1,int nP1,POINT32F *p2,int nP2){int i,j POINT32F *ptr00,*ptr01,*ptr10,*ptr11 for ( ptr00=p1+nP1-1,ptr01=p1,i=0i <nP1i++,ptr00=ptr01,ptr01++ ){for ( ptr10=p2+nP2-1,ptr11=p2,j=0j <nP2j++,ptr10=ptr11,ptr11++ ){if( cxLineIntersect32F(ptr00,ptr01,ptr10,ptr11) ){return 1 }}}return 0 }//:}多边形相交判断 End//******************************************************///{:测试代码 Begin//随机产生点坐标,fmin为坐标的最小值，fmax为坐标的最大值POINT32F randPoint(float fmin,float fmax){POINT32F point int fd = (int)(fmax-fmin)point.x = (rand()%fd)+fmin point.y = (rand()%fd)+fmin return point }int main(){int nLines = 10000 POINT32F *rgn0 = new POINT32F[nLines]POINT32F *rgn1 = new POINT32F[nLines]for ( int i=0i <nLinesi++ ){rgn0[i] = randPoint(0,1000)//多边形1的坐标从0到1000rgn1[i] = randPoint(1200,10000)//多边形2的坐标从1200到10000，确保两个多边形不相交，这样运算的时间能够体现出来}//开始计时time_t tBegin = clock() //判断两多边形是否相交cxPolyCross2_32F(rgn0,nLines,rgn1,nLines) //结束计时time_t tEnd = clock() time_t tDif = tEnd-tBegin cout <<"A边数: " <<nLines <<" B边数: " <<nLines <<endl cout <<"用时: " <<tDif <<"毫秒 " <<endl return 0}
