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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。
" j* M8 X/ u  S9 z
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。
3 N( C7 d3 O$ X" g
　　首先定义点结构如下：( T! p1 [3 s1 k6 @: {
8 w9 g& r3 |$ r' S: A! [% ~( F; M9 W
以下是引用片段：* W6 o* c2 `5 ^' `! D
　　/* Vertex structure */ / r- m0 X; O+ m) t7 O* Z3 Y
　　typedef struct
　　{ # U6 Q& L% @! W3 D
　　double x, y; - v4 V. F1 r* d( S: y9 H( t* j' U8 p2 f
　　} vertex_t;
- E( ^( o2 d* L2 R) ]1 q  n) q

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

以下是引用片段：1 ?" p6 ~& e7 I6 b6 d
　　/* Vertex list structure – polygon */
　　typedef struct ! E$ h" k7 V/ l' J
　　{ : H2 [/ k+ C4 ]/ G
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */ ( B; |& I/ K( w" f' f
　　} vertexlist_t; 9 w. z  [$ Y. V2 U* T: S# a8 V
7 i- _" _3 |  i( F+ v) t; a

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

以下是引用片段：
　　/* bounding rectangle type */
　　typedef struct - N7 N' d" P: J: G
　　{
　　double min_x, min_y, max_x, max_y; ( @( P9 E+ Q  g3 l, s
　　} rect_t; ' W( J7 [) b% a1 F
　　/* gets extent of vertices */ 4 m6 m  Q& A3 H3 s( e: k5 V0 f8 f
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */   h! B0 d: l! O" ^" ^
　　rect_t* rc /* out extent*/ ) 6 y& A& Y% }% n' e, K; s
　　{ 6 g9 G" x5 h% H
　　int i;
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; , u$ R4 K" l3 w5 }5 v) ~" n
　　}else{
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
　　} ( L8 F' \5 o$ `0 D. a9 ~) {9 @# j/ ]3 q
　　for(i=1; i
　　{ ' y6 v8 D2 p5 i3 Y* ~
　　if(vl.x < rc->min_x) rc->min_x = vl.x; 4 S* H5 L  Q' j7 X6 e6 b6 H' o  \
　　if(vl.y < rc->min_y) rc->min_y = vl.y; , X0 P8 A1 P5 j
　　if(vl.x > rc->max_x) rc->max_x = vl.x; & l3 u, u# m8 t0 p4 O7 p
　　if(vl.y > rc->max_y) rc->max_y = vl.y;
: a9 u/ ~& _" F; [; y( X: }% A　　}
) T* f' X8 D& r5 L& X　　}
  m7 a3 _0 y! P- L" z
- U, V7 G+ {% k0 f6 L% L. C) l/ [8 e8 r  j
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。' P3 q) Z2 B1 K; L' l
7 M- d% c- U: S) ?+ T
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：) _: [9 O2 c! k5 F% N
0 I' k2 m8 |+ {  I
　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;( g, ~1 g1 T: k  t

5 _( I0 k/ X2 X( D- Z' C! a- F　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
* H/ s, u9 b8 D  ~& Q8 X8 {8 n1 h8 M2 D6 {& n9 Y
以下是引用片段：3 f$ H! a+ @! W, y- B
　　/* p, q is on the same of line l */
" |% w* @$ P1 I) ^& [　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
% [) ]- y  V5 v5 i6 l4 q　　const vertex_t* p, 9 o+ d& \0 f! o! N; l3 M# \% a
　　const vertex_t* q) % d. D; N! @& r3 o# }
　　{ / B" w4 q4 E& i2 [) r4 S6 z
　　double dx = l_end->x - l_start->x;
) e; ^0 K' G" H3 g# N　　double dy = l_end->y - l_start->y;
( A; @9 }; _) ]: ?8 E* N　　double dx1= p->x - l_start->x; 8 V( q8 P1 }/ a
　　double dy1= p->y - l_start->y;
! w7 R3 T3 y- h! @# R　　double dx2= q->x - l_end->x;
5 n6 p! G. q' E6 f; S1 B6 V2 c　　double dy2= q->y - l_end->y;
6 _5 g" O7 S1 L' O" C8 [- w  ]　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
  P" a% J7 r5 R5 R+ i7 u　　}
+ p/ o) n; h3 z. z6 u( U　　/* 2 line segments (s1, s2) are intersect? */
6 X' [; v8 [/ J4 g　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, : g, }  K  S/ p1 S9 W% l
　　const vertex_t* s2_start, const vertex_t* s2_end)
4 H9 i! [" Y; N" f. A　　{
7 h/ |" K3 _, x# r, w( r3 h　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && ! B* Z+ T7 r  \. H  l4 S
　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
& a' y4 }7 o  t) C! U/ F　　} : b+ K$ y5 D% V+ o. h' m

2 y/ M( O. @  Y1 n. [+ I( o. E/ K
6 d; b: v' S6 V　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：$ }9 a/ b3 m8 A- ~: x9 L6 [1 |
8 s& |; `$ b! R3 l+ y% _; o4 ~4 E+ v
以下是引用片段：+ ~7 z+ c2 c% z% e
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ ; h; S3 y9 I% K
　　const vertex_t* v) 6 H/ T5 M9 i/ r4 }
　　{ 1 Z: X7 W6 b* l6 D$ t0 J
　　int i, j, k1, k2, c; 8 @6 c- {+ r5 D, _9 |
　　rect_t rc;
, O9 A' I& c5 {0 D9 B　　vertex_t w; 5 T! F$ ^' w5 X, \) _
　　if (np < 3)
! d2 j) Q$ X/ z) Z9 u" V) e4 C　　return 0;
+ g( O+ u* W, n1 A6 I　　vertices_get_extent(vl, np, &rc);
; g7 ]: D( a5 a6 X6 a　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
  R: v+ v9 R1 s8 p$ @! D" O, \' Q　　return 0;
3 [9 M+ E% f$ Z1 C0 A　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
' i7 Z0 D: Y+ ~. C, ~( J; b　　w.x = rc.max_x + DBL_EPSILON; 6 O" V  }' R  X) Y4 T8 p+ H6 J
　　w.y = v->y; : U7 C8 Y; R' v% e- x+ h
　　c = 0; /* Intersection points counter */ " p8 x" e" b8 h% z
　　for(i=0; i  % m3 n# i$ _7 E4 r
　　{
3 x% l' @7 \7 J' i, H" _　　j = (i+1) % np; 8 O- G9 N0 v# a3 v
　　if(is_intersect(vl+i, vl+j, v, &w)) ! b4 G1 g8 e) X2 Z2 `% s$ Z
　　{ ( a% a+ q3 o  E% E1 L6 r
　　C++; 6 ^7 L+ r$ d, x- ^2 h" T
　　} ; d) I: O8 J' A* I! H0 }
　　else if(vl.y==w.y)
3 b  Q6 \- o- A6 X8 ~, e　　{ / ]3 Z8 U; T4 I7 F) D3 x
　　k1 = (np+i-1)%np;
' W0 L6 n% t2 |　　while(k1!=i && vl[k1].y==w.y)
0 a7 b! y* O0 _　　k1 = (np+k1-1)%np;
* E* U7 `8 ?% |　　k2 = (i+1)%np; 6 h2 L, c( H' i# Q9 ^% ?/ k; r
　　while(k2!=i && vl[k2].y==w.y) $ ]) ]" }6 s, u. f! Y! d
　　k2 = (k2+1)%np; ) Z5 P2 n. f$ u, W
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
* g8 e" u4 q. K4 k$ s　　C++;
1 U7 ]4 ?- R0 R, E; ~. X9 ~　　if(k2 <= i) . |! q2 U9 c: M  n6 Z: L, c
　　break; " r) |$ g. D0 L8 Y8 M! T. A
　　i = k2; 4 E+ }$ W1 D  ~; `  d. P
　　} ( D; H( A  y# M) W' D
　　}
8 d+ p8 K; Y" O　　return c%2;
3 U; e0 R! ?0 S# Z8 u　　}
* O7 y* j0 J8 \6 n& O* X9 Q8 j% M9 |8 ^! H' w! ~* h( R) {

) W7 u2 Q: \8 j( v& c　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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