点在多边形经典算法.docVIP

再经典不过的算法了： // 功能：判断点是否在多边形内 // 方法：求解通过该点的水平线与多边形各边的交点 // 结论：单边交点为奇数，成立! //参数： // POINT p 指定的某个点 // LPPOINT ptPolygon 多边形的各个顶点坐标（首末点可以不一致） // int nCount 多边形定点的个数 BOOL PtInPolygon POINT p, LPPOINT ptPolygon, int nCount int nCross 0; for int i 0; i nCount; i++ POINT p1 ptPolygon[i]; POINT p2 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 坐标 double x 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. 角度和判别法（适用于任意多边形） double angle 0; realPointList::iterator iter1 points.begin ; for realPointList::iterator iter2 iter1 + 1 ; iter2 points.end ; ++iter1, ++iter2 double x1 *iter1 .x - p.x; double y1 *iter1 .y - p.y; double x2 *iter2 .x - p.x; double y2 *iter2 .y - p.y; angle + angle2D x1, y1, x2, y2 ; if fabs angle - span::PI2 0.01 return true; else return false; 另外，可以使用bounding box来加速。 if p.x *iter - boundingBox.left || p.x *iter - boundingBox.right || p.y *iter - boundingBox.bottom || p.y *iter - boundingBox.top 。。。。。。 对于多边形来说，计算bounding box非常的简单。只需要把水平和垂直方向上的最大最小值找出来就可以了。 对于三角形：第四点分别与三角形的两个点的交线组成的角度分别设为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是否在边 P