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

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

　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。( X" L& u/ b! n' u' _( d( e
( W' X" j- W; A, ~8 E+ M
　　首先定义点结构如下：6 ?! C+ r/ B( p- E3 j
1 L1 k# D9 x4 ^$ Y+ j1 {
以下是引用片段：
　　/* Vertex structure */ - [. J$ @/ f! e$ M% `6 R$ y  V2 Q. o
　　typedef struct
　　{ ; [9 \1 q& `' ]
　　double x, y;
　　} vertex_t; / \. N, h+ T6 m- Z+ `

- K: q( z: y; n5 h
　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：+ _5 o2 z- n# L% M" v
% H- Q+ v5 H% e- W/ ^
以下是引用片段：
　　/* Vertex list structure – polygon */ * t6 S  K6 g  U4 H2 D% u
　　typedef struct
　　{ ; q. M1 n. M6 L' d5 @8 S
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */ - w2 r2 e, ]! U% _
　　} vertexlist_t;

4 O: B7 H  C3 m- I, t9 K
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：

以下是引用片段：, H" H# i* ?" [2 }4 a, B  d5 S
　　/* bounding rectangle type */   k7 R1 C; a+ ]! H2 ^. }
　　typedef struct ! G# J* n# h4 I% u* }5 K+ h5 z+ Z7 K
　　{ 6 C  e, \+ `& _0 M3 Y% `
　　double min_x, min_y, max_x, max_y; 6 {* U" K$ Y. X, k$ N' m( ~* C
　　} rect_t; 6 `0 F' M8 @( J, A3 w* J0 M* R( M/ J3 i
　　/* gets extent of vertices */ : p  Y  Y0 ~" N- l9 e4 o% {
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ " p. j/ z1 d. g7 ]- S2 E" _/ X
　　rect_t* rc /* out extent*/ ) ; X2 f( r& s$ ]* V. L
　　{
　　int i;
　　if (np > 0){ " ]6 @1 `9 b4 _8 V1 r" I
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;   i. E$ t7 `% i% J0 e
　　}else{   D- |: G2 c2 A! O1 l" Y, C$ o
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
　　}
　　for(i=1; i  $ S! X0 f- y! p' O( C! J6 j
　　{ . p3 f0 N; |+ r; L* ~6 x; c
　　if(vl.x < rc->min_x) rc->min_x = vl.x; , |% _2 W: ~7 ^9 d
　　if(vl.y < rc->min_y) rc->min_y = vl.y;
$ h5 c0 \7 n' O- `$ n# q" Q% W6 g　　if(vl.x > rc->max_x) rc->max_x = vl.x;
+ ^9 `7 L4 G  E( M9 W  w6 V3 ~( M　　if(vl.y > rc->max_y) rc->max_y = vl.y;
) \& Z4 C: h2 o　　}   @1 a, J2 [6 M6 p; L
　　} 8 @4 l* W* X7 M" O

) Y& [5 i& ~) z* ]/ i5 N1 H4 p8 ?: b: x
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。1 D( R$ j( V& d# U$ K5 M8 e

" ^, L/ F" G& U0 E　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
& F5 k9 z, x' F& Z4 d8 N5 H6 J2 p3 S! g" E
　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
. X- P5 \7 X* h" W8 o5 H) e9 b) L3 B  h9 i
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
0 |* x  {9 T4 Y
  k) Z+ F) Q/ \0 L) c以下是引用片段：5 N7 X( e$ H/ G+ P! `) D
　　/* p, q is on the same of line l */
1 }3 A- c$ S* M　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ $ v$ \$ T8 w9 W4 D5 m2 u
　　const vertex_t* p, + N+ }* [( D0 M; D
　　const vertex_t* q) + |/ Z& U+ z* ]& Q) _0 F
　　{ 9 B3 ?# k6 `. k  F
　　double dx = l_end->x - l_start->x; ( k8 M# ~( D% h" ~: ~' C  k, r
　　double dy = l_end->y - l_start->y;
+ J( }* r' F. R4 M; u　　double dx1= p->x - l_start->x; 4 O# e0 o( N2 g
　　double dy1= p->y - l_start->y; 0 x, b/ u; E: n: v5 S; p. k1 K$ \
　　double dx2= q->x - l_end->x;
! T1 P: h) ~% O　　double dy2= q->y - l_end->y; 8 A' ~0 E: h. p9 o5 r# X
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); . s0 h4 W3 b" t
　　}
/ A- k( g6 G7 \' Z6 b" k　　/* 2 line segments (s1, s2) are intersect? */
% z1 `5 Z/ U& V2 U- q# d5 Y　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, / t# g* j! \+ N
　　const vertex_t* s2_start, const vertex_t* s2_end) # {  s" d8 F2 R5 p" q; R* S/ r
　　{
9 H2 M8 y3 |$ x# J' D- g) X　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
; l, W: U1 l. u# z# \　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; % |) W6 ~! B$ c5 ?
　　}
. |! W( ^% p1 r
! M! l2 R  L" R9 I
1 D+ @3 _; Y' [　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：$ ~6 U; g, `& x  W& g" D( |: @
% h2 n2 b- _. X4 _
以下是引用片段：/ {9 D( b( ]0 i. P4 Z
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ ' x4 d9 ~* k" A; t
　　const vertex_t* v)
2 S" `/ N; t+ \) o& f6 y　　{ 6 R" `/ Q7 i9 E2 D: S. a
　　int i, j, k1, k2, c; 8 J6 Q5 B3 E% f- y& F
　　rect_t rc; . H; ?' {7 }; j8 r: e
　　vertex_t w; 6 k; d( M4 b' G8 r" {4 U2 B
　　if (np < 3) : o9 V9 D4 y" ?' T, P7 i9 R
　　return 0; ' O0 v5 V9 {+ N+ Q+ n! d
　　vertices_get_extent(vl, np, &rc);
7 ~/ M0 B: ]8 t7 m　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
2 h+ @' a& E9 P7 i% Z$ D9 o　　return 0;
' s7 A: c" }( k8 C% k( j4 n+ j9 y　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
, C5 H  S3 P/ F1 _& I5 ]+ {　　w.x = rc.max_x + DBL_EPSILON;
+ ?9 g6 ]$ m2 v/ F- |　　w.y = v->y;
; ?* @+ z% X, H/ d; {* U　　c = 0; /* Intersection points counter */ 0 `! ?; s& E0 d4 e
　　for(i=0; i
/ c7 P6 g; U' p) N　　{ 5 p& b/ v/ J/ ~0 Q
　　j = (i+1) % np; % \  o0 `# l5 r3 I
　　if(is_intersect(vl+i, vl+j, v, &w)) 7 t: C; {; U& p- ?, {6 X
　　{
% Q9 f2 V7 l) c9 y! [: W. {2 n　　C++;
8 @/ I2 {- c& r3 Y5 l* I. x　　} + Y. U( F' f3 L) e0 E
　　else if(vl.y==w.y) . _  i8 {* t) N
　　{
. v& L) w, L. W: N9 s3 t　　k1 = (np+i-1)%np; - R) u. Y$ d3 p0 \/ _
　　while(k1!=i && vl[k1].y==w.y) ( X/ J/ n0 w5 R- ~
　　k1 = (np+k1-1)%np;
( Z+ H$ [) o% S! {9 |　　k2 = (i+1)%np; $ o1 w% k' w9 M+ f( E
　　while(k2!=i && vl[k2].y==w.y) 5 @' Z+ e- ^% G2 s
　　k2 = (k2+1)%np;
9 |" v+ v+ w3 D4 X2 r7 y# g　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) . C, e" Q3 q/ M2 c5 U
　　C++; ; ]" Y( o: c5 a# p' y
　　if(k2 <= i)
1 ^) l: j% r/ s5 Z+ f  s7 }8 E　　break;
8 m; u3 {" @+ a% ?# R2 w　　i = k2;
8 b) z6 I& _: v% _. g6 P/ t6 p　　}
* N% J; N+ {1 l5 d　　} . [" T, ]6 I7 _
　　return c%2;
7 z$ v1 e- Z- N$ h　　}
& i0 v9 K3 S' s8 b# Y6 I' ^4 o3 S/ y

1 d. B% V/ z& b" t　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

[收藏此主题] [关注此主题的新回复]

[通过 QQ、MSN 分享给朋友]

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

[收藏此主题] [关注此主题的新回复]

[通过 QQ、MSN 分享给朋友]

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