漳州专业网站建设公司,新型网络营销模式,自驾游网站建设方案,wordpress 置顶排序问题描述#xff1a;已知点P(x,y)和多边形Poly#xff0c;判断点P(x,y)是否在多边形内部。 基本方法#xff1a;射线法 以点P为端点#xff0c;向左方作射线L#xff0c;由于多边形是有界的#xff0c;所以射线L的左端一定在多边形外部#xff0c;考虑沿着L从无究远处开…问题描述已知点P(x,y)和多边形Poly判断点P(x,y)是否在多边形内部。 基本方法射线法 以点P为端点向左方作射线L由于多边形是有界的所以射线L的左端一定在多边形外部考虑沿着L从无究远处开始自左向右移动。 遇到和多边形的第一个交点的时候进入到了多边形的内部遇到第二个交点的时候离开了多边形... 因而当L和多边形的交点数目C是奇数的时候P在多边形内是偶数则P在多边形外。 特殊情况分析如图下图(a),(b),(c),(d)所示。 图(a)中L和多边形的顶点相交交点只能计算一个。 图(b)中L和多边形顶点的交点不应被计算。 图(c)和(d)中L和多边形的一条边重合这条边应该被忽略不计。 代码实现如下 1 typedef struct Point2 {3 int x;4 int y;5 }Point;6 // The function will return YES if the point x,y is inside the polygon, or7 // NO if it is not. If the point is exactly on the edge of the polygon,8 // then the function may return YES or NO.9 bool IsPointInPolygon(std::vectorPoint poly,Point pt)
10 {
11 int i,j;
12 bool c false;
13 for (i 0,j poly.size() - 1;i poly.size();j i)
14 {
15 if ((((poly[i].y pt.y) (pt.y poly[j].y)) ||
16 ((poly[j].y pt.y) (pt.y poly[i].y)))
17 (pt.x (poly[j].x - poly[i].x) * (pt.y - poly[i].y)/(poly[j].y - poly[i].y) poly[i].x))
18 {
19 c !c;
20 }
21 }
22 return c;
23 } 代码分析 条件1((ploy[i].y pt.y) (pt.y poly[j].y)) || ((ploy[j].y pt.y) (pt.y poly[i].y)) 由于判断过程主要是判断射线L与多边形每条边是否存在交点而射线L平行于X轴因此条件1相当于判断点P在Pi和Pj在垂直距离之间。 条件2: (pt.x (poly[j].x - poly[i].x) * (pt.y - poly[i].y)/(poly[j].y - poly[i].y) poly[i].x) 条件2可转换成(pt.x - poly[i].x) * (poly[j].y - poly[i].y) - (poly[j].x - poly[i].x) * (pt.y - poly[i].y) 0相当于向量PiP和向量PiPj的叉积。 当向量PiP和向量PiPj的叉积小于0时向量PiP在向量PiPj的逆时针方向相当于向量PiP在向量PiPj的右侧而射线L由左侧射出而且点P在Pi和Pj在垂直距离之间因此射线L和PiPj的跨立条件成立相交。 参考资料 http://alienryderflex.com/polygon/转载于:https://www.cnblogs.com/xmphoenix/p/4508457.html
