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

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

　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。# A5 W( O4 V  i' p' g
4 v! U3 }1 ^, F8 G, u& {
　　首先定义点结构如下：7 q. F4 {  z2 z1 _( g/ s
8 G2 z, k* h; ?7 w( P/ N- \
以下是引用片段：* @; C  X7 C! U4 g5 k$ V
　　/* Vertex structure */
　　typedef struct : d6 g$ z2 w6 b. y8 c) |
　　{ - w, X6 H$ u( D7 Z9 m
　　double x, y; . f1 O  t& z; Q/ n( b8 v
　　} vertex_t;

　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：8 V) `# j4 b  |7 x( Y: a8 q
+ l5 [# f4 `2 H! o/ A( t
以下是引用片段：6 H/ ~+ B& W# j) f5 l
　　/* Vertex list structure – polygon */ * t  C  }) f8 \
　　typedef struct
　　{
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t;
2 [6 n( ^1 H' V# [4 a: _
5 Y: n' P$ ?+ X! a) I9 O
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：
' }, X* K! I) m6 m( s
以下是引用片段：
　　/* bounding rectangle type */ 0 v) }  @- `, N/ i: Q0 i5 S, R
　　typedef struct
　　{ 6 A0 d, d2 |& t8 z. |! C
　　double min_x, min_y, max_x, max_y;
　　} rect_t; ) y2 _* ]. Q- k0 b
　　/* gets extent of vertices */ * z+ u8 _% S' a3 H, ~8 R
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ )
　　{ : S! A/ `0 W4 [3 A$ u# E% Z! L( Z
　　int i; : `/ d" X. [& o, H7 w
　　if (np > 0){ 6 K" e- m/ _- ^4 V- D( d% ?
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
　　}else{
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
　　} / v7 Y4 `, s9 [8 X. W+ t' p+ ^
　　for(i=1; i  7 Q/ R6 i+ L& |2 n. D
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
. L% ~; q. e' C0 |, c7 F/ ?　　if(vl.y < rc->min_y) rc->min_y = vl.y;
0 Z* V' t6 y8 R6 p% J% m　　if(vl.x > rc->max_x) rc->max_x = vl.x; 4 J$ V/ D6 k/ Q2 F; l" W0 Z6 Q
　　if(vl.y > rc->max_y) rc->max_y = vl.y;
# U' a" R' D. {  ^# e( D　　}   W7 ]/ I* K& o! v/ S
　　} ' G8 K+ J6 Q" `- S' d( ^8 R
, [* k! U( H* r% g) z6 O

' ?7 t) v2 I  {& R7 u' i　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。3 b) w# H0 E/ |! A) A$ q! X; Z
$ L6 E9 M( \1 ^2 F% P! ]
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
- G0 T! t8 T' R
9 |# }& R; \. N: F+ g) G2 d" s　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;, N! N1 L- y" v
$ l2 d$ A: m& O1 X# {3 r* z* M
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
; F/ U% i. e5 J' c+ F' V4 g7 L/ J" |5 u$ |5 v- {: `, `
以下是引用片段：8 {# @8 |9 D3 \$ c; x4 k
　　/* p, q is on the same of line l */ ) ]) t! w0 ~- [1 n$ `, m+ X
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ . L: ^5 u6 O- [
　　const vertex_t* p,
+ B/ ]5 g; E/ P( J! |5 L7 s　　const vertex_t* q)
* o  m1 W/ k, L; `) [　　{ ( r$ K( Q* I; {7 q+ d9 J
　　double dx = l_end->x - l_start->x;
: s/ n5 {5 ^: G　　double dy = l_end->y - l_start->y;
, i- g" R. R% I" O5 e　　double dx1= p->x - l_start->x;
2 r* w: \2 `7 J　　double dy1= p->y - l_start->y;
: u, @5 F' R* X; M6 P　　double dx2= q->x - l_end->x; / D2 z1 k/ V/ E: J2 f( |- |, A
　　double dy2= q->y - l_end->y;
# T  h5 k0 x$ [, @　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); ' i" w% `) m( p$ |8 P
　　} / l6 O. Q( N  E, K2 U7 F5 W4 n
　　/* 2 line segments (s1, s2) are intersect? */
) U' u; o2 B6 E5 ?4 q　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, " ~( d% ?2 [" M  h- U9 a0 U
　　const vertex_t* s2_start, const vertex_t* s2_end)
# U0 [# @* g+ a9 I: ~　　{
% V. r" A. U8 j7 t1 {+ o2 {　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && & @* n, n6 I% ?5 A
　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; - ^& z& _' z; T( F  y- x
　　} 8 n6 _- X# I% B9 A/ h
, Z3 T& l+ Z- V0 Z6 ]

0 S5 F; {. p: F5 m* |3 ]# }　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
9 B; t7 ]$ A: H  R$ e+ J1 K
* S  X0 u' Y8 ~% |以下是引用片段：
# ?) H6 Y% t7 S9 j% m' ^  K　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
% h( F8 ]( b2 @# ^1 H& B. y, T　　const vertex_t* v) & m1 d+ \- p3 _
　　{
6 U4 g2 x" T2 A  K　　int i, j, k1, k2, c;
4 l$ a% }4 D: f% ]3 k& v! L) ]　　rect_t rc;
3 l; Y: @+ @' [/ |　　vertex_t w;
/ y0 Q; h" j# `" d* h( r　　if (np < 3)
7 j; R0 c& B' X! }2 ]$ |　　return 0;
# l; b# Y1 r5 ?9 f& j- K$ \6 I+ R　　vertices_get_extent(vl, np, &rc); % x" ?5 a) J2 {3 G/ w
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) ! R9 [9 v! v: ?* n4 K! b; ]
　　return 0;
. [. k: `8 L" s　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ / _4 g1 q  N0 J9 L; k
　　w.x = rc.max_x + DBL_EPSILON;
0 K8 p; L: R# Z4 @　　w.y = v->y; # l( f$ l3 y4 ]3 o3 z
　　c = 0; /* Intersection points counter */
! @4 S$ L0 B4 j& I' c( ]1 {" I$ q　　for(i=0; i
( M% y0 ?( F' {0 b% B　　{ " c1 Q: a  J4 @6 ?1 w$ k
　　j = (i+1) % np;
! f& e2 _+ ~: y# z. |" l5 n　　if(is_intersect(vl+i, vl+j, v, &w)) 3 F& Z+ Q/ T* f" ^8 m* E
　　{ " R# u8 m+ `+ e3 Y
　　C++; # a) G( P. s3 B" Q% f- o/ r
　　}
: Y( N1 `8 W& u+ K$ p: c3 r- n　　else if(vl.y==w.y) 6 _- W: J  t: j( T. {+ d& Y
　　{ ; \. _6 d( V8 D
　　k1 = (np+i-1)%np;
7 l2 N+ S. x/ M) P: m　　while(k1!=i && vl[k1].y==w.y)
, t) R# X" J3 ?( Y2 `　　k1 = (np+k1-1)%np;
* X7 F+ K. J, S8 ^3 N2 v　　k2 = (i+1)%np;
* I0 m2 Q7 C0 x' M9 ^( P　　while(k2!=i && vl[k2].y==w.y) 1 ]) E+ z4 ~* \8 \
　　k2 = (k2+1)%np;
6 K7 |& r/ B; K' C( v# D7 U　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
& N& t$ E. ?. D% b　　C++; $ i. y6 I: a$ M' ~
　　if(k2 <= i)
2 Z( a- J1 V' ^/ d　　break;
: r3 R: v" u" h2 e' |9 Q　　i = k2; 7 }1 v! C% P% e! z. D
　　} ) A8 h/ a6 `' O. F4 E1 e/ T5 K
　　} 9 g, o& e9 v& C; E: g' Y  `
　　return c%2;
: _. Y: |2 m1 Y! X1 _　　} 2 D5 `+ f0 \3 w8 o! [1 I4 u

; ]$ p% i! C, a, {  x" R' Z& C/ a3 X) ^: u. g" N( S# V+ c
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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