判断点在多边形内

By | 08月06日
Advertisement
 1 // Copyright 2000 softSurfer, 2012 Dan Sunday
 2 // This code may be freely used and modified for any purpose
 3 // providing that this copyright notice is included with it.
 4 // SoftSurfer makes no warranty for this code, and cannot be held
 5 // liable for any real or imagined damage resulting from its use.
 6 // Users of this code must verify correctness for their application.
 7  // a Point is defined by its coordinates {int x, y;}
 8 //===================================================================
 9  // isLeft(): tests if a point is Left|On|Right of an infinite line.
10 判断P2点在直线上(P0,P1)
11 //    Input:  three points P0, P1, and P2
12 //    Return: >0 for P2 left of the line through P0 and P1
13 //            =0 for P2  on the line
14 //            <0 for P2  right of the line
15 //    See: Algorithm 1 "Area of Triangles and Polygons"
16 inline int isLeft( Point P0, Point P1, Point P2 )
17 {
18     return ( (P1.x - P0.x) * (P2.y - P0.y)
19             - (P2.x -  P0.x) * (P1.y - P0.y) );
20 }
21 //===================================================================
22 射线法判断点在多边形内
23 // cn_PnPoly(): crossing number test for a point in a polygon
24 //      Input:   P = a point,
25 //               V[] = vertex points of a polygon V[n+1] with V[n]=V[0]
26 //      Return:  0 = outside, 1 = inside
27 // This code is patterned after [Franklin, 2000]
28 int cn_PnPoly( Point P, Point* V, int n )
29 {
30     int    cn = 0;    // the  crossing number counter
31
32     // loop through all edges of the polygon
33     for (int i=0; i<n; i++) {    // edge from V[i]  to V[i+1]
34        if (((V[i].y <= P.y) && (V[i+1].y > P.y))     // an upward crossing
35         || ((V[i].y > P.y) && (V[i+1].y <=  P.y))) { // a downward crossing
36             // compute  the actual edge-ray intersect x-coordinate
37             float vt = (float)(P.y  - V[i].y) / (V[i+1].y - V[i].y);
38             if (P.x <  V[i].x + vt * (V[i+1].x - V[i].x)) // P.x < intersect
39                  ++cn;   // a valid crossing of y=P.y right of P.x
40         }
41     }
42     return (cn&1);    // 0 if even (out), and 1 if  odd (in)
43
44 }
45 //===================================================================
46
47 // wn_PnPoly(): winding number test for a point in a polygon
48 //      Input:   P = a point,
49 //               V[] = vertex points of a polygon V[n+1] with V[n]=V[0]
50 //      Return:  wn = the winding number (=0 only when P is outside)
51 int wn_PnPoly( Point P, Point* V, int n )
52 {
53     int    wn = 0;    // the  winding number counter
54
55     // loop through all edges of the polygon
56     for (int i=0; i<n; i++) {   // edge from V[i] to  V[i+1]
57         if (V[i].y <= P.y) {          // start y <= P.y
58             if (V[i+1].y  > P.y)      // an upward crossing
59                  if (isLeft( V[i], V[i+1], P) > 0)  // P left of  edge
60                      ++wn;            // have  a valid up intersect
61         }
62         else {                        // start y > P.y (no test needed)
63             if (V[i+1].y  <= P.y)     // a downward crossing
64                  if (isLeft( V[i], V[i+1], P) < 0)  // P right of  edge
65                      --wn;            // have  a valid down intersect
66         }
67     }
68     return wn;
69 }
70 //===================================================================

