捌玖网络工作室 » 网页编程 » C语言中显示 点在多边形内 算法

zw2004 发表于 2008-1-21 17:20

C语言中显示 点在多边形内 算法

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。

_A}4og1f 5I#~9mD
Z`/nl6|
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。
}3O s7qD"P/H%s
TdX!d5M{ 　　首先定义点结构如下：
*]-\abJ~,bnA
K e-zY,d-c.dp 以下是引用片段：
x/~)e8dN 　　/* Vertex structure */ b#O,Bv}
　　typedef struct "b)N%N$V{0^b
　　{ o~"_ |\|'` C
　　double x, y;
f#eSt&K bz+R 　　} vertex_t; !sn
^'h+kxL%c$r@

2giUMfZ]&Q"}-] 4F A4L1T0n]5T
　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：j]5_hUL(M

!{nxhxd&o4} 以下是引用片段：
0Pr:c'ZT*uOI9C"oM 　　/* Vertex list structure – polygon */ rj/S*DqtZ:b
　　typedef struct 5C2{q%?1K%\wv.F
　　{ V$R5] U6CI\
　　int num_vertices; /* Number of vertices in list */

{\\F$X%?r 　　vertex_t *vertex; /* Vertex array pointer */ t$rEyB%HF @`ud
　　} vertexlist_t;
:U9st:XN%~
oo|'S
X1_#L
5F(m%T.~Fz8gd 　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：
5^ p7Ggz4g"mz
(P4f-OAag%`2j 以下是引用片段：
:NH1WEoW C5FX 　　/* bounding rectangle type */
q$jx#~)JI"~ 　　typedef struct
k%hBT$X7t*xW 　　{
V;B[)FQ2j z 　　double min_x, min_y, max_x, max_y;
#I7w4`!}W|?8a 　　} rect_t; q)`&a M4A9i~
　　/* gets extent of vertices */
]v7\-[;uCFS.h 　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ N+{5t1K:r8j+J'}\
　　rect_t* rc /* out extent*/ )
{d _(](? 　　{
gp&GjZ2?y Y$Tl)[~ 　　int i;
m}
S%O$vN 　　if (np > 0){
*@M(f J:k1e 　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; *?$ks&cT!y^.t(g
　　}else{
Y,r
tI0o y E 　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ &cX,u0b#q(R
　　}
.x'o!ZgP6p 　　for(i=1; i  7{V8eY*v mc
　　{ E)V^Vo_A-n
　　if(vl[i].x < rc->min_x) rc->min_x = vl[i].x; ~5`"m?,Nxv
　　if(vl[i].y < rc->min_y) rc->min_y = vl[i].y; }3h(}U-q{O
　　if(vl[i].x > rc->max_x) rc->max_x = vl[i].x;
m4M*l)GyG)|&Nr-h 　　if(vl[i].y > rc->max_y) rc->max_y = vl[i].y; ](]'T0d^cf5O_r'XB
　　}
Im8~]m+Y@\ 　　}
-l$]W,v&M{Rl` 3jq(Qm^U]9C
+{)u){(DfUT
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。u)A,jm&D5c*|%gB
Q.Lh~c;q
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：^er@CHvs

Xrg/K7{;h,\f 　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
3~?l.t.e-I*Xzj4f0M@ GPhOJtM
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
T(v*E#z&GhY-ls0S
Nh.|a%g1\:@yS 以下是引用片段：WP\ dY:YC!S+y
　　/* p, q is on the same of line l */
y rSU2[E.j
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ _)s Z-Sl*G i%F
　　const vertex_t* p,
0zdG~!Pt 　　const vertex_t* q)
7K*@]2pm|a} 　　{
#\#n!\_2K 　　double dx = l_end->x - l_start->x;
Tl;s/?'X 　　double dy = l_end->y - l_start->y; -u3Z J)m/[C!UaG
　　double dx1= p->x - l_start->x;
3NL I-xy5M1i 　　double dy1= p->y - l_start->y;
cT3Z t%U"|,`mA 　　double dx2= q->x - l_end->x;
guA^3|M 　　double dy2= q->y - l_end->y;
il)X7`8T(cR 　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); &G,Y u7H j&D#l"IO
　　}
V(t|,n1M`+n,j 　　/* 2 line segments (s1, s2) are intersect? */ ^S{2}mVd
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, 3M U$|1H)u)|U
　　const vertex_t* s2_start, const vertex_t* s2_end)
~ r:_+wUlo 　　{ 8pP1M7@J-rD
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
"L,Tl u!I A5E 　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
U!{-C|,h'E:j!tZ 　　} dvj#}c5p

dk SJ p!fQVzwr
P`H.r4v%q
W-] 　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
R8r4D/JHl9NZ\
2{
[.V(u pN9d q 以下是引用片段：^G U-w1r~!T,Y
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
)l_b)Iyb tY,u 　　const vertex_t* v) Mua$~9K2y:V`
　　{ 7E7lm&k-r
　　int i, j, k1, k2, c;
`|1e6im8KbuD;F 　　rect_t rc;
9B`i%J#Vu"Df 　　vertex_t w;
+A W"j/F_(jZ 　　if (np < 3) #b K:JN1t
　　return 0; +nKql+i2h!Wu)`
　　vertices_get_extent(vl, np, &rc);
,O)OoZYw6Tx5x[ 　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) 6ZnDC2A$t
　　return 0;
y4G/tQ2v*tJ6H 　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ OkJS.G6w[8es
　　w.x = rc.max_x + DBL_EPSILON; ti)aJ3@8nr[/i
　　w.y = v->y;
$M!|g@K 　　c = 0; /* Intersection points counter */
\A1sx/TZh 　　for(i=0; i  
6U2f;GQ}/C 　　{
H"AcF FvI? 　　j = (i+1) % np;
&S:H2}.Qh q 　　if(is_intersect(vl+i, vl+j, v, &w))
r;v2m:mt-p h 　　{ F&X6~\+|v*~l F
　　C++;
.gP@2mmOVRo;@2e$t 　　}
:xEU1]8i 　　else if(vl[i].y==w.y)
!u%XzB5N)j`g t,m 　　{ b9R9nch[*g7s+J
　　k1 = (np+i-1)%np; i#Ho/ZM!a&g
　　while(k1!=i && vl[k1].y==w.y)
+]c+GQ~;x 　　k1 = (np+k1-1)%np;
dN5a*nt8U R`$| 　　k2 = (i+1)%np; Q"p~RT
　　while(k2!=i && vl[k2].y==w.y) &?NqWz,a,W
　　k2 = (k2+1)%np; ;j{Ht Zk4}-O
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) 'F7Tx.D~.j
　　C++; ,Uk+x:W)MBm$^ F
　　if(k2 <= i) `+p6KV;HA
　　break; r;KT JC*o[!q ^L
　　i = k2;
A0BX PA+A;c 　　} 6\1IWFy%m:U!zE
　　} [8D:mP,`Ic@ ]`
　　return c%2;
E5yJ.Rj$?/H{ 　　} ohD4w;G)i

~VjX+C.k.\U f ,w4k'l%^^-j5J;\
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

查看完整版本: C语言中显示 点在多边形内 算法