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

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

　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。

　　首先定义点结构如下：
1 Q) i+ ]  R' e. B0 W9 B
以下是引用片段：6 g0 f/ S* u' K5 W" u" Q2 P: x# a$ Y
　　/* Vertex structure */ ! S* r" ^$ V, }7 @; [( a
　　typedef struct
　　{ 2 _! L9 l* e% D4 l+ v+ h% N
　　double x, y;
　　} vertex_t; 1 X  x( C3 p8 w/ T) f
- z! [0 i) P$ e9 @6 C( @: X) c+ S

　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：" }% w7 k; X* A- ^: u
" K9 j9 y2 X5 C! E5 }% A
以下是引用片段：  ]4 H! V4 O: Q* y* U
　　/* Vertex list structure – polygon */
　　typedef struct ( ?2 }6 E# ^1 i3 B
　　{ + e( ?* u  E% c
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */ / u6 Y. ]9 w1 H- W4 J
　　} vertexlist_t;

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

以下是引用片段：7 Q& o( q0 P+ V# w6 Z7 R) S& p- T+ T
　　/* bounding rectangle type */
　　typedef struct # i: P% f; C$ k) R
　　{ # J1 C8 U; H8 v# U$ T
　　double min_x, min_y, max_x, max_y;
　　} rect_t; : _) ^# _# L7 e0 z! [+ [
　　/* gets extent of vertices */ ( y8 c! a' q' U4 f5 H' |
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ 7 [! r7 p3 p2 v5 ?5 b8 I2 `& Q
　　rect_t* rc /* out extent*/ ) 8 m; q5 u  w" c& \. t  ^
　　{ 7 O5 i- m) [% Y5 K5 p
　　int i; ; y% ]9 n! @8 p+ o  I
　　if (np > 0){ * y" Y, R8 M4 p7 f; m5 W& b
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
　　}else{ 7 ~7 |& m4 b  ~% [! ]
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ 5 o- E" }: H* V: u8 x
　　} & g1 l1 w3 l! i9 s! d9 q& T
　　for(i=1; i  # @& o! s* ]. G6 P( L- D
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
* Z  G( o' [% w5 C: B) g　　if(vl.y < rc->min_y) rc->min_y = vl.y; 9 q! L8 B6 r8 J( C( S
　　if(vl.x > rc->max_x) rc->max_x = vl.x; 5 m+ L- X: C7 X* H8 e
　　if(vl.y > rc->max_y) rc->max_y = vl.y;
8 V/ j! d" _/ ^　　}
) o0 j' b5 y' n$ _+ R6 ?. ]　　} ; L8 l+ x% `' C. @& R: U
. I1 \& z4 _# x  X8 o1 b

; \" C! c% U$ f　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
" T9 [8 A( V$ S# t2 c/ H! I0 n, K$ t' f$ N7 h! o
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
0 L1 P2 W  o/ d4 Z6 g+ o% s& y2 E5 x2 s7 R' H
　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;* @/ Q! {% `8 [/ _6 l' C9 b

　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;$ t4 F* E  \& R. y7 C9 ^' B# H

# Y4 F/ u: G, k2 j以下是引用片段：+ E" r. M1 l) `% H  [3 v
　　/* p, q is on the same of line l */ ' U  Q; w& g+ n. e" q+ }; f
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
2 r# \1 O$ Q$ Z　　const vertex_t* p,
" `# c( T+ ?, L& @1 W- R4 C　　const vertex_t* q) ; W# j6 t- d% V+ R
　　{
6 D# ~9 M4 A0 i- |% o0 S4 o　　double dx = l_end->x - l_start->x; 0 r4 D4 l! X  W
　　double dy = l_end->y - l_start->y;
; U8 X3 w  C5 I7 j$ d6 t　　double dx1= p->x - l_start->x; ! L; G% S3 |" G6 r% x  n
　　double dy1= p->y - l_start->y; ! R! H8 U! y) A7 E1 q- F
　　double dx2= q->x - l_end->x;
7 y2 R( {5 T$ ~$ F　　double dy2= q->y - l_end->y;
+ a+ i. Q* t/ M( V& ~　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
/ C$ J, t) ^1 h% m( A0 |7 C8 ?　　} ' B& F* m4 p' M; l
　　/* 2 line segments (s1, s2) are intersect? */ 1 }, g( R1 `( j; V% b2 t/ x
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, ! G, i& M3 l6 L, V" b$ W- i6 g
　　const vertex_t* s2_start, const vertex_t* s2_end) 8 Y6 E8 E9 m1 Z3 k
　　{
2 m/ K' b$ ^8 Q+ H+ L8 G　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
% n7 S9 z5 n# r- X: I$ H　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
" u6 I1 X: D/ [2 @　　}
7 ^  g6 s9 w; g/ J! G; N5 F  C6 l& @7 d

! s, f( ~) |; j# N　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：; d% N# L) @, U, e* V% v$ w

$ a. |' A5 Y' e* M1 r% y5 F以下是引用片段：
. l: z7 r% }0 O, d; r+ T　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
& z! K+ o4 g/ c5 U4 M, m　　const vertex_t* v) * t& Y, e; q" c, |
　　{ 2 k$ t  O5 m. Z) r3 w
　　int i, j, k1, k2, c;
" ?7 D* ?4 p+ P( Y3 a　　rect_t rc; ) e) y5 ~: w/ x, z* A; S( u
　　vertex_t w;
( w" m: ~; O# k1 M) f, \! v　　if (np < 3)
- I8 H) b- k  B' L# P2 Q　　return 0;
3 \( Y+ E( v  Y. I　　vertices_get_extent(vl, np, &rc);
+ [6 k. _$ F! N/ v2 k) C  r　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) 0 H  Y* t4 G( J% u! c+ S5 ^, ?* @
　　return 0; , n1 E- x: H/ I: Q5 V8 F
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ & b6 U) I! a! |1 h3 g" I8 h. q
　　w.x = rc.max_x + DBL_EPSILON; . ]0 s" t! C& |5 ?
　　w.y = v->y;
/ [' S: ]% Q, f  R* o3 R) s& B　　c = 0; /* Intersection points counter */
9 M* q- P1 i" H- n2 s# |7 I　　for(i=0; i  5 q9 c, g+ R; ?; Y6 ~6 s8 X+ Z$ n
　　{ 2 S% Q; O( y$ ~6 a
　　j = (i+1) % np;
3 b/ M  x4 d* C( u2 g　　if(is_intersect(vl+i, vl+j, v, &w))
' R& g' A" F* i0 w　　{ * N* z- m. F% L, ^
　　C++;
$ r( N2 e' C6 l( B8 V　　} 3 y' Z0 R0 t- ^& i
　　else if(vl.y==w.y)
4 o. l6 B7 h9 ]) v　　{ ( t8 ~9 O. Y# I  B0 p
　　k1 = (np+i-1)%np;
$ q* |' R9 f& j4 D, b/ |　　while(k1!=i && vl[k1].y==w.y)
! s; [( `& j) K6 O　　k1 = (np+k1-1)%np;
) _* a% G' h& J5 b' ~6 M6 e　　k2 = (i+1)%np;
8 z. L  t* n6 s$ c　　while(k2!=i && vl[k2].y==w.y) ( G* c; j6 q: S) ^& ]5 k2 K5 x3 Y
　　k2 = (k2+1)%np; ' _; X! o# I9 N3 V3 P
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
6 i, h( U! e' j: _0 x- f　　C++; 9 J; c% `* t2 u* w6 U, ^
　　if(k2 <= i)
- O; Y. t$ m6 i9 u. u8 _; Y　　break; ; s6 J8 ?* K: m8 E# h  @
　　i = k2;
/ o5 ?* U  V5 s' t' k! y6 a! H　　}
# q2 k5 x2 G$ U5 g　　}
& L* N, M/ Q, M9 I　　return c%2;
( x- h2 \' m* H2 Z0 i1 a　　} 3 ]& S" h5 B7 R3 J7 K5 w9 K+ v
/ p# z3 h) ^! R5 Z7 H  ]6 q/ T+ |

6 S5 G  L* D# J+ ~/ G　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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