《判断点在多边形内的多种写法.》由会员分享，可在线阅读，更多相关《判断点在多边形内的多种写法.（17页珍藏版）》请在金锄头文库上搜索。
1、判断点在多边形内的多种写法(射线算法) (2010-10-09 17:04:24)转载标签：计算几何射线法杂谈分类：经验总结*射线算法一*1.已知点point(x,y)和多边形Polygon（x1,y1;x2,y2;.xn,yn;）；2.以point为起点，以无穷远为终点作平行于X轴的直线line(x,y; -,y)；3.循环取得(for(i=0;in;i+)多边形的每一条边side(xi,yi;xi+1,yi+1)，且判断是否平行于X轴，如果平行continue，否则，i+；4.同时判断point(x,y)是否在side上，如果是，则返回1(点在多边形上)，否则继续下面的判断；5.判断线si
2、de与line是否有交点，如果有则count+，否则，i+。6.判断交点的总数，如果为奇数则返回0（点在多边形内），偶数则返回2（点在多边形外）。代码：const double INFINITY = 1e10;const double ESP = 1e-5;const int MAX_N = 1000;struct Pointdouble x, y;struct LineSegmentPoint pt1, pt2;typedef vector Polygon;/计算叉乘|P0P1|P0P2|double Multiply(Point p1, Point p2, Point p0)return
3、( (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y) );/判断线段是否包含点pointbool IsOnline(Point point, LineSegment line)return( ( fabs(Multiply(line.pt1, line.pt2, point) ESP ) &( ( point.x - line.pt1.x ) * ( point.x - line.pt2.x ) = 0 ) &( ( point.y - line.pt1.y ) * ( point.y - line.pt2.y ) =
4、min(L2.pt1.x, L2.pt2.x) &(max(L2.pt1.x, L2.pt2.x) = min(L1.pt1.x, L1.pt2.x) &(max(L1.pt1.y, L1.pt2.y) = min(L2.pt1.y, L2.pt2.y) &(max(L2.pt1.y, L2.pt2.y) = min(L1.pt1.y, L1.pt2.y) &(Multiply(L2.pt1, L1.pt2, L1.pt1) * Multiply(L1.pt2, L2.pt2, L1.pt1) = 0) &(Multiply(L1.pt1, L2.pt2, L2.pt1) * Multiply
5、(L2.pt2, L1.pt2, L2.pt1) = 0);/判断点在多边形内bool InPolygon(const Polygon& polygon, Point point)int n = polygon.size();int count = 0;LineSegment line;line.pt1 = point;line.pt2.y = point.y;line.pt2.x = - INFINITY;for( int i = 0; i n; i+ )/得到多边形的一条边LineSegment side;side.pt1 = polygoni;side.pt2 = polygon(i +
6、 1) % n;if( IsOnline(point, side) )return1 ;/如果side平行x轴则不作考虑if( fabs(side.pt1.y - side.pt2.y) side.pt2.y ) count+;else if( IsOnline(side.pt2, line) )if( side.pt2.y side.pt1.y ) count+;else if( Intersect(line, side) )count+;if ( count % 2 = 1 ) return 0;else return 2;*射线算法二*本文是采用射线法判断点是否在多边形内的C语言程序。多
7、年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的计算几何一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。首先定义点结构如下： 以下是引用片段：typedef structdouble x, y; vertex_t;本算法里所指的多边形，是指由一系列点序列组成的封闭简单多
8、边形。它的首尾点可以是或不是同一个点（不强制要求首尾点是同一个点）。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下： 以下是引用片段：typedef structint num_vertices;vertex_t *vertex; vertexlist_t;为加快判别速度，首先计算多边形的外包矩形（rect_t），判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下： 以下是引用片段：typedef structdoubl
9、e min_x, min_y, max_x, max_y; rect_t;void vertices_get_extent (const vertex_t* vl, int np,rect_t* rc )int i;if (np 0)rc-min_x = rc-max_x = vl0.x; rc-min_y = rc-max_y = vl0.y;elserc-min_x = rc-min_y = rc-max_x = rc-max_y = 0;for(i=1; iif(vli.x min_x) rc-min_x = vli.x;if(vli.y min_y) rc-min_y = vli.y;
10、if(vli.x rc-max_x) rc-max_x = vli.x;if(vli.y rc-max_y) rc-max_y = vli.y;当点满足落在多边形外包矩形内的条件，要进一步判断点（v）是否在多边形（vl：np）内。本程序采用射线法，由待测试点（v）水平引出一条射线B（v，w），计算B与vl边线的交点数目，记为c，根据奇内偶外原则（c为奇数说明v在vl内，否则v不在vl内）判断点是否在多边形内。具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：（1）is_same判断2（p、q）个点是（1）否（0）在直线l（l_start，l_end）的同侧；（2）is_interse
11、ct用来判断2条线段（不是直线）s1、s2是（1）否（0）相交； 以下是引用片段：static int is_same(const vertex_t* l_start, const vertex_t* l_end,const vertex_t* p,const vertex_t* q)double dx = l_end-x - l_start-x;double dy = l_end-y - l_start-y;double dx1= p-x - l_start-x;double dy1= p-y - l_start-y;double dx2= q-x - l_end-x;double dy2= q-y - l_end-y;return (dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) 0? 1 : 0);static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,const vertex_t* s2_start, const vertex_t* s2_end)return (is_same(s1_start, s1_end, s2_start, s2_end)=0 &is_same(s2_start, s2_end, s1_start, s1_end
