返回列表 发帖

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

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

- n8 C* ?% U/ ^9 c/ u6 I. t  这是个C语言的小算法的实现程序,本来不想放到这里。可是,当我自己要实现这样一个算法的时候,想在网上找个现成的,考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心,所以,决定重新写一个,并把它放到这里,以飨读者。也增加一下BLOG的点击量。
! n0 v5 M, ]; S( j$ K+ s4 }/ `/ e5 W7 o1 A& L
  首先定义点结构如下:- J1 y: t( L; q  v; v9 }( O
0 W5 q) k7 ~8 v4 n: |
以下是引用片段:
8 o* X  k" d1 _; V4 w  /* Vertex structure */
4 n% w7 J8 N- `0 y* p  typedef struct
/ U, \9 _; P. P  {   l* [0 P# ?$ C* A( y
  double x, y;
4 q; ]0 z; r* p/ M9 ~  } vertex_t; 3 v1 j5 B3 M  c& U% x. s
4 b5 H% {, i! t! M  M
" d  |+ }  f6 T! y4 Y" P
  本算法里所指的多边形,是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的,包括多条边在一条绝对直线上。因此,定义多边形结构如下:
& H( u' c  Y1 J. O+ u- a
) C; O# G/ V1 Q以下是引用片段:; Q  ~2 ~; w0 S1 A2 I
  /* Vertex list structure – polygon */ . p9 B2 ]3 X8 {- H2 E
  typedef struct
  \& I/ u0 t6 i- @$ b0 J  {
& x& i! h2 d5 ?( f  int num_vertices; /* Number of vertices in list */ / Z4 U% d  S) ^* J
  vertex_t *vertex; /* Vertex array pointer */ # L4 e. p- f, ^
  } vertexlist_t; % i  Y/ g6 i# l* {% F) m1 I

# r4 ^0 X' ?/ e9 c, F; }
2 }; N2 F; W5 z% z  f: g- o) x  为加快判别速度,首先计算多边形的外包矩形(rect_t),判断点是否落在外包矩形内,只有满足落在外包矩形内的条件的点,才进入下一步的计算。为此,引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent,代码如下:
9 u3 @9 k0 T; N6 N) t3 r2 e" Y1 m2 e
以下是引用片段:
6 e4 C: m- u  J& x8 T+ \  /* bounding rectangle type */ 5 _9 O" m* Z* R" m8 m$ K
  typedef struct
! f+ S# V! ~9 @$ `: g  { ; k/ _& b) J6 Q; D
  double min_x, min_y, max_x, max_y;
$ q7 R) ]+ g. F. W# T  } rect_t;
" ~* ^  L7 o, b+ X% R# s  /* gets extent of vertices */
% B; Q( ?( V) R. `0 X: \# r6 Q  void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
: u/ X/ \8 y& Q$ v! _/ k  rect_t* rc /* out extent*/ ) - j7 y4 i2 x- C  g
  {
, g4 I: O$ J! Y& D# O  int i; % x9 Q6 R1 `" C8 N% @/ ~1 M( B
  if (np > 0){ 1 ~) Z" B  c* ?: b! V' a
  rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; + j; D/ o: `! j. g( a' g
  }else{ 0 j2 Z3 G6 j" i4 M
  rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ ; I" A: U/ o$ o" X7 R6 c( @
  } , t$ W  c1 W0 m; v
  for(i=1; i  5 G) L5 ^& b  a- ~
  {
" h' ]6 T5 V" I0 [/ ?  if(vl.x < rc->min_x) rc->min_x = vl.x;
& X; ^" I+ i" Y' g. z7 Q  if(vl.y < rc->min_y) rc->min_y = vl.y; $ c+ @4 y) m. n' o' J/ o
  if(vl.x > rc->max_x) rc->max_x = vl.x;
$ B/ X& X0 X3 b% F  if(vl.y > rc->max_y) rc->max_y = vl.y; 0 @! [2 F1 A- B
  } 2 I8 C1 ^1 u, l% H3 x
  }
9 U3 D* G1 L6 l+ c3 h* k/ _; C" `3 T8 G6 _

) T9 v! O+ M6 v. Q  当点满足落在多边形外包矩形内的条件,要进一步判断点(v)是否在多边形(vl:np)内。本程序采用射线法,由待测试点(v)水平引出一条射线B(v,w),计算B与vl边线的交点数目,记为c,根据奇内偶外原则(c为奇数说明v在vl内,否则v不在vl内)判断点是否在多边形内。1 S5 K/ {0 t4 R# d( C
( J6 b; t' y$ m  ]7 q
  具体原理就不多说。为计算线段间是否存在交点,引入下面的函数:
* n" @. M: B' T, {$ ^# J
# T' F( j5 o- K/ t' E5 i4 h3 F  (1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start,l_end)的同侧;
# I  ?  r5 m0 A2 ]& o
' S1 f  t+ Q$ u* i  (2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
. |& G6 X( Y3 B8 i9 R: Z0 w5 J2 n4 O
以下是引用片段:) l( k9 |9 E# E1 z- Q& c
  /* p, q is on the same of line l */ + n6 ^3 I* ?9 s" A+ x
  static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
+ \# }. z' ^/ p/ b  const vertex_t* p,   \% Z: _$ [- B
  const vertex_t* q)
4 v! k& ~: b; A2 K6 ~' w, e" H7 V  { : j* A4 Q% z9 R2 v; |8 [
  double dx = l_end->x - l_start->x;
6 h, `( ~) y  g+ g7 M  double dy = l_end->y - l_start->y;
  b) m- t4 c) Z  double dx1= p->x - l_start->x;
9 D" y( g. s) T  double dy1= p->y - l_start->y; 7 i7 V" P2 I4 J5 T8 o
  double dx2= q->x - l_end->x;
$ m9 o. i) `" ^$ n0 r. t  double dy2= q->y - l_end->y;
" l$ A2 S: p4 x2 V) j  return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
) T7 E" P; E$ t: a4 R8 Q# F  }
  h( N8 B1 T: C. C. w  /* 2 line segments (s1, s2) are intersect? */ 2 Y8 k7 Z  {9 l4 S  v2 Z
  static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, 4 G2 z+ `9 ]( s: z$ I2 {
  const vertex_t* s2_start, const vertex_t* s2_end)
5 ~2 \" \: g6 t5 G0 H3 W  { + G* k: y6 G  |: {) c/ B; F  Z
  return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && 7 x- b0 p6 W# k' i
  is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
# \7 b$ _% U- X+ ]5 v# W  v* a  }
: D( A- B) U; n0 c
) e4 r6 N" \6 l- y; t2 M  C/ X  q$ x; q& g, v9 b4 j: w
  下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl:np)内的程序:
% J& s8 s3 w) x& P( ~4 w4 H1 V6 M' K8 d
以下是引用片段:& e/ ?9 _3 c3 q1 M
  int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
! n0 _$ m# r1 u9 D  const vertex_t* v)
. r- e) v* p; r. z5 k2 J9 `  {
! k1 x; G. o, M7 O7 m  c1 Z$ V  int i, j, k1, k2, c;
- x- s: ]) c" n( j" W4 C  rect_t rc;
" R6 u+ W% ?+ b( ]  vertex_t w;
/ N& c- I# t1 Y6 G; e& o2 N( G  if (np < 3)
2 N3 y) E' W5 w  y1 |1 y# P! \4 w  return 0;
0 Q+ j/ B; x6 v2 P: E& w: B+ r- q  vertices_get_extent(vl, np, &rc);
' i+ w+ J; w5 I* K& R2 v  if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) & l( M6 h, M9 [2 Y; f  S1 }
  return 0;
1 j* x. B) j) H  /* Set a horizontal beam l(*v, w) from v to the ultra right */
, B. I% X: A! j6 v! n  w.x = rc.max_x + DBL_EPSILON; ' P( Z# e) I3 e& a
  w.y = v->y; 9 V, w. ]5 n5 o2 K
  c = 0; /* Intersection points counter */ / N. p8 p( P8 @: B( `1 H( w
  for(i=0; i  # R9 V# j$ g  j* L0 J! O: t
  { 9 S( f& g& @4 ~3 V
  j = (i+1) % np; - M/ q$ U4 u4 M7 n
  if(is_intersect(vl+i, vl+j, v, &w)) 3 m. s$ H, w5 B) @
  { 2 v/ b6 `8 z7 c* `2 b# o7 E* B+ }
  C++; $ L( R: h- j) V( _3 f( {  \
  }
9 ?3 h2 t) L+ ?. M  else if(vl.y==w.y) 8 v+ Y0 i4 I. G/ Y
  {
7 ?# L8 p) U6 l* I  k1 = (np+i-1)%np;
. v$ P% n( p) b! i( ]  while(k1!=i && vl[k1].y==w.y)
0 U, b5 B( R: A. h: C; `  k1 = (np+k1-1)%np; 8 I" A* {& a( h  f2 r6 |( C
  k2 = (i+1)%np; ' y% i0 y( t8 W5 m
  while(k2!=i && vl[k2].y==w.y) $ M; {" S# r# ?- S" m. W( K1 u& }
  k2 = (k2+1)%np;
& R2 [2 E* ?' C! G# f5 B! ~7 ?/ `  if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
+ t; D+ a4 H1 q! p- m  C++; & [0 l, ]$ ]0 f6 h( P
  if(k2 <= i)
5 N& z( O! {6 v& C3 ], _  break;
8 V: R( n$ Z& m5 E$ Y* m1 P  i = k2;
- p) ~2 o6 H5 B. y2 t" N# X  } 0 d( Y4 a1 _( S: \1 k8 V
  } ; p0 o2 _, y& T; |
  return c%2;
% @+ }6 s1 s  b! k  }
# U/ l; |" Y# H2 Q! v  U) B
$ O: C% B/ i: d, l0 S
0 R$ G% V. [0 `! M  本想配些插图说明问题,但是,CSDN的文章里放图片我还没用过。以后再试吧!实践证明,本程序算法的适应性极强。但是,对于点正好落在多边形边上的极端情形,有可能得出2种不同的结果。

返回列表
【捌玖网络】已经运行: