|
  
- UID
- 133
- 帖子
- 51
- 精华
- 1
- 积分
- 186
- 金币
- 55
- 威望
- 2
- 贡献
- 0
|
C语言中显示 点在多边形内 算法
本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。8 I! W7 k3 |& t, v' e- r7 }
4 K3 @# T1 T8 w1 P' [8 j3 s: M' [ 这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。
3 [) H1 I+ ?4 I7 P
1 }- \2 g* D. W. k/ i7 n0 x* I- F 首先定义点结构如下：
( L4 b- _- J! h9 x3 A* w+ P
% F" D2 f* j6 I7 N" A2 h以下是引用片段：$ ^3 \! ?' v; p! L0 v$ d" {
/* Vertex structure */ 1 P a/ z( l3 o7 S
typedef struct
5 _: V7 a# v, h4 ^ {
* x8 J: e0 ~- s' }, J( R double x, y;
6 ?$ D: b! d9 Q: N } vertex_t;
0 Z% h/ |& v3 D+ e1 e l7 p; Q; R1 y" H @6 S5 y- Z0 q/ a/ |
" E" [' d! k; e3 M2 N$ K+ K0 s }/ H 本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：6 U* F3 G! l; ]' ^4 ]$ M1 a
: r) q8 \5 x# j6 U2 c8 N1 U以下是引用片段：
. L5 N* v, y" j n/ x: b+ {; F /* Vertex list structure – polygon */
+ A# O( ~- {9 o! _* o typedef struct
# L1 z' s* j: w' d( K5 A2 r3 P {
& Y' K3 i8 W9 f" d0 j; m& p int num_vertices; /* Number of vertices in list */
. w$ U* o+ u9 F+ ?# r8 r3 s% V vertex_t *vertex; /* Vertex array pointer */ . U- t6 g ]) b& U: R- s
} vertexlist_t; % G+ e8 L! y( O3 ^) ^7 k" i/ V, f" Y
! R/ t$ r2 y" G. ~% T; m. x3 J4 U6 y$ P
为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：
' J+ H: M9 ^; | K) F
$ z3 n3 e. p5 I' ~ m+ I以下是引用片段：
4 C" Q' W* V7 l3 C3 n7 Y /* bounding rectangle type */
& W" c( m7 b0 G" r4 `( v- R typedef struct
8 T+ f6 C) O; y5 N7 U* Y4 Y {
% h: V$ t4 t) Z: a double min_x, min_y, max_x, max_y; ! ~6 \7 T3 e p3 N8 m! `/ S- t# a
} rect_t;
. N W* s3 e1 ~. L /* gets extent of vertices */ # K+ i n3 C% ~/ b% d, V5 A: k/ G v
void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
* j0 x" r. f8 S; v* A: \3 A: ?, U. _5 q rect_t* rc /* out extent*/ ) " Y; o) J/ u4 s. X( P" K: g
{
* O% @" A5 B6 F int i; 2 R7 t) I7 f8 N, g' D+ |% W# b$ W, z
if (np > 0){
0 U L# \. z( |+ c: ]- A5 r rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
3 t/ R' Z6 X9 q }else{
) t) F4 ?- [- O; r rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ 9 T! L4 u5 ]) }/ | s: j2 h
} $ O+ m( U# c4 | m
for(i=1; i
, v! j" ]) b; j7 m" ~; Q {
m) l# P( X% |! v8 L if(vl.x < rc->min_x) rc->min_x = vl.x; , d5 H9 Q4 `" `' W8 q7 z: M
if(vl.y < rc->min_y) rc->min_y = vl.y;
( S! v2 l: p; @2 b if(vl.x > rc->max_x) rc->max_x = vl.x;
& Q z6 M; Y9 S( L0 o if(vl.y > rc->max_y) rc->max_y = vl.y;
% ~4 |' S$ B8 `( s } ! K" V1 g; P- k6 a
} 8 [9 t% Z6 }! E6 }; U
1 l2 d( q. ]: w X) D/ r. W# I# P3 D# V) _* l0 w( |3 }
当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。6 d6 a" P7 V, p. j
' E; o6 w$ _6 q7 y4 r 具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
! L8 g0 B3 \* ]' l. F6 I) z, c8 ~0 U% r+ h
(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;( ?( v& M9 D, s% o: M0 Q
) |( ~* ]' z2 f9 m
(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
! L% y3 L7 z, i7 { P& Q
0 ?* n- j) _0 s( r: G以下是引用片段：
$ B4 N! g/ @9 D* W1 I /* p, q is on the same of line l */
$ @# |& V! H$ d2 d. r# r4 e static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
3 d4 b+ _2 P0 I _0 ]4 E9 k7 B const vertex_t* p, + S; S" g/ d+ a' W |3 m
const vertex_t* q)
2 P/ l7 R. C- q# Y: K5 V {
/ B! h' Z9 s9 j2 i double dx = l_end->x - l_start->x;
# M0 t" W9 I0 ^7 K& X9 L double dy = l_end->y - l_start->y;
, @* H- A8 u! ]5 _* ~( w double dx1= p->x - l_start->x; " ]. j/ _7 H3 b0 I
double dy1= p->y - l_start->y;
5 R8 i+ D! y8 Y, \$ U8 n6 Q double dx2= q->x - l_end->x; 1 t, f1 j; B6 p' P( Q
double dy2= q->y - l_end->y;
4 l, ^$ S- W/ C; r return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); $ j4 z9 B1 i1 r3 h$ j, Z: h
} & E0 u8 d+ J0 E1 J* M
/* 2 line segments (s1, s2) are intersect? */ 5 I5 Y6 y; ? Q( f$ ~, W( d
static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
5 T2 q# |& K) I7 M- J: Z5 ? const vertex_t* s2_start, const vertex_t* s2_end) / ^9 Q8 d+ A0 [" r' h& V
{ ( k% Z! _3 V- ]1 b a
return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
" H) ?( ~0 w( J' V9 O0 D7 A. | is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; . G1 o- K7 I2 l% B. f
}
7 z; T! N& y5 G- I8 n; f! S( v
: K9 W. l. j d8 Z' C" {8 }) Z$ z& ~3 c$ o5 O" d. ?& ^
下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：, K& C! H) O4 \8 _; X
2 l) E; w$ [0 h以下是引用片段：
I! q& ?+ }! e6 V int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ ! Z/ ^& v, U4 }: J0 q. g
const vertex_t* v)
" H, x2 m+ L2 Y' A8 ~ {
8 P7 x3 X8 @/ W/ E# x9 ]! F int i, j, k1, k2, c; 6 P2 B) n) j+ [
rect_t rc;
" u* H5 C* N ~* j S& P0 B vertex_t w; , m `' F& K# n0 o5 N3 h1 @
if (np < 3) " ?2 v8 ?( {4 Y( ^/ S) T! c
return 0; 0 x# i0 B2 A5 p% G4 m
vertices_get_extent(vl, np, &rc); ' M8 M0 `: A; w, T
if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
9 S) ?& G$ _1 W return 0;
+ h r+ }5 J0 @ /* Set a horizontal beam l(*v, w) from v to the ultra right */
' D# E4 D3 U! S: l0 { w.x = rc.max_x + DBL_EPSILON;
9 y: _& Y3 k8 w( h: }9 _" n w.y = v->y;
- L: S/ {" C, p- L* I+ @3 Y# d: p* s c = 0; /* Intersection points counter */ / X6 A* Y% K9 n5 T
for(i=0; i
7 c" X0 h" z8 _( T! d' E8 T { , Q; f3 b& f. L* b" J) S
j = (i+1) % np; 7 }/ S0 D0 I% x# D0 }! K
if(is_intersect(vl+i, vl+j, v, &w)) 5 Y" t3 N3 G' T _2 A0 }8 H' v
{ " P8 b& q9 T/ t- I% I
C++; 7 o' {+ y6 C! {$ y/ h* f5 ?& ?; ?2 O
} 5 n# N( m; T/ \: r# x
else if(vl.y==w.y)
1 f# @2 }( }# k3 j" a2 x { : h+ Z; R- @% C+ K0 R6 _$ C: f; i
k1 = (np+i-1)%np; , ~4 k2 N1 t$ D
while(k1!=i && vl[k1].y==w.y) 4 x" N3 p8 a' i- ]7 ?$ h8 z
k1 = (np+k1-1)%np;
3 Y/ D5 G4 [% m k2 = (i+1)%np;
- q' b/ k e. J% [ while(k2!=i && vl[k2].y==w.y) * e+ g' w( Q8 o* \
k2 = (k2+1)%np;
3 ?" X- _) M! S. p% a if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
/ j4 V9 `/ P! ^) X5 U! d, N7 i C++;
0 G8 b3 m% @3 q# c) D' D if(k2 <= i)
3 |# \) `) L" U+ M break; 2 G( e. O8 z" N! [/ Q3 e: e
i = k2; * W# _! X$ _( J6 r% v. d5 C% n
}
E5 w3 c* ^' u& k& Z } + h- p6 }0 {8 r
return c%2; ; S( _* C* R/ W Y0 H+ r& U# t
}
1 Z" K8 E$ u/ D
\, w7 i2 F% W' g" I9 R
6 ?4 u" `7 i# r. [# C 本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。 |
|
发表于 2008-1-21 17:20
|