Similar Posts:

  • hdu 2823(旋转卡壳+线段相交判断+点在多边形内判断)

    题意:给出两个点集p和q,求这两个点集之间的最小距离,如果p与q相交,或者p包含q,或者q包含p,则输出0.0000. 思路:先对两个点集各求一次凸包得到s,t两个凸包,用得到的凸包先判断两个凸包是否相交,分别枚举凸包t的每条边是否与s中的边相交,s中的每条边是否与t中的每条边相交,如果相交则输出0.0000,否则再判断两个凸包是否有包含关系,枚举s上的点是否在t内,如果有就跳出输出0.0000,没有的话再枚举t上的点是否在s内,如果有就跳出输出0.0000,没有的话就对两个凸包进行旋转卡壳求两

  • matlab inpolygon 判断点在多边形内

    如何判断一个点在多边形内部? xv= [0 3 3 0 0]; %x坐标 yv= [0 0 3 3 0];%y坐标 x=1.5; y=1.5; in=inpolygon(x,y,xv,yv) plot(xv,yv,x(in),y(in),'.r',x(~in),y(~in),'.b') in=1; xv= [0 3 3 0 0]; %x坐标 yv= [0 0 3 3 0];%y坐标 x=4; y=4; in=inpolygon(x,y,xv,yv) plot(xv,yv,x(in),y(in),

  • poj_1584 A Round Peg in a Ground Hole(凸包判断凸多边形+判断点在多边形内)

    A Round Peg in a Ground Hole Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 6641   Accepted: 2124 Description The DIY Furniture company specializes in assemble-it-yourself furniture kits. Typically, the pieces of wood are attached to on

  • HDU1756 Cupid&#39;s Arrow (判断点在多边形内)

    Cupid's Arrow Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1781    Accepted Submission(s): 661 Problem Description 传说世上有一支丘比特的箭,凡是被这支箭射到的人,就会深深的爱上射箭的人.世上无数人都曾经梦想得到这支箭.Lele当然也不例外.不过他想,在得到这支箭前,

  • 判断点是否在多边形内(包括在多边形上)

    判断点是否在多边形内(包括在多边形上) /** 检查某点是否包含在多边形的范围内(只用与判断在多边形内部,不包含点在多边形边上的情况)~ */ - (BOOL) checkPointWithinPolygon:(PolyVerticesWrapper*)pvw point:(b2Vec2)point { int verticesCount = [pvw verticesCount]; b2Vec2 *ptPolygon = [pvw vertices]; int nCross = 0; for

  • 【算法】判断点在多边形内部

    转自 http://blog.csdn.net/hgl868/article/details/7947272 水平/垂直交叉点数判别法(适用于任意多边形) 注意到如果从P作水平向左的射线的话,如果P在多边形内部,那么这条射线与多边形的交点必为奇数,如果P在多边形外部,则交点个数必为偶数(0也在内).所以,我们可以顺序考虑多边形的每条边,求出交点的总个数. 下面考虑特殊情况,假如考虑边(P1,P2): 1)如果射线正好穿过P1或者P2,那么这个交点会被算作2次,处理办法是如果P的纵坐标与P1,P2

  • 点在多边形内算法比较

    点在多边形内部算法比较 ----by wangsh 判断点在多边形内外是计算机图形学的最基本算法,在计算机图形处理.模式识别. CAD .科学计算可视化以及 GIS 中有着广泛的应用.判断点在多边形内外的算法有主要有定向射线法.角度法.数学公式计算法和网格索引法等方法.角度法要使用复杂的三角运算,计算量大:在工程上应用最多的是定向射线法,这种方法简单.可靠,但其难以处理对边界点及边界与射线共线等特殊情况的处理. 常见的算法是射线法. 该算法顾名思义,即从给定点引一条射线,计算出该点与多边形交点的

  • poj1584——判断凸包,判断点是否在多边形内

    poj1584--判断凸包,判断点是否在多边形内 A Round Peg in a Ground Hole Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 5441 Accepted: 1729 Description The DIY Furniture company specializes in assemble-it-yourself furniture kits. Typically, the pieces of wo

  • 判断点是否在不规则多边形内

    最近项目用到在Google map上判断事发地点,是否在管辖区域内.典型的判断一个点是否在不规则多边形内的例子. 但是Google map没有提供相应的api,找资料发现百度地图提供了,肿么办,为了一个工具类,加入百度地图吗,操蛋,这是不可能的! 百度地图api链接: http://wiki.lbsyun.baidu.com/cms/androidsdk/doc/v3_7_0/com/baidu/mapapi/utils/SpatialRelationUtil.html com.baidu.ma

  • 判断一个坐标点是否在一个无规则的多边形内 (iOS定位服务与地图应用开发:高德地图开发)

    m 之前工作在一家智能设备的公司,做过一个亲友定位监控系统,类似现在比较流行的360儿童手环.所以这里简单介绍定位与地图. 1 定位服务 iOS设备提供三种不同定位途径,蜂窝式移动电话基站定位:WiFi定位,通过查询一个WiFi路由器的地理位置信息,比较省电:GPS卫星定位,通过3-4颗卫星定位,最为准确,但是耗电量大.iOS系统如果能够接收GPS信息,那么设备优先采用GPS,其次是WiFi,最后是基站,开发人员不能选择哪种定位方式. 定位服务使用CoreLocation框架,主要使用CLLoc

Tags: