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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。
* ^+ v. ?2 h4 ^: x$ ~
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。6 h) @( G9 `# e4 g& b8 Q% O) L1 l

　　首先定义点结构如下：

以下是引用片段：1 V/ [" m( _1 `( X6 ^
　　/* Vertex structure */ 2 x* J: r9 x- v
　　typedef struct
　　{
　　double x, y;
　　} vertex_t;
* d* Z% ~* @8 E6 F0 {: ~% n

　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：) z3 Q* c6 j2 ?# s0 Z, q

以下是引用片段：
　　/* Vertex list structure – polygon */
　　typedef struct
　　{ 5 r: e4 `% J; ~  g2 `8 Q
　　int num_vertices; /* Number of vertices in list */ ! O! y+ h# T0 V2 J# [  E" i5 c$ o5 h
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t;

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

以下是引用片段：
　　/* bounding rectangle type */ $ J& v) C: b3 K
　　typedef struct & o5 l) I/ u/ @
　　{
　　double min_x, min_y, max_x, max_y;
　　} rect_t;
　　/* gets extent of vertices */ - w% D+ A# ~6 D& p& U. P: C6 _& B
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ , Z: ?* C" S" E; ?4 X, r7 ]$ R; i$ m
　　rect_t* rc /* out extent*/ ) * K. |: ~3 @- ]" [
　　{
　　int i;
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
　　}else{ - k6 j, E' U3 N9 }. O, u: f
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
　　} * u( G  V6 x3 m8 F8 E
　　for(i=1; i
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
) ]9 B; r; l+ e　　if(vl.y < rc->min_y) rc->min_y = vl.y; - `) s1 K( U, H3 V2 k) R
　　if(vl.x > rc->max_x) rc->max_x = vl.x;
* x3 N- H3 _$ _1 F* u　　if(vl.y > rc->max_y) rc->max_y = vl.y; ' ?8 U1 E7 a4 y) d: T
　　} ) a" g5 u0 k9 M9 F
　　}
* ~! \' m! m" J( V: ], c0 ?: T1 P" ]4 q" M3 [  r$ }2 R9 q% r/ f2 B# |
9 M- u* u2 G, K% d' a. w
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。% r# L, y5 h6 n# X; u+ ?# q

" X: ?( u+ G: ?( f" b　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：: `+ ~' n1 T7 P; G. O

' j6 H) V' |, p$ e  ?　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;) V& z6 X3 O* {# G' d

$ p& R; p% }( [% O　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
' Z2 K7 k8 y* ]- k) K8 p
  k6 v# d! v9 i/ M- Q, r6 H+ k# J以下是引用片段：
1 S  F' H5 z" e　　/* p, q is on the same of line l */
/ z2 c/ y) L! J2 A! c- K' s3 H　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ 5 b7 e5 r/ }( [
　　const vertex_t* p, 2 M2 r3 y: D! x9 y. E/ w
　　const vertex_t* q) , [) ]4 [9 s, f2 y* d' U1 v
　　{ 3 P7 d6 b! e, Q; Z4 r
　　double dx = l_end->x - l_start->x;
" h' Y0 H8 L* G, H  ~6 D　　double dy = l_end->y - l_start->y;
" _: v. l; |4 D: ~0 t　　double dx1= p->x - l_start->x; 0 g* k% _7 J0 l- P: G& w+ v$ M/ W
　　double dy1= p->y - l_start->y; 9 V$ \! _8 g2 ]: I$ a  v
　　double dx2= q->x - l_end->x; * J3 n! j3 l& @! E
　　double dy2= q->y - l_end->y; ( ]8 K. U* o4 {6 z$ H. S# N
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
! |6 ^7 z' V' n: f" Q$ P! }: v　　} . x3 G( R7 R. w& j* }* H5 e, ^! W
　　/* 2 line segments (s1, s2) are intersect? */ 5 q2 y# O& A- j8 f/ f" R
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, " b% _' Y. E( H( D+ j5 }( d
　　const vertex_t* s2_start, const vertex_t* s2_end) 6 ?5 d+ Q( `4 Y' r# f8 k
　　{ * _- T4 f. ]) n4 `- A. }4 H
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&   u# G1 S8 Z4 v8 a* K
　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; 9 j5 x. i- R0 i+ C  p8 f
　　} 9 B# l- V4 r7 J/ e& h2 X

- h( G7 ~( D; Y( l( D9 O& P. o
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
5 Z* t2 P8 P* v$ o4 T' e
( O) x8 G+ e7 q+ v) g以下是引用片段：& Q$ n0 C" r% c4 i
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ : Y. h) E. u# q5 a8 E6 t" \
　　const vertex_t* v)
* o/ t$ J& B/ @9 U　　{   L6 ^3 D" p: U% Y
　　int i, j, k1, k2, c;
0 Y/ R. W  z1 H/ _+ T$ y" s  m5 G　　rect_t rc; 5 f0 Z, L6 M5 f5 ?3 Y6 p5 [  b. X
　　vertex_t w; . H. M0 @% m' Y+ C
　　if (np < 3) & X0 S! c2 J$ d! m" m
　　return 0; ) e" g+ s9 w; r; K
　　vertices_get_extent(vl, np, &rc);
+ x0 A/ K& H  }- ?! h- Y8 I; U/ b　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
* v3 B+ Q0 Q( m: A" V　　return 0; ' p; P1 l' t' [2 b# I
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ 8 U+ ^7 M+ k1 V/ a
　　w.x = rc.max_x + DBL_EPSILON; % V6 V5 \  o" C* u  f# y
　　w.y = v->y; / ]  G0 ]$ s, b' ]" q0 Y
　　c = 0; /* Intersection points counter */
7 i1 J9 {' A; c  I7 t4 a7 t" m　　for(i=0; i
7 I/ j9 S  K5 `* [+ K% p3 h　　{
; q& Y; K. K  c% V9 m  e　　j = (i+1) % np; ) y, `& ^. {2 U3 n
　　if(is_intersect(vl+i, vl+j, v, &w))
0 r% G4 d1 L, `( N　　{
3 S8 [7 k) D: H' @1 d　　C++; $ i6 R7 R9 o8 X5 \; y- w3 R
　　} 5 Y7 r% Y! @0 a
　　else if(vl.y==w.y) * N6 m) |2 y& r" n; [
　　{
/ k* e+ z7 q0 F- o% w/ c' F  |　　k1 = (np+i-1)%np;
0 b, y7 A+ Q8 [6 w9 f　　while(k1!=i && vl[k1].y==w.y)
3 C/ q; p4 O/ F: A　　k1 = (np+k1-1)%np;
7 Y3 {6 K( K9 P, j　　k2 = (i+1)%np;
0 }6 ~/ n3 {9 o　　while(k2!=i && vl[k2].y==w.y) ! u5 @  r3 ?& m
　　k2 = (k2+1)%np;
- _, t* O) J- o9 `3 F　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) " h- j* D1 ^4 S; d% C
　　C++;
- Y8 _; e* z# Y2 h: s　　if(k2 <= i)
2 H: A4 Z( c$ N' J7 A5 Y　　break;
+ t; M" e* W# @　　i = k2;
7 ~0 q3 w3 ?. N, n% j　　} " P+ o+ u3 Q( }! q/ H$ z
　　} $ J$ C, F3 j/ N4 h2 H
　　return c%2; # w2 [. d; M  S, l! J3 C
　　}
1 H6 @7 }5 T0 v" @! K1 B# n. K& ~" I2 v4 _8 C

) M) w( `9 N) x: p3 X; w; z% u　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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