点在多边形经典算法

再经典不过的算法了：//功能：判断点是否在多边形内//方法：求解通过该点的水平线与多边形各边的交点//结论：单边交点为奇数，成立!//参数：//POINTp指定的某个点//LPPOINTptPolygon多边形的各个顶点坐标（首末点可以不一致）//intnCount多边形定点的个数BOOLPtInPolygon(POINTp,LPPOINTptPolygon,intnCount){intnCross=0;for(inti=0;i<nCount;i++){POINTp1=ptPolygon[i];POINTp2=ptPolygon[(i+1)%nCount];//求解y=p.y与p1p2的交点if(p1.y==p2.y)//p1p2与y=p0.y平行continue;if(p.y<min(p1.y,p2.y))//交点在p1p2延长线上continue;if(p.y>=max(p1.y,p2.y))//交点在p1p2延长线上continue;//求交点的X坐标--------------------------------------------------------------doublex=(double)(p.y-p1.y)*(double)(p2.x-p1.x)/(double)(p2.y-p1.y)+p1.x;if(x>p.x)nCross++;//只统计单边交点}//单边交点为偶数，点在多边形之外---return(nCross%2==1);}1.叉乘判别法（只适用于凸多边形）想象一个凸多边形，其每一个边都将整个2D屏幕划分成为左右两边，连接每一边的第一个端点和要测试的点得到一个矢量v，将两个2维矢量扩展成3维的，然后将该边与v叉乘，判断结果3维矢量中Z分量的符号是否发生变化，进而推导出点是否处于凸多边形内外。这里要注意的是，多边形顶点究竟是左手序还是右手序，这对具体判断方式有影响。2.面积判别法（只适用于凸多边形）第四点分别与三角形的两个点组成的面积分别设为S1,S2,S3，只要S1+S2+S3>原来的三角形面积就不在三角形范围中.可以使用海伦公式。推广一下是否可以得到面向凸多边形的算法？（不确定）3.角度和判别法（适用于任意多边形）doubleangle=0;realPointList::iteratoriter1=points.begin();for(realPointList::iteratoriter2=(iter1+1);iter2<points.end();++iter1,++iter2){doublex1=(*iter1).x-p.x;doubley1=(*iter1).y-p.y;doublex2=(*iter2).x-p.x;doubley2=(*iter2).y-p.y;angle+=angle2D(x1,y1,x2,y2);}if(fabs(angle-span::PI2)<0.01)returntrue;elsereturnfalse;另外，可以使用boundingbox来加速。if(p.x<(*iter)->boundingBox.left||p.x>(*iter)->boundingBox.right||p.y<(*iter)->boundingBox.bottom||p.y>(*iter)->boundingBox.top)。。。。。。对于多边形来说，计算boundingbox非常的简单。只需要把水平和垂直方向上的最大最小值找出来就可以了。对于三角形：第四点分别与三角形的两个点的交线组成的角度分别设为j1,j2,j3，只要j1+j2+j3>360就不在三角形范围中。4.水平/垂直交叉点数判别法（适用于任意多边形）注意到如果从P作水平向左的射线的话，如果P在多边形内部，那么这条射线与多边形的交点必为奇数，如果P在多边形外部，则交点个数必为偶数（0也在内）。所以，我们可以顺序考虑多边形的每条边，求出交点的总个数。还有一些特殊情况要考虑。假如考虑边(P1,P2)，1)如果射线正好穿过P1或者P2,那么这个交点会被算作2次，处理办法是如果P的从坐标与P1,P2中较小的纵坐标相同，则直接忽略这种情况2)如果射线水平，则射线要么与其无交点，要么有无数个，这种情况也直接忽略。3)如果射线竖直，而P0的横坐标小于P1,P2的横坐标，则必然相交。4)再判断相交之前，先判断P是否在边(P1,P2)的上面，如果在，则直接得出结论：P再多边形内部。射线算法1.已知点point(x,y)和多边形Polygon（x1,y1;x2,y2;….xn,yn;）；2.以point为起点，以无穷远为终点作平行于X轴的直线line(x,y;-∞,y)；3.循环取得(for(i=0;i<n;i++))多边形的每一条边side(xi,yi;xi+1,yi+1)，且判断是否平行于X轴，如果平行continue，否则，i++；4.同时判断point(x,y)是否在side上，