【经验】如何判断一个点在多边形内部

如何判断一个点在多边形内部：射线法

struct Point { double x;//此处类型根据采用的经纬度类型决定。 double y; }; /*计算点的最大x，y与最小x，y值*/ unsigned char array_MAX_MIN(Point p,Point *pPoly,unsigned char number){ double max_x=0,min_x=0,max_y=0,min_y=0; unsigned char i; for(i=0;i<number;i++) { if(max_x<=pPoly[i].x) { max_x=pPoly[i].x; } if(min_x>=pPoly[i].x){ min_x=pPoly[i].x; } if(max_y<=pPoly[i].y) { max_y=pPoly[i].y; } if(min_y>=pPoly[i].y){ min_y=pPoly[i].y; } } if (p.x < min_x || p.x > max_x || p.y < min_y || p.y > max_y) { return 1; //在四边形之外 } return 0; } //判断点是否在线上，在返回1，不在返回0 int onSegement(Point p1,Point p2,Point Q) { if ((Q.x >=p1.x && Q.x <=p2.x)||(Q.x >=p2.x && Q.x <=p1.x)) // if ((Q.y >=p1.y && Q.y <=p2.y)||(Q.y >=p2.y && Q.y <=p1.y)) return 1; else return 0; } //若有三点A(x1,y1) B(x2,y2) C(x3,y3)共线，则必有向量ab cb共线。即(x1*y2-x2*y1)=(x1*y3-x3*y1) //(y3−y1)(x2−x1)−(y2−y1)(x3−x1)=0 unsigned char Line(Point p1,Point p2,Point Q) { if((p2.y - Q.y)*(p1.x - Q.x) == (p1.y - Q.y)*(p2.x - Q.x) ) return 1; //共线 return 0; } /* 功能：判断点是否在多边形内 // 方法：求解通过该点的水平线与多边形各边的交点 // 结论：单边交点为奇数，成立! // 参数： // POINT p 指定的某个点 // LPPOINT ptPolygon 多边形的各个顶点坐标（首末点可以不一致） // int nCount 多边形定点的个数 //public static bool PointInPolygon(Point p, Point *ptPolygon, int nCount) unsigned char PointInPolygon(Point p, Point *ptPolygon, int nCount) { int nCross = 0,c1=0,c2=0,c3=0; int duanpoint=0; if( array_MAX_MIN(p,ptPolygon,nCount) ){ return 10; //不在多边形内 } for (int i = 0; i < nCount; i++) { Point p1,p2; p1= ptPolygon[i];//当前节点 p2 = ptPolygon[(i + 1) % nCount];//下一个节点 // 求解 y=p.y 与 p1p2 的交点 if (Line(p1,p2,p)) // 共线，不在线上 { if (onSegement(p1,p2,p)) // 点在线段上 return 16; return 17; } /* // 从P发射一条水平射线 求交点的 X 坐标 ------原理: ((p2.y-p1.y)/(p2.x-p1.x))=((y-p1.y)/(x-p1.x)) //直线k值相等 交点y=p.y*/ // if((p1.y>p.y != p2.y>p.y) &&(p.y != p1.y)&&(p.y != p1.y)) //被测点纵坐标要在2点纵坐标之间 if((p.y > p1.y && p.y < p2.y) || (p.y > p2.y && p.y < p1.y)) { double x =(double)( (p.y - p1.y) * (p2.x - p1.x)*1.0 / (p2.y - p1.y) + p1.x ); //交点X坐标 if(x>p.x) { nCross++; } }else if(p.y == p1.y){ double x =(double)( (p.y - p1.y) * (p2.x - p1.x)*1.0 / (p2.y - p1.y) + p1.x ); //交点X坐标 if(x>p.x) { if(p2.y > p1.y) //点算在线上方 nCross++; } }else if(p.y == p2.y){ double x =(double)( (p.y - p1.y) * (p2.x - p1.x)*1.0 / (p2.y - p1.y) + p1.x ); //交点X坐标 if(x>p.x) { if(p1.y > p.y) //点算在线上方 nCross++; } } } // nCross=nCross+duanpoint/2 ; if(nCross==0) { nCross=0; } // 单边交点为偶数，点在多边形之外 --- return nCross; } #define K_LINE 1.19175 //tan50 struct Point Point_all[2160][3840]; void Ctest1Dlg::OnBnClickedOk() { unsigned int i,x,y,count1,count2; i=0;x=0;y=0;count1=0;count2=0; double a1,a2,b1,b2,c1,c2; CString strText = ""; CString szLine = ""; //打开文件 CStdioFile file; file.Open("warpM.txt",CFile::modeRead); file.ReadString( szLine ); int line_zid =0; //逐行读取字符串 while( file.ReadString( szLine ) ) { char * line_data = (LPTSTR)(LPCTSTR)szLine; int col = 0; // char *tokenPtr=(char *)malloc(sizeof(double)*1); char *tokenPtr; Point_all[line_zid][col].x = (int)(atof( tokenPtr=strtok(line_data,","))*8+0.5 ); Point_all[line_zid][col].y = (int)(atof( tokenPtr=strtok(NULL,";"))*8+0.5); col++; while(tokenPtr !=NULL ) { Point_all[line_zid][col].x = (int)(atof( tokenPtr=strtok(NULL,","))*8+0.5 ); Point_all[line_zid][col].y = (int)(atof( tokenPtr=strtok(NULL,";"))*8+0.5 ); col++; if(col == 3840) break; } // free(tokenPtr); line_zid++; } //关闭文件 file.Close(); // TODO: ÔÚ´ËÌí¼Ó¿Ø¼þ֪ͨ´¦Àí³ÌÐò´úÂë //OnOK(); #if (0) for(int y=1;y<2160-2;y++) { for(int x=1;x<3840-2;x++) { //检测某个点是否在区域中 Point p = Point_all[y][x]; Point pt[8]; pt[0] = Point_all[y-1][x-1]; //1 左上方 pt[1] = Point_all[y-1][x-0]; //2 正上方 pt[2] = Point_all[y-1][x+1]; //3 右上方 pt[3] = Point_all[y-0][x+1]; //4 右方 pt[4] = Point_all[y+1][x+1]; //5 左上方 pt[5] = Point_all[y+1][x+0]; //6 左上方 pt[6] = Point_all[y+1][x-1]; //7 左上方 pt[7] = Point_all[y+0][x-1]; //8 左上方 i=PointInPolygon( p , pt , 8); //i为奇数在多边形内，偶数在多边形外 if(i==16) // 点在线段上 { count1++; }else if(i==17) // 共线，不在线上 { count1++; }else if(i%2==0 && i>0) { count1++; } if(count1==200) { count1=0; count2++; } } } #elif (1) for(int y=1;y<2160-2;y++) { for(int x=1;x<3840-2;x++) { //检测某个点是否在区域中 Point p = Point_all[y][x]; Point pt[4],pt2[4]; pt[0] = Point_all[y][x-1]; //1 左上方 pt[1] = Point_all[y][x+1]; //2 正上方 a1=K_LINE; b1=-1; c1=-K_LINE*Point_all[y][x-1].x+Point_all[y][x-1].y; a2=-K_LINE; b2=-1; c2=K_LINE*Point_all[y][x+1].x+Point_all[y][x+1].y; pt[2].x = (b1*c2-b2*c1)/(a1*b2-a2*b1); //3 右上方 pt[2].y = (a2*c1-a1*c2)/(a1*b2-a2*b1); //3 右上方 a1=-K_LINE; b1=-1; c1=K_LINE*Point_all[y][x-1].x+Point_all[y][x-1].y; a2=K_LINE; b2=-1; c2=-K_LINE*Point_all[y][x+1].x+Point_all[y][x+1].y; pt[3].x = (b1*c2-b2*c1)/(a1*b2-a2*b1); //3 右上方 pt[3].y = (a2*c1-a1*c2)/(a1*b2-a2*b1); //3 右上方 pt2[0]=Point_all[y][x-1]; pt2[1]=pt[2]; pt2[2]=Point_all[y][x+1]; pt2[3]=pt[3]; i=PointInPolygon( p , pt2 , 4); //i为奇数在多边形内，偶数在多边形外 if(i==16) // 点在线段上 { count1++; }else if(i==17) // 共线，不在线上 { count1++; }else if(i%2==0 && i>0) { count1++; } if(count1==200) { count1=0; count2++; } } } #else double slope_before=0,slope_after=0; for(int y=1;y<2160-2;y++) { for(int x=1;x<3840-2;x++) { //检测某个点是否在区域中 Point p = Point_all[y][x]; Point pt[2]; pt[0] = Point_all[y][x-1]; //1 左上方 pt[1] = Point_all[y][x+1]; //2 正上方 if(abs(p.y-pt[0].y) > K_LINE*abs(p.x-pt[0].x)) //>50 或 <-50 { slope_before++; } if(abs(p.y-pt[1].y) > K_LINE*abs(p.x-pt[1].x)) { slope_after++; } } } #endif ::OutputDebugString("end\n"); }