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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。+ d% ?1 P# }6 O. i" @, o
: E' t- O8 S3 b6 A& i2 a" |
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。! C" {5 v$ {1 `# o  W  G( z# k' K
4 c) g2 r: j# _4 e
　　首先定义点结构如下：
0 `  V# e6 C$ D/ [3 P$ l. I
以下是引用片段：
　　/* Vertex structure */ 3 u" }) N3 G& H; r9 m7 y
　　typedef struct
　　{
　　double x, y;
　　} vertex_t;
2 _0 m4 E; ~5 Q" M& \* Z

　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：6 \5 w' D7 l' i2 i8 F+ O2 R8 n

以下是引用片段：
　　/* Vertex list structure – polygon */
　　typedef struct 8 I4 P2 V- _. C# ?; \) {) K  v
　　{
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */ ) e9 `+ z/ y# H! Q( B" B! `
　　} vertexlist_t;
) Q; {7 t3 z. ?) ^

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

以下是引用片段：2 i+ w* I  N0 x! z
　　/* bounding rectangle type */
　　typedef struct
　　{ ! v- L2 V& r  x6 |  y
　　double min_x, min_y, max_x, max_y;
　　} rect_t; 0 ^0 `6 T3 |* X7 s. X: R1 T  N
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ )   ?$ F, W2 \: ?3 r! ?+ o: X8 O
　　{ 5 j$ \2 v5 E5 V  f2 I3 R9 e0 \) ]
　　int i; % g3 v$ [# A% {$ B  S
　　if (np > 0){ 6 H, a. @6 u$ I2 p
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
　　}else{
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
　　} 4 E' x  m) O- @
　　for(i=1; i
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x; 9 R  i. v, R# N7 E& F, H4 l
　　if(vl.y < rc->min_y) rc->min_y = vl.y;
& c1 C6 m4 I. m- L4 P$ R% s9 A　　if(vl.x > rc->max_x) rc->max_x = vl.x;
! V$ R  _( l1 Q0 I　　if(vl.y > rc->max_y) rc->max_y = vl.y; / f$ G1 i8 o0 H) I
　　}
! `- Q( A% ?: `　　}
, s/ R( Y8 \# a- b7 ]# \$ y
8 }$ c3 `$ L5 C' H( S  r' O7 u7 j
$ ^6 }7 M  g' j0 ^% d　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
9 |+ x6 v' v! m2 _/ U
7 ^) i+ S1 Q: @　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
9 i; m9 {7 S& x' T3 l) ~& K( B3 o; I' v9 m
　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;# ^% N0 x. ~' P4 c! F
$ ~! B7 ~1 M2 Q) ^, B( U! a, {
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
3 S+ W% D! @/ [- ^) R) e
( }& C" u% r& i( Z6 m& X以下是引用片段：
# g+ u9 W. U  \+ P　　/* p, q is on the same of line l */
* N- J  ]2 L& a$ {& x3 v　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ ) m$ z; ?4 y. C+ b
　　const vertex_t* p, , r2 B  P7 |8 W
　　const vertex_t* q) : @7 I; }3 `6 e
　　{
6 o. V# E0 v1 r  H& [' I# C. J　　double dx = l_end->x - l_start->x;
7 x( ^& r, B, q; [　　double dy = l_end->y - l_start->y; ; J! r3 K, n0 Q( h2 K, c( L3 r  k
　　double dx1= p->x - l_start->x;
9 F7 f  V3 E' h# ~! a8 y" Y- e  }　　double dy1= p->y - l_start->y;
/ f4 g  n( I  O; q　　double dx2= q->x - l_end->x;
+ f% }2 u/ x3 V! R/ s; u　　double dy2= q->y - l_end->y;
" a! |* i3 s/ \% c; n　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
; r9 k% _* K; y3 m' J　　} , J' V, W% B8 E4 P6 R
　　/* 2 line segments (s1, s2) are intersect? */
( S9 `+ {0 h) i0 A2 l　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, 8 D8 }1 S: v) @- k
　　const vertex_t* s2_start, const vertex_t* s2_end)
' H3 v; F' K% Q% f　　{
' f, C8 g) |4 ]　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && ! V! s2 I3 B, `, V6 s8 _
　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; ( }+ r0 |  P" a4 {( C- _
　　}
4 c( r3 d2 I4 ]9 }
$ Y+ n. T/ g3 d
) M, k' i5 z. g( Z# O) M　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：9 k3 N0 V0 o  k3 W  m0 m+ d" B- N8 D
1 |0 O0 o9 v5 a
以下是引用片段：) V+ b& Y! Z' L' }/ f* h! _7 M
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
+ ?: a9 P5 s% P0 H8 W　　const vertex_t* v)
" H8 y6 {2 f- P; l% e9 G0 h　　{
( @0 e7 V3 T; D8 ?4 l　　int i, j, k1, k2, c; 9 ]9 H: j- u6 ]; ?+ k
　　rect_t rc; 8 \5 e: ]2 Z4 [6 _0 E
　　vertex_t w; & e/ B* _$ |* D2 I% u
　　if (np < 3)
: d" m8 a& C9 `5 z2 I: B1 {4 r2 ~　　return 0; # n6 N, Z" P1 i5 o$ O* D
　　vertices_get_extent(vl, np, &rc); . T3 C  O+ V: Y: Q" V0 \
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) 2 o4 g9 n' M9 t( a) B1 c
　　return 0;   V, g" ^+ u. K
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ . q* [0 n  S0 V0 I2 F4 N  K$ ^5 A2 M
　　w.x = rc.max_x + DBL_EPSILON; 9 [! K3 D& b2 d, |  d
　　w.y = v->y;
2 F; v, e3 a* P' d  A+ M$ z. U　　c = 0; /* Intersection points counter */ ; e) W' Q  ^9 k0 j
　　for(i=0; i  % a% ^- I5 S# x7 d7 K
　　{
+ c9 y" H  W! M' |* H2 M　　j = (i+1) % np;
% Q% F4 A* B$ T1 [# S　　if(is_intersect(vl+i, vl+j, v, &w)) & O4 ^8 M1 M- F% ~2 Y& Q, Z0 V" ]5 V
　　{
/ }5 D& N$ L& b　　C++;
6 \8 w0 R" A0 G7 N% t　　} , C/ ^7 B3 a" ?, F4 q
　　else if(vl.y==w.y) . ?. S6 L) Z5 U; ], V  o
　　{ ' o- ?& m0 m; f* z9 M0 }
　　k1 = (np+i-1)%np;
: c0 c4 V, B7 _& @　　while(k1!=i && vl[k1].y==w.y)
  j  L2 B/ n) i" t5 x# }　　k1 = (np+k1-1)%np;
6 M. M+ a3 @: o　　k2 = (i+1)%np; 0 l9 S$ S6 T: U, _$ U. d" V! v6 I
　　while(k2!=i && vl[k2].y==w.y)
# y  C% _& C$ [' I( \　　k2 = (k2+1)%np;
& E# {( T0 }+ g$ B　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) 2 r* |, E- m% l2 {/ F
　　C++;
' z5 I9 @+ v+ p" L9 z9 N; O% G" R; i　　if(k2 <= i)
" Q) f( X+ n: A* [! J  i　　break;
0 |8 d) J- k+ N5 z$ p　　i = k2; ! r4 e6 c# }- A9 g+ w
　　} 3 Y% r2 [* Y) {+ e" T) ^7 R* Z
　　}
" L3 d# r8 [# d- C  @, @1 E　　return c%2; : N; B% Z3 N, Z; `  M1 `
　　} 3 ]2 F% `/ T+ Q

6 @9 d8 u, X% r1 r6 _  r5 [9 J, d! [) E, x  L! z( {
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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