  
- UID
- 133
- 帖子
- 51
- 精华
- 1
- 积分
- 186
- 金币
- 55
- 威望
- 2
- 贡献
- 0

|
C语言中显示 点在多边形内 算法
本文是采用射线法判断点是否在多边形内的C语言程序。多年前,我自己实现了这样一个算法。但是随着时间的推移,我决定重写这个代码。参考周培德的《计算几何》一书,结合我的实践和经验,我相信,在这个算法的实现上,这是你迄今为止遇到的最优的代码。( v- e9 `3 H a* x7 z" X8 L
+ _9 a8 R3 \: X% J8 |
这是个C语言的小算法的实现程序,本来不想放到这里。可是,当我自己要实现这样一个算法的时候,想在网上找个现成的,考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心,所以,决定重新写一个,并把它放到这里,以飨读者。也增加一下BLOG的点击量。
- l d: y- V/ {9 y4 q
' E; v8 G0 v$ z: h0 ~ r7 q, ~ 首先定义点结构如下:% ~. |/ O. K- f5 N
3 o, V B/ K6 c; I/ G! a以下是引用片段:$ ^7 d) W# A4 K6 X3 ^
/* Vertex structure */
5 k4 n% ^" C+ u4 J% ?3 B typedef struct
1 N8 ~$ D# H0 r- ~ { * R2 ^4 V! L1 c* w. Z) J' B
double x, y;
4 l/ T( K3 o" e% q2 R1 j } vertex_t; $ o7 E% V: Z! c. Q/ Y) R- V3 |' \
, c8 V. w! _, y/ F+ j
- J! z: R1 O- x# L0 d 本算法里所指的多边形,是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的,包括多条边在一条绝对直线上。因此,定义多边形结构如下:, @# E& u! f0 V. d, j
+ B. m% {) r' E
以下是引用片段:
& n% j- h' ~8 C* h /* Vertex list structure – polygon */ : D/ r0 C2 F i: O# B1 o4 X! r
typedef struct 8 E0 D4 A9 b* u
{ ' f5 X s& ]" A9 h7 D' H
int num_vertices; /* Number of vertices in list */
9 v/ G2 U, `, {! |& a# ~ vertex_t *vertex; /* Vertex array pointer */
: N4 |# `2 C/ y. f } vertexlist_t; 1 D- ^( |) {% g
2 Y/ x3 Z) w6 E9 O/ v: a
9 ~# ?0 y" J6 E" T$ v
为加快判别速度,首先计算多边形的外包矩形(rect_t),判断点是否落在外包矩形内,只有满足落在外包矩形内的条件的点,才进入下一步的计算。为此,引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent,代码如下:9 u3 \0 J& E! ~2 w D$ z8 \
. E3 O$ N* }8 z7 r' e: x( @) x以下是引用片段:$ x. {0 x. e: O! L
/* bounding rectangle type */ 9 H# B$ e- |5 h1 z# b0 Y0 b
typedef struct & y) O4 g) s3 Q& n4 u! Z' v- Y
{ 0 \6 _, `3 l7 o7 e2 g
double min_x, min_y, max_x, max_y; : c& O, n. v- F" ^4 o1 m7 F, I
} rect_t;
+ O2 J+ k& a9 D: x+ q5 _' q /* gets extent of vertices */
. k1 f) _# o+ I" @6 Q3 T U void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ ( z% M6 H% u# v" q
rect_t* rc /* out extent*/ )
+ T8 x5 i3 F5 \9 h! k {
: y6 N) q0 T5 M" A5 ~0 w int i; , l, L6 ?4 e7 W7 J6 [/ a8 a
if (np > 0){ _9 }+ X9 | a" L$ _8 r+ B% {! Q
rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
v& c: M9 }) T5 h# `% r9 N }else{
5 U/ E5 Z% b/ ]8 V2 W8 R! [- p rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
1 W4 G9 t! ^! ]9 g1 }/ f5 { }
: U; L1 e! K3 Q- k/ ] for(i=1; i 3 v- R. f& h. k5 P* u4 c9 P% a
{ 7 b; D. K2 M( f. G7 M$ R5 p
if(vl.x < rc->min_x) rc->min_x = vl.x;
' j- r7 O! \- p) B0 [' m if(vl.y < rc->min_y) rc->min_y = vl.y;
, x2 d9 D( V7 t H$ L9 X if(vl.x > rc->max_x) rc->max_x = vl.x; + v, H* ~' y, h. T' s
if(vl.y > rc->max_y) rc->max_y = vl.y; + K; H% o+ T+ F v7 t
} 1 y2 F4 M. N- l+ G0 @
} 9 F8 h, y' D P/ Y7 j" u
" f5 t. u9 P# v" |) p
) |; d$ U8 \4 ]" K
当点满足落在多边形外包矩形内的条件,要进一步判断点(v)是否在多边形(vl:np)内。本程序采用射线法,由待测试点(v)水平引出一条射线B(v,w),计算B与vl边线的交点数目,记为c,根据奇内偶外原则(c为奇数说明v在vl内,否则v不在vl内)判断点是否在多边形内。- W6 Z* g9 H% J' G/ Y$ Q: ^9 Z4 m
# U( J! e9 n$ ^* h5 {' v, I/ a 具体原理就不多说。为计算线段间是否存在交点,引入下面的函数:
# u, u0 Z7 Z0 r. L1 U; R& R+ n- W% y o8 ?3 P" U6 j
(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start,l_end)的同侧;
W' x( X7 H( _6 Q! I$ P+ A6 F
1 a' K7 R& [; i" D; d. u (2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;( d/ x$ R3 X8 {) j' t
" D1 ]8 V8 q' E. B) P( n/ U以下是引用片段:+ Y. I9 J% I7 r* J+ W
/* p, q is on the same of line l */ 6 f, B5 u$ t z/ i4 S
static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ ( D& X+ R( P9 \( f8 q
const vertex_t* p, 8 ~' g7 b7 N! U
const vertex_t* q)
* ]+ N/ @; u8 ]4 U7 G# m: O1 o {
6 o' G1 W/ Y9 S9 J0 c g8 z double dx = l_end->x - l_start->x; ; `, B4 S* j+ `! d# B0 G
double dy = l_end->y - l_start->y;
2 P% s4 y+ z* ?2 D2 N4 z double dx1= p->x - l_start->x;
# e: \3 l7 C! u double dy1= p->y - l_start->y;
% g: s; p; G2 X* W% @- z double dx2= q->x - l_end->x;
3 Y$ H# V$ ^' @; k& I1 p double dy2= q->y - l_end->y; \& h: r- |$ ?% M: ]5 n5 ?' |
return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
3 a$ s7 _1 L) K } $ ?6 Q& t2 A. C
/* 2 line segments (s1, s2) are intersect? */ ) w9 ~6 H5 L+ J
static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
0 \: O5 d& @6 Z# E& } y const vertex_t* s2_start, const vertex_t* s2_end) : }4 G" H9 D8 o
{ $ `/ |( C* m ?- I; e$ {
return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && 2 }$ l$ ~' D* m/ z7 {9 C$ i
is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; ' @6 ?7 b( J6 v' ^
}
# ~! Y7 j7 u) |% N7 K: h1 P( O$ a% u7 x, U t3 ?( p6 k2 c. g
* f# @+ p5 s7 m0 k
下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl:np)内的程序:1 ]" O! `8 p# _ f5 {
, P9 s; } }0 Z6 [8 |
以下是引用片段:% J; ^% V* J/ m) S' {( X+ N
int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ 4 K' n- D5 U1 N8 x8 ^( q# R
const vertex_t* v)
7 p" m! } j* E9 B( x/ d9 V' j" m @$ p { 9 H, V$ `7 ?/ n9 w
int i, j, k1, k2, c; + N4 _3 P# ?+ I. S5 R( y2 b* k
rect_t rc; 7 [( A) t/ G; Z, j3 q. f* u* k
vertex_t w; 0 C5 X- L5 U& \. q' m
if (np < 3)
$ y b* g) k6 B' k1 L6 H return 0;
; p. R/ g5 I Q4 ?+ q* E7 a6 V vertices_get_extent(vl, np, &rc);
+ k9 \4 K- f2 G- ^' r9 V, G- Q5 h if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) 0 b& t1 A# z# ]5 z+ F
return 0; + [- n* V7 @. Z) @) [
/* Set a horizontal beam l(*v, w) from v to the ultra right */ ! p9 D: Y! A, e9 |
w.x = rc.max_x + DBL_EPSILON;
0 A* }4 P8 N; l w.y = v->y; ' u6 c& `7 a: [7 K6 M
c = 0; /* Intersection points counter */ 8 S+ {5 w; X- a! P. K; b# V; m
for(i=0; i 5 b1 j' L7 j2 @1 a
{ 0 X; C- v) g) ^8 n9 `5 k' d
j = (i+1) % np;
! P" t: R# ^1 k* t V if(is_intersect(vl+i, vl+j, v, &w))
1 Q1 Z3 W" u C; N% y& n l { # e8 H" ?/ w% c/ J' n
C++;
# m# F; f5 E& H& \ } 8 d- S) c6 `7 d, V6 b2 K
else if(vl.y==w.y) 6 |7 W& @0 R+ R8 x
{ : P6 \, y2 Y7 S7 T
k1 = (np+i-1)%np;
/ }, G! j, n: O# R* a6 Q% e while(k1!=i && vl[k1].y==w.y) ! r" W- I2 _" a
k1 = (np+k1-1)%np;
2 \+ P8 S% u. q* y" u. f& ~' w: n- l k2 = (i+1)%np;
. |. o% \! T9 l, N J# g( ` while(k2!=i && vl[k2].y==w.y)
* x9 u5 a. {3 Z2 X/ }/ E9 t k2 = (k2+1)%np;
' x' U" A% Q, [/ a: `) p) c if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) . k* q S3 n5 c! Q
C++;
" f' E) o: N% v& v* Y3 |- {1 X if(k2 <= i)
5 s. H4 e4 ]! q/ y break;
- W" T; @( j1 b' O i = k2; ' l. P. j+ t6 B8 g1 q
}
9 w0 t% h* `. q! L7 L3 x9 ] }
/ T" [( P1 X4 o. P0 r/ f# a return c%2;
# c y3 c, d8 Z2 F } : _ p2 F# d9 |6 i* L6 K2 {5 z
4 }+ U7 I$ \9 v' o. R7 ?
( T' b4 |& {, c" Z' s 本想配些插图说明问题,但是,CSDN的文章里放图片我还没用过。以后再试吧!实践证明,本程序算法的适应性极强。但是,对于点正好落在多边形边上的极端情形,有可能得出2种不同的结果。 |
|