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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。& n: o. v1 H5 j( A& T# w- u
- j7 O+ j2 E3 z- b: m4 p. O4 W# Z
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。
( b- U: Z  e+ k3 [
　　首先定义点结构如下：
# x9 W# ~+ K5 I+ B- d2 O) J* g& U
以下是引用片段：
　　/* Vertex structure */
　　typedef struct $ o# b6 @+ q: F8 L( L  p
　　{ $ N$ e( U% G2 ]1 |  x
　　double x, y;
　　} vertex_t; 7 i7 G' q  l( h& v
% W( c0 D7 O9 ~; K

　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：' g. |6 `. Z6 p% a

以下是引用片段：, X' D; v9 I3 r* q6 b
　　/* Vertex list structure – polygon */ + \9 X) ]- _4 K+ t
　　typedef struct
　　{
　　int num_vertices; /* Number of vertices in list */ 1 n- O8 v7 O# \8 d9 N! [  E- t
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t; 0 F" G$ j9 t3 N( I( G( z9 [  w5 G
. n/ v. q! N' h2 W! c6 P( Z5 {
+ t0 z- e4 O) L. T  Z3 T
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：* ]& n% \2 h. N6 p! c, }

以下是引用片段：0 I0 U0 n4 k( ^" k) B* d$ s
　　/* bounding rectangle type */
　　typedef struct , k  H& Z3 d5 M0 y$ z2 f: z
　　{   p" ]- d( {& g# I7 S4 f/ [& X
　　double min_x, min_y, max_x, max_y;
　　} rect_t; ) m2 {( I, E& _1 q% I. a4 q
　　/* gets extent of vertices */ + W8 a8 L, I5 f
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ & o1 r) p& X+ ]4 n, G0 \" [
　　rect_t* rc /* out extent*/ )
　　{
　　int i;
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
　　}else{   f' F9 Z/ n9 L0 Q+ C7 D' R9 w
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
　　} ' @+ |) Y6 o0 x
　　for(i=1; i
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
/ f, L, k0 N( `7 Y: b3 ?  Z　　if(vl.y < rc->min_y) rc->min_y = vl.y; 0 e% d9 p4 c4 S' b0 D% i/ D: L! D
　　if(vl.x > rc->max_x) rc->max_x = vl.x; 2 v- F6 J3 V3 d/ \. O
　　if(vl.y > rc->max_y) rc->max_y = vl.y;
9 ^7 |9 f3 a$ Y2 K! p) \: B　　} % \- t: m. ^. q( s) V2 X
　　} + W/ O4 b& v% ^6 S
7 ?; N. ~4 c7 d

- C9 H8 K6 ~0 [  ?7 K7 l　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。  O& P0 @4 D0 l1 h  Z
/ }- w* u7 w7 R, J, |8 h& f' q- R
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
( ?6 P, ?  g1 E
2 [1 p- U# c( y8 D( O; V　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
9 k* P2 [2 ?/ L) A0 x" c& s4 M( D; w; c9 Y; m
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
& N% U! @) _2 i( y6 Q
( d, z+ \# n+ L% m7 g) H/ O- z以下是引用片段：+ T4 ?( A7 _% g8 j, S6 o+ Y& b: K9 e
　　/* p, q is on the same of line l */ # s; o: w  L. [3 s/ K
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ 8 P5 |! b  l* u
　　const vertex_t* p, . l. G, |8 P( ]  ?
　　const vertex_t* q) * }9 a4 H. d7 Z" G' m
　　{ , M; _- K; M7 b9 w
　　double dx = l_end->x - l_start->x; 7 D8 L4 s8 I* D5 `+ \% W
　　double dy = l_end->y - l_start->y; 9 \' N# {2 t' H8 A6 |9 k4 P' d) y
　　double dx1= p->x - l_start->x; 5 R; K2 t8 Q' h  r: {. O+ {% K
　　double dy1= p->y - l_start->y; 3 q& x. {7 N  ~+ g- S! N$ Q. K
　　double dx2= q->x - l_end->x;
9 _& T" k. ^5 x& M& r+ f2 a　　double dy2= q->y - l_end->y;
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
) W" l5 R! \1 u/ V' w# R  O　　} 2 j) m$ {) e" Q$ q* ^+ \) F
　　/* 2 line segments (s1, s2) are intersect? */ 1 k# ]- Y. _; b+ r8 a% z. `  A
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
8 N4 Z5 c; E6 H# a4 I! {　　const vertex_t* s2_start, const vertex_t* s2_end)
- Y$ o' C  l/ D" D/ k7 u　　{
) H4 ?- R* A9 c　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
- L4 w6 H% B5 H8 }- M. q! D　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
* _/ X) _" t7 c　　}
, N5 I) t. @8 J9 M+ }) L
' G2 A+ M8 H: }2 i; U  p
! h( ^. ?/ A  ]+ k$ @　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：/ m4 A2 s# Y0 I8 @4 ^
% w9 P1 {5 Y1 d' x% b
以下是引用片段：* ~1 y# |0 o0 [. q3 X, ?
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ # s; {" {, a8 X3 C7 K
　　const vertex_t* v)
6 x; e8 z4 p1 _8 D* q1 n　　{ 1 n! b5 J3 q' r
　　int i, j, k1, k2, c;   w; s, ~/ o; t# ]( h
　　rect_t rc;
# k8 \2 m" L% [; J( ~9 D9 p　　vertex_t w; ( ]% U7 ^7 k% O3 g# q" _2 ^
　　if (np < 3)
! J4 o6 g8 @% O3 l* ^　　return 0; 0 Z+ o8 |. m/ k" b% i
　　vertices_get_extent(vl, np, &rc); ; ~1 S( r0 P0 P
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
6 X- V' I& F' x  }+ Q& Z　　return 0;
9 A4 J  g* q7 K$ l7 Y　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
* b* D! H$ T2 S0 h　　w.x = rc.max_x + DBL_EPSILON; ( d3 N- k9 a6 ~# a% M0 P& g
　　w.y = v->y;
" r- @: T$ l: I8 i% R, ~$ ~4 F　　c = 0; /* Intersection points counter */ 4 b; I) g; w9 O4 @, F% J
　　for(i=0; i  0 c- ?0 O+ j3 n- ?6 z
　　{
  {1 e3 C0 s' r　　j = (i+1) % np;
9 b: d: m. E; A　　if(is_intersect(vl+i, vl+j, v, &w))
+ c0 p5 D* A; C) S: g/ R3 D　　{ ' I) H; `7 L+ M' S/ u
　　C++;
2 I2 c, ^" B4 \3 c0 V& k% k4 z　　} 1 q5 q5 @* o& E$ Z
　　else if(vl.y==w.y) - d2 L" _: R/ z' S0 ]
　　{ $ i( f" t  I' D/ K0 m; R9 k
　　k1 = (np+i-1)%np; 3 N' R0 N2 m1 X1 O
　　while(k1!=i && vl[k1].y==w.y)
3 f& {3 ]- H6 r$ R. r% G　　k1 = (np+k1-1)%np;
( r* N  s) y* o" `5 @. N/ Y6 @　　k2 = (i+1)%np; % R6 J# ^+ ~+ Z/ H2 A
　　while(k2!=i && vl[k2].y==w.y)
" E& T& |* F# W2 a8 D7 G4 S5 W　　k2 = (k2+1)%np;
7 p7 v7 `" c& |) T, K2 H　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)   }. ]1 Q; c/ \6 p7 C( @/ j
　　C++; 7 h* D; [: ^8 A+ ^. W  E
　　if(k2 <= i)
% \5 P" g2 m4 x　　break; 8 }% h- E$ k9 S9 \
　　i = k2; . B, M  l5 O8 f( n9 L5 ^
　　}
1 i+ c/ D3 W' j7 F( @0 l) Y8 d# r　　}
3 ~, |$ Y$ V$ T! m) P3 c3 i, A　　return c%2; / e! t5 i% A8 V% @
　　}
. b0 n' O( M& y' w% v9 j* j  J- F( W- C' ]5 u( C& p  c2 T' [

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

返回列表

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

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

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

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

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

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

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