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

|
C语言中显示 点在多边形内 算法
本文是采用射线法判断点是否在多边形内的C语言程序。多年前,我自己实现了这样一个算法。但是随着时间的推移,我决定重写这个代码。参考周培德的《计算几何》一书,结合我的实践和经验,我相信,在这个算法的实现上,这是你迄今为止遇到的最优的代码。/ D/ |( J8 \6 K. x' p
! V* W5 z* C v) p( I9 x% H 这是个C语言的小算法的实现程序,本来不想放到这里。可是,当我自己要实现这样一个算法的时候,想在网上找个现成的,考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心,所以,决定重新写一个,并把它放到这里,以飨读者。也增加一下BLOG的点击量。- e- L6 m0 [( K# I3 e- T; m
- F7 ~5 j+ T2 o9 l* C& l 首先定义点结构如下:" R4 j$ q5 p; ?, r% K) I: Y
! L1 \% Y) L3 f' g/ G0 H6 c以下是引用片段:
9 p# {1 w8 K% H# |7 L% Q /* Vertex structure */ 2 H* e. e7 ~( R# a/ ~) `9 |0 U
typedef struct ( g! ?2 y. T6 J
{ ( i/ \" b8 J5 I2 {
double x, y;
3 v4 d4 V7 L- {" `; S# W } vertex_t; . T( q4 w9 G# e1 G0 z# r( E. ]
; t( j" ^9 D9 |$ ?- ]6 P1 q
4 j- W1 g! A4 m+ X 本算法里所指的多边形,是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的,包括多条边在一条绝对直线上。因此,定义多边形结构如下:/ r" k, N: c- v7 E
, r8 L9 U3 v0 x+ p以下是引用片段:) M! j, m0 \6 `( y/ @/ ?
/* Vertex list structure – polygon */
! G# P; r1 g- E typedef struct + h' j9 [; i! v1 k+ L, g
{ + T+ L9 b+ @, V
int num_vertices; /* Number of vertices in list */
& X H# \* C+ t vertex_t *vertex; /* Vertex array pointer */ & h. m. u; c3 X& G! `( v% W
} vertexlist_t;
/ Y2 @+ X' Q6 c4 `4 Y3 b# b- M* h: N6 y; r' I7 `$ f
9 s6 @3 K3 R3 L5 _' c2 C' i
为加快判别速度,首先计算多边形的外包矩形(rect_t),判断点是否落在外包矩形内,只有满足落在外包矩形内的条件的点,才进入下一步的计算。为此,引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent,代码如下:" p3 ]2 g9 A n7 Z. s8 D& g. Q+ N
& V! n: P z8 C( {8 g! e0 B
以下是引用片段:
4 A8 v: k# b# x' u* i0 T. O /* bounding rectangle type */ . [% m+ ^; p: u) ~; z$ Z9 K2 I. L/ [
typedef struct
' x% T' t3 t! q' s. l( V) R {
* p( [1 R" {8 _ double min_x, min_y, max_x, max_y;
+ ~, ~5 U0 G6 B, ~, J } rect_t;
- C" X& d7 G; W) p% A: | /* gets extent of vertices */
% A8 l2 e. i: ^; L void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
7 B2 I* z- a& G* H( d5 [ rect_t* rc /* out extent*/ ) - K T: f( J$ b. F2 I/ O
{ 8 j! x' M9 C; _- z2 a* b! r! F* K
int i; ^" Q0 e' ]0 u5 M
if (np > 0){ 9 v7 A. ~: L. v P
rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
, i: [7 R& S1 D. f% C }else{ . E) ^% N6 g2 X: B- Y# d
rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
! g( B" P, @, b. v } : m, r4 I D" ~& b5 n
for(i=1; i
: z# g$ r( B' o" ~/ ^' Y1 F {
8 b: q/ |+ s5 w7 `3 f! R if(vl.x < rc->min_x) rc->min_x = vl.x; ; \* \- g% ~, V7 g2 I* ~
if(vl.y < rc->min_y) rc->min_y = vl.y; / V# R; I! d# h/ b, o; e
if(vl.x > rc->max_x) rc->max_x = vl.x; , s3 l% J( u3 q: j
if(vl.y > rc->max_y) rc->max_y = vl.y;
2 y7 N# \) c! j9 V2 x. Z }
1 L5 T: Q! L K }
, W7 c: _8 J5 S/ s1 i3 j, E# H
" Q! J; Y! f4 q3 Q/ s
( I" p: {* R& _! `8 k: U7 ~ 当点满足落在多边形外包矩形内的条件,要进一步判断点(v)是否在多边形(vl:np)内。本程序采用射线法,由待测试点(v)水平引出一条射线B(v,w),计算B与vl边线的交点数目,记为c,根据奇内偶外原则(c为奇数说明v在vl内,否则v不在vl内)判断点是否在多边形内。
% ]3 [ |( X i" }+ x, v! ]
' a5 y3 W5 \# T2 R$ k 具体原理就不多说。为计算线段间是否存在交点,引入下面的函数:2 Z3 y+ B! `+ X) h8 U
4 m, z" |" m W
(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start,l_end)的同侧;3 `. x: O$ _6 t6 Z3 H6 |2 n
) t/ P+ t/ }. c4 w
(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;* Z( u7 k) k4 s# k; b% D
7 x' R' B( U% s; F. a! K以下是引用片段:* S' b$ q ?" e0 m, G$ @
/* p, q is on the same of line l */ 7 S o$ M, G: h+ C, m' u" V9 U
static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ & I$ L( F; h8 O, s @
const vertex_t* p, 9 ?7 O" O2 v* r: ]! w+ H
const vertex_t* q) 6 l: L8 l7 L$ \0 S0 X1 \
{ 2 j3 y! o, Z: h% w( l* ^! V
double dx = l_end->x - l_start->x; # H- M7 }( ^" ]# ]) S O6 j
double dy = l_end->y - l_start->y; 6 E' y1 E7 X" B# B& u1 ]* `
double dx1= p->x - l_start->x;
3 A, I* o# `0 _% I* ? double dy1= p->y - l_start->y;
5 _4 W/ }' t p( L/ ` double dx2= q->x - l_end->x; , M8 [) @/ _7 l
double dy2= q->y - l_end->y;
3 \7 L& j! t% K7 G( t- r. B$ ] return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); / G a9 ~$ @) r2 F" V
}
- F0 ?6 j4 N) i$ `) Q- b /* 2 line segments (s1, s2) are intersect? */
4 h8 @( Z2 Z- F+ S static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, 2 y5 {$ |5 X, d- ?# N
const vertex_t* s2_start, const vertex_t* s2_end) 1 O2 t* d: \# z) s( J1 l" B+ U
{ , ]& C7 ]" T S2 a; I
return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && 0 ^2 h% b- q/ x% E# G
is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
8 J9 Y5 D5 O1 x# h: ? } # |1 M* p, d, }' C6 ^* @/ A5 t
0 a- |6 s0 O$ }& D% ~% G( M% a, @6 q& s# n8 y l, i0 P3 P1 y
下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl:np)内的程序:
& f$ K; q: E8 K- b2 G3 w
; _6 t6 y3 o5 R8 x以下是引用片段:
L; Z; ?5 f0 ~# H: p: _/ w int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ * m* w2 r5 x/ _; [
const vertex_t* v)
4 D7 [, P- s" o; x x7 w! V { & M$ f- V8 s0 K( j
int i, j, k1, k2, c; + ~& F' M1 [1 T6 U7 B
rect_t rc;
) W! ~$ Q2 U5 n7 a vertex_t w;
. @7 \) Q6 ^3 f if (np < 3)
& w1 ~& r% S5 A: b( k6 \$ u* g return 0; & Z4 l; W$ B' z/ s
vertices_get_extent(vl, np, &rc); ( w% _2 e9 I3 a/ F3 G6 t& L
if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) $ L$ l' ]( P" _3 O# Q! Q- V
return 0;
{& U: d' s) S; S) W" R; Z3 T! ] /* Set a horizontal beam l(*v, w) from v to the ultra right */ 3 [- ]8 v' l& A4 u' o! P+ t* q
w.x = rc.max_x + DBL_EPSILON; ; E1 |$ h4 j! U# V$ ?
w.y = v->y; 4 P6 a& l# R1 T1 `7 s1 u
c = 0; /* Intersection points counter */ 3 ?. ^& y7 A3 n# B
for(i=0; i
6 K$ E$ {4 Z1 }* h1 @5 j! | {
: P8 |" \5 L5 w N0 R4 c, O4 i; { j = (i+1) % np;
2 b3 P! O* {$ ?3 D* ~ if(is_intersect(vl+i, vl+j, v, &w)) 0 i9 O, b. P' }( _! ^
{ + ]/ s' P% k. r
C++; : V5 L3 Y& o3 G& Y/ k
} 4 y4 }6 u* O( b! i9 @+ N1 R% N
else if(vl.y==w.y) ( _0 E. c' h0 j/ S! b' r
{
4 u% ^# c- x; v/ F k1 = (np+i-1)%np;
! r8 E6 o' [0 ?4 Y5 t' H( Z2 J0 x4 V while(k1!=i && vl[k1].y==w.y) 3 Y3 u9 t/ v. M
k1 = (np+k1-1)%np; P8 Z6 [# {! m g- S
k2 = (i+1)%np;
1 S H+ M/ z8 u3 o while(k2!=i && vl[k2].y==w.y)
7 h6 o; j" r$ L; c2 V& E7 X k2 = (k2+1)%np; / J4 C8 C* Y1 C+ T
if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
. _# y1 f; y1 @( R5 h L7 B C++; 7 l! D9 E) l2 _3 ^6 J& T3 t
if(k2 <= i) 7 @% w7 Y$ i5 i
break; ( a" A' C+ [1 z; S1 U
i = k2; + b. d) _: s2 H9 E. P
} ' W! a2 ], p' G4 C( h8 s+ l. S2 P
}
7 |" M+ z' v& d; e6 K$ B return c%2;
; V* ?% O8 g$ F+ X$ N }
{5 G3 l# b8 Q% s4 x" o, o1 g$ Z' e5 G* w! s
9 W3 r, m& D9 b' j2 E9 k
本想配些插图说明问题,但是,CSDN的文章里放图片我还没用过。以后再试吧!实践证明,本程序算法的适应性极强。但是,对于点正好落在多边形边上的极端情形,有可能得出2种不同的结果。 |
|