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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。" c& h! }2 @  s0 B- o& Y
; w$ ?, f, d6 p8 {4 v' J1 c! g
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。
. P( w+ D. W7 M) N2 V6 ~
　　首先定义点结构如下：1 T$ |3 q+ b  m+ o1 w0 @

以下是引用片段：
　　/* Vertex structure */
　　typedef struct 9 c* T# h& W5 n, G' ~  r+ z6 X/ v; f
　　{ 5 b/ M5 d( _! u& T
　　double x, y;
　　} vertex_t; ; s9 b7 c% w+ A0 g0 [
  t5 z$ V6 M8 C
' q: ~3 l( O1 y: N
　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：

以下是引用片段：4 c0 t5 U  _" g2 d
　　/* Vertex list structure – polygon */
　　typedef struct
　　{
　　int num_vertices; /* Number of vertices in list */ 5 k+ o2 h- T6 K
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t; 6 i4 w) l3 @3 H  E
$ O$ y5 L% ?8 H7 G% S7 \) H0 @

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

以下是引用片段：
　　/* bounding rectangle type */ # k* f0 H2 l. W& i& d; C1 h. Z. x5 R
　　typedef struct ( z* n+ f' C7 R4 n/ w7 E
　　{ / @. ?' p1 w2 N3 V8 }: |0 _: Z* Y0 W
　　double min_x, min_y, max_x, max_y; ) R' g2 Q6 y9 w  T& n4 A* u3 m
　　} rect_t;
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ )
　　{ / d$ f9 p) Q7 o0 A0 s: E3 H1 C1 m
　　int i; ) _! o0 {& x! O7 U  c
　　if (np > 0){ 4 O0 i% C: H- u+ u
　　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 */
　　} $ t+ I. ^3 O& p9 A5 O9 V' E% w) F* L( T
　　for(i=1; i  , W) M5 U9 F' y5 n( L
　　{ # Q' ^( D% ]( D2 |( G1 O
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
3 [) E9 A" Y! D2 N$ D: n5 C　　if(vl.y < rc->min_y) rc->min_y = vl.y; # C: u  O- W+ f+ S+ u. j
　　if(vl.x > rc->max_x) rc->max_x = vl.x;
/ N6 B' z1 C, }9 a0 h2 V　　if(vl.y > rc->max_y) rc->max_y = vl.y;
+ Y9 f) E# S  N+ u! \$ M  O6 ?- \　　} 1 e+ A- K5 u4 M* Y
　　}
* v3 o- |3 j0 Y+ n1 x  g" ?4 a6 ]2 X3 {* I
  b, _$ x0 w' k8 o
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。# d4 O3 |  a7 ^' p8 P9 B% z* R
0 w( a* z. K' T' `+ A' u/ K
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
, |, Z" m$ c! w! a3 M, M
3 |9 k7 F- y6 N# y) a2 d# K　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;: g6 K4 C+ U/ c5 q6 [
# ]/ j9 T( `8 O6 f3 j5 m& D) Y
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
- }( s' O- V- S/ X- B5 o; _$ d$ |2 ~: N# ]) d
以下是引用片段：
$ T4 a: f8 a0 `　　/* p, q is on the same of line l */ ! I8 T/ ]9 L- b* q+ |& T& k" `5 J  F* N
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
) S7 O) l# ^5 r, d4 Z2 j: Q+ Z% m　　const vertex_t* p,
: _3 x( `0 |5 O# C* D　　const vertex_t* q) # q& L& Y- q  n$ _, k) @
　　{ # G9 ?. N8 Z9 |
　　double dx = l_end->x - l_start->x;
4 Y4 t, j8 s( x5 d7 y　　double dy = l_end->y - l_start->y; ( ]6 y: E7 g' g8 o, i3 v3 n" e
　　double dx1= p->x - l_start->x; + ?6 ?/ P, j7 |/ U: a7 H
　　double dy1= p->y - l_start->y;
  b4 o/ t- {5 R& y# b' j　　double dx2= q->x - l_end->x; + H6 d  b' l# }% t9 d5 O
　　double dy2= q->y - l_end->y; % E2 B6 w3 i% U+ l( \
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); ) {* i4 a/ I4 J, a  g# x
　　}
# R* Q. s" G/ |; M$ o. x　　/* 2 line segments (s1, s2) are intersect? */ 6 b& G& \+ v* m9 S
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
. {5 R, |, S5 D- l. b0 i8 O# Y　　const vertex_t* s2_start, const vertex_t* s2_end) $ p: b3 Y+ i- J+ Z7 [1 k1 b
　　{ ( T+ `3 q# T, B0 R: K
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
3 K; v% y' h7 V/ }" |% {, y9 L8 v1 t　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
3 d# r/ _8 u$ X( U　　} 2 O4 U9 C3 k* T+ n! o3 D
; ~" |9 v% i+ \- M6 A* K0 F
1 g- H5 d; r7 l9 v
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
  n9 F, p' {) y3 ]& R5 Y9 S( I  T
; g  N# Z; R7 x! S. B; j' f以下是引用片段：
) p* G  {: Z) i& y- u* J　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ 0 _& w* Q- w, u6 M! [  Q) }2 Y
　　const vertex_t* v)
. Z- M" z/ }  ^0 x5 }& j　　{ 4 T+ ?7 w! L' y, n: p; f
　　int i, j, k1, k2, c; 4 g0 o& ^6 c2 G  v! A
　　rect_t rc;
* L2 r. {* V2 W1 L4 L+ a　　vertex_t w; ! W1 G0 ~2 }& ]5 w& q
　　if (np < 3)
2 Q6 ]( q" E# W; p: z2 z3 e( W　　return 0;
; z& r. {/ ]* r: Q　　vertices_get_extent(vl, np, &rc); - j* H& v" B. f' ~* m+ K) t
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
8 {) l) z, q& f; N/ b! F0 o　　return 0; 1 }$ r' r/ L! o% ^6 Q( ~
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
# K1 ?5 d0 H- D& _! V# ^0 O" \, k　　w.x = rc.max_x + DBL_EPSILON;
7 f3 n9 c! X/ }5 @" {( P' E4 @　　w.y = v->y;
( h; x% r: s3 ?5 y+ P) B　　c = 0; /* Intersection points counter */
1 a( w" g1 T9 d7 n- Y　　for(i=0; i  + P" J* ]3 x  Y# E  N6 j* @
　　{
* l. ]6 i/ C: M5 X6 j　　j = (i+1) % np; : x* F4 p# l/ K9 p( x) H9 W2 {
　　if(is_intersect(vl+i, vl+j, v, &w)) ( w9 P2 l6 a2 _0 T) g
　　{ + O: ~8 D8 x( p
　　C++; " C0 o* {* F* P8 G
　　}
3 n' Y; w4 E, [3 ?- M" c! s/ e　　else if(vl.y==w.y)
6 z! G. M7 {, @9 J) a7 `　　{ 5 O, P, v$ D, d5 |
　　k1 = (np+i-1)%np; # F, h3 j$ R& L
　　while(k1!=i && vl[k1].y==w.y)
0 I8 B8 N- K% K# X% E9 P9 f　　k1 = (np+k1-1)%np; - ?# \' {1 A0 t8 c; ^) b
　　k2 = (i+1)%np; 0 a- J; T) _1 c, j7 E! {1 v
　　while(k2!=i && vl[k2].y==w.y)
1 F. m  T6 T* B. a　　k2 = (k2+1)%np;
/ b! O% f/ \  s( `　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) 1 E: i: l+ \. z. O, M9 i
　　C++;
9 B. t3 x2 |9 G  n1 o! ~! c8 q　　if(k2 <= i)
" ?/ E, D$ t& I; `% w# T8 g　　break;
' s! u  c) U% s6 R( N　　i = k2;
; e' U- P) a; A& z' ]8 D" ?  F1 x　　}   \* P, X- x3 r/ n# y
　　} 8 T: r* n$ Q5 n% R0 u
　　return c%2;
5 I0 H4 m( \# w  P) d% d　　} 3 Y: w. k3 G* p# \2 D5 V9 @5 e

; [/ u& A2 }+ v; g$ q4 R" X4 ^5 _. f  E: ^2 R$ C& v6 q9 p
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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