UVa 634 Polygon

题目描述给定一个简单多边形边与坐标轴平行但算法适用于任意简单多边形及其顶点坐标按顺序给出可能是顺时针或逆时针以及一个待检测的点PPP。要求判断点PPP是否位于多边形内部包括边界。输入包含多组数据每组以顶点个数nnn开始随后nnn行顶点坐标最后一行给出点PPP的坐标。输入以n0n 0n0结束。输出时若点在多边形内部含边界输出T否则输出F。输入格式每组数据第一行为一个整数nnnn≤1000n \le 1000n≤1000表示多边形顶点个数。接下来nnn行每行两个整数xxx和yyy按顺序给出多边形顶点坐标。随后一行包含两个整数为待检测点PPP的坐标。输入以n0n 0n0结束。输出格式对于每个点输出一行字符T表示点在多边形内部或边界F表示点在多边形外部。样例输入4 1 1 1 3 3 3 1 2 2 2 12 1 1 1 9 3 9 3 5 5 5 5 9 7 9 7 1 5 1 5 3 3 3 1 4 2 0输出T F题目分析本题是经典的点与多边形位置关系判定问题。常用的算法是射线法奇偶规则从点PPP向右作水平射线统计该射线与多边形边的交点数。若交点数为奇数则点在多边形内部若为偶数则在外部。若点恰好在边上也应判定为内部。在实现时需要处理射线与多边形顶点相交的边界情况以避免重复计数。通常的解决方案是只统计那些跨越射线水平线且两个端点位于射线水平线两侧或者其中一个端点在射线上另一个端点在上方的边。代码中采用了一种简洁的处理方式对每条边先判断射线与边所在线段是否相交通过方向叉积然后对顶点相交的情况只计数那些边的两个端点都在射线水平线上方即side.start.y ray.start.y side.end.y ray.start.y的情况从而确保每个顶点只被计数一次。解题思路射线法基本原理从点PPP向右作一条水平射线与多边形的边求交。若射线穿过多边形边界奇数次则PPP在多边形内部否则在外部。交点判断对于每条边ABABAB和射线起点为PPP方向向右判断它们是否相交若射线与边无交点则跳过。若射线与边相交于边内部非端点则计数加一。若射线与边的某个端点相交则必须统一规则防止端点被重复计数。代码中采用“只计数边的两个端点都在射线水平线上方”的规则即只有当边的两个端点的yyy坐标都不小于射线起点的yyy坐标时才认为该交点有效。实际上更常见的做法是若射线与边的交点恰好是边的上端点则计数下端点则不计数。代码中的规则与之等价。具体步骤读入多边形顶点数组。构造一条水平射线起点为点PPP终点为xxx坐标足够大的点例如2×2 \times2×多边形最右顶点的xxx坐标确保射线能穿过多边形。遍历多边形的每条边调用segmentsIntersect判断射线与边是否相交。统计相交次数若为奇数则返回true否则false。边界处理点恰好在边上的情况由于题目输入满足一定条件点PPP的坐标均为偶数多边形边长为偶数等但算法中未特殊处理在判断相交时若点与边共线且点在边上则方向叉积为000且点位于边范围内此时应判定为内部。但代码中对于共线情况直接返回false这可能漏掉点在边上的情况。然而根据题目输入的特殊性点PPP坐标为偶数多边形边长为偶数且至少一个顶点坐标为奇数点PPP不可能落在多边形边上因为边上的点至少有一个坐标为奇数或者边长偶数导致边界点坐标奇偶性固定因此可以安全忽略边界情况。为通用性也可增加点在边上的显式判断但代码未做故保持原样。复杂度分析每组数据对每条边进行常数次叉积运算时间复杂度O(n)O(n)O(n)其中nnn为顶点数n≤1000n \le 1000n≤1000。空间复杂度O(n)O(n)O(n)用于存储顶点。代码实现// Polygon// UVa ID: 634// Verdict: Accepted// Submission Date: 2016-08-29// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAX_VERTICES1100;constintEPSILON0;structpoint{doublex,y;};structsegment{point start,end;};structpolygon{intvertexNumber;point vertex[MAX_VERTICES];};// 使用叉积来表示线段的相对方向。doubledirection(point a,point b,point c){return(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}// 判断多边形的边是否在射线上方。boolisSideAboveRay(segment ray,segment side){returnside.start.yray.start.yside.end.yray.start.y;}// 根据设定的交点数规则判断射线与多边形的边是否相交。boolsegmentsIntersect(segment ray,segment side){doubled1,d2,d3,d4;d1direction(ray.start,ray.end,side.start);d2direction(ray.start,ray.end,side.end);d3direction(side.start,side.end,ray.start);d4direction(side.start,side.end,ray.end);// 跨越式相交。if((d1*d20)(d3*d40))returntrue;// 不相交。if((d1*d20)||(d3*d40))returnfalse;// 共线不论线段是否重合均规定为不相交。if((fabs(d1)EPSILONfabs(d2)EPSILON)||(fabs(d3)EPSILONfabs(d4)EPSILON))returnfalse;// 相交于顶点判断是否在射线上方。if(fabs(d1)EPSILON||fabs(d2)EPSILON||fabs(d3)EPSILON||fabs(d4)EPSILON)returnisSideAboveRay(ray,side);returnfalse;}boolisPointInPolygon(pointp,polygonpg){// 找到多边形顶点中位于最右边的点的横坐标。doublerightXpg.vertex[0].x;for(inti0;ipg.vertexNumber;i)if(pg.vertex[i].xrightX)rightXpg.vertex[i].x;intnumberOfIntersection0;segment ray(segment){p,(point){2*rightX,p.y}};for(inti0;ipg.vertexNumber;i){segment side(segment){pg.vertex[i],pg.vertex[(i1)%pg.vertexNumber]};if(segmentsIntersect(ray,side))numberOfIntersection;}// 测试交点个数奇偶性。return((numberOfIntersection1)1);}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);point p;polygon pg;while(cinpg.vertexNumber,pg.vertexNumber){for(inti0;ipg.vertexNumber;i)cinpg.vertex[i].xpg.vertex[i].y;cinp.xp.y;cout(isPointInPolygon(p,pg)?T:F)\n;}return0;}总结本题使用射线法判断点与多边形的位置关系通过方向叉积判断线段相交并采用“端点只计上方”的规则避免顶点重复计数。由于输入数据满足特定奇偶性条件边界情况被简化使得算法可以稳定运行。时间复杂度为O(n)O(n)O(n)空间复杂度O(n)O(n)O(n)适合n≤1000n \le 1000n≤1000的数据规模。此解法是计算几何中点与多边形关系判定问题的经典实现掌握该方法对解决类似几何问题很有帮助。