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

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

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

　　首先定义点结构如下：

以下是引用片段：. A0 A8 P4 B/ y6 U
　　/* Vertex structure */
　　typedef struct " ]( `6 }) \' K+ P/ A
　　{ 1 L) W, F" n- m
　　double x, y;   {5 M" @2 f, C& i( o
　　} vertex_t;
5 _. _4 ?7 G5 N' U, n- c

　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：
2 D$ l, t& Q  G% J
以下是引用片段：
　　/* Vertex list structure – polygon */
　　typedef struct 4 P9 U2 X* ?% N: E
　　{ , _0 D( E: Q) W$ f- j& E
　　int num_vertices; /* Number of vertices in list */ ; Q. {! Y3 \+ v9 Z
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t;

% y. T0 L# x/ O6 P* }+ E( k
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：5 ^/ W3 v8 k% T) q

以下是引用片段：% S9 f  w7 n: k2 H! v
　　/* bounding rectangle type */ ( |' J' m: T4 ?6 l* G4 W
　　typedef struct
　　{
　　double min_x, min_y, max_x, max_y; : g, T4 J: L, ~0 w
　　} rect_t; , P0 q9 `6 {$ h1 Q4 y
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ )
　　{ * ^5 H$ N. _2 o0 N3 X: @' |
　　int i;
　　if (np > 0){ & ?8 i* s+ {+ e5 O  u
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
　　}else{ : H  V5 @  p/ ^9 W! n; W
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ , \1 k- H( Y/ k0 L9 i% F
　　}
　　for(i=1; i
　　{ & ^! y6 u# E: g) o+ K8 q% ?  u4 g
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
0 e1 X! f2 U3 A5 T) W1 H: ]/ J　　if(vl.y < rc->min_y) rc->min_y = vl.y; $ A- ?* u. U' T' V
　　if(vl.x > rc->max_x) rc->max_x = vl.x; " g5 `4 }) x% @9 E5 j& _9 j
　　if(vl.y > rc->max_y) rc->max_y = vl.y;
9 A* [4 Z. i8 c8 P　　}
) x2 C- O" ?4 y& Y- E　　}
3 u; S  u9 B( S
: Z; s7 j( l" o5 i# n+ R2 M9 b) a6 j. J4 Q6 y0 Y
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。8 J8 U" f. [- x* P( [
/ m$ g2 ~7 X4 B
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：& F+ w, w- ~1 \" `, r4 V  b: |
! z5 N2 {/ z; E+ z! O2 f) U4 p
　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
- }$ f* x9 M! Y* l& l2 X
$ t& I  s) L1 d; f" \  |　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;$ u7 ~! {, K# x$ ?1 F! J# s

) ~% i6 D0 @$ ]  P8 Z2 A2 N$ ~以下是引用片段：
2 E1 O8 @3 j2 T* {1 i' X: Z8 S# _　　/* p, q is on the same of line l */ * Q( R* R  M& y5 D0 f9 ~' H# t5 ?' ~
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ : e7 c7 Y7 N1 z) x7 g3 t
　　const vertex_t* p, ; g$ z- c4 G. g! Q1 a) Y, s
　　const vertex_t* q)
% R/ h: A& ]5 @　　{
! V: ^% k/ k6 J  Z2 c　　double dx = l_end->x - l_start->x; 4 c  |6 V- e7 E! u7 \9 k7 |  l
　　double dy = l_end->y - l_start->y; ; u* w4 S; c& i+ E0 i' H/ i
　　double dx1= p->x - l_start->x; 2 Z7 \" o( e6 @9 Y4 C7 c
　　double dy1= p->y - l_start->y;   n2 G4 X+ x+ b0 ?
　　double dx2= q->x - l_end->x; $ Z  [7 d5 c7 Z3 i* A" d
　　double dy2= q->y - l_end->y;
/ G* c! i8 G0 l" c5 t3 m9 z　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
  l( b/ v: [! v, v* L: q( F　　}
9 G- W7 a0 K6 B$ Y' d　　/* 2 line segments (s1, s2) are intersect? */
! e2 V! E- h1 _$ n# A　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
* r- ]( u% d5 s7 `9 `, L, j* B  V　　const vertex_t* s2_start, const vertex_t* s2_end)
$ D6 l3 @; Y% F　　{
6 z' ?: }/ r" Q5 ~& B　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
: _  q% p2 ~- N& v" n" a+ [/ W　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; / C- T: L' k% g5 E4 K! d
　　}
4 V- ~0 M! [+ |  _$ C! o" k5 B
* p7 z- K& b7 p+ F% B! D' m8 o3 c( v" _% f( v+ v
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
6 I0 O! q: u8 k0 T6 y9 l+ R! a  }5 [" T) k
以下是引用片段：
& v! d, I+ a$ u1 C# v& g1 c; X　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
  Q0 |# F1 z1 {1 B7 `0 N9 O1 x& Z! |　　const vertex_t* v)
+ ]1 b# S1 U3 ]8 t0 C　　{
$ u' V% j% Y3 P9 R6 z4 t3 R1 s　　int i, j, k1, k2, c;
1 T: B; a( q2 g% z5 c　　rect_t rc; 9 h1 B1 e& h' v% P  `+ Y& N+ |
　　vertex_t w;
8 S2 o! C+ c8 ^) T. S　　if (np < 3)
4 g2 U  ~2 v3 d2 x4 I　　return 0; 3 o; B% N. A% L" S1 [
　　vertices_get_extent(vl, np, &rc);
2 }7 J8 w6 p1 g+ g/ ]2 {　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) ! @' F3 @$ q2 e3 a. U
　　return 0;
: [- U  u# K! O0 W　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ # m: b8 I) z1 _  g6 K
　　w.x = rc.max_x + DBL_EPSILON; 3 K; x' ?+ \  M) n) @
　　w.y = v->y; 0 h& Z2 z7 C+ b9 A' A3 Q
　　c = 0; /* Intersection points counter */ 5 F: @, c$ n7 j2 G; H# T/ n+ m
　　for(i=0; i
" D; r  ~( B& {( \) k　　{ 4 s; B" o+ ~5 c9 d( z
　　j = (i+1) % np; 4 d( \! Q6 A7 }  {6 m( K0 n
　　if(is_intersect(vl+i, vl+j, v, &w)) 9 z9 h5 r! \- `' n
　　{
3 V" {# e, l) _; G2 u" N　　C++;
" `; E  j/ Q& p5 W　　} 0 {9 Y2 p/ X  j) e9 g5 J1 T! u  Y
　　else if(vl.y==w.y) " z5 F# u8 u* r! v( Y3 m/ Z
　　{
  X: h! W$ [* J- f' Q, Z) [; _  B　　k1 = (np+i-1)%np;
& j$ v) v4 m0 K1 ]7 P　　while(k1!=i && vl[k1].y==w.y)
" @7 R: X' Z" Z　　k1 = (np+k1-1)%np; 0 y- j8 j* j$ W3 t: s2 ]: R7 }
　　k2 = (i+1)%np;
5 i$ I) h7 G+ T, H7 c: ~& }　　while(k2!=i && vl[k2].y==w.y)
! o# Y, F- o0 G% i+ O1 J# p　　k2 = (k2+1)%np;
2 \; |* R$ s5 \+ P/ W7 I　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) 6 [; `. {# o( R: u' [
　　C++; % b7 g! e. w0 _# I6 j! d. u% u4 j
　　if(k2 <= i) 4 e4 \0 _! E7 T" K
　　break;
# p. O4 z' Y  w  O　　i = k2; . l. L& B$ a# f0 i: n& b
　　}
! h. ~, O# K( [6 w' D! ^8 i7 i　　}
! A' n" K2 S! H, ~* f　　return c%2;
4 q% U: e% P, c, P　　}
  N2 l, v" X$ e  p
5 C& q: `# N5 H0 j& _' P
+ @+ C& P% q7 g9 f$ [$ w6 u　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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