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

zw2004

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。4 q3 F+ _% P5 E4 }( p$ |. @: M* X

8 W7 h6 Y& Z# k* ]0 c/ H3 c　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。
- n7 Q+ a  h) r* V/ l. K) E3 p! x, x7 M* Y3 ~0 \+ ?+ C3 m; [& H
　　首先定义点结构如下：
, j3 H* E3 a- l: F0 g# b) K" p$ o- M- _
以下是引用片段：6 p6 U$ e# r( W, v. Z5 ^& n
　　/* Vertex structure */
+ X( n9 G7 d: v　　typedef struct ( b+ G3 }, H$ f* `1 ^; V
　　{
  x- S/ L! m. Q% p) K7 n　　double x, y; + e/ ^, l& r) K% R2 `! j4 A
　　} vertex_t; 3 K8 U) M# S& P- E- G- E* y# V
, b' E2 v' T7 K+ ?0 \# `& p

- m3 H$ ~# }8 {. V$ L　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：. S9 Y$ }% U( S7 z4 O
+ N4 Y- \" ~; F: \6 T
以下是引用片段：, E) ]2 V) j$ T
　　/* Vertex list structure – polygon */
" k9 Z. _& X7 ^7 l  @　　typedef struct 0 H  X8 L- @3 L
　　{ 8 n3 p+ F6 s8 u9 \
　　int num_vertices; /* Number of vertices in list */ 2 e( r3 k& c4 R! e
　　vertex_t *vertex; /* Vertex array pointer */ 4 c, p3 E* y3 Q
　　} vertexlist_t;
, y$ ~5 t) R& M: V: E, T. ]9 f' ?6 S4 t. R3 A
0 q$ s; i+ b5 X3 f, \3 W+ B
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：0 [+ O# N) K( U6 l

6 {% ~, U* M0 R- p1 A$ t, n( a$ c, D以下是引用片段：7 l. ^  h/ b" O6 F0 x5 q
　　/* bounding rectangle type */ & C' q3 D6 j5 V! g  z" J
　　typedef struct ( l$ ~) {' Y( e
　　{
9 U" G( _4 q+ x# m; ]5 k　　double min_x, min_y, max_x, max_y;   g' u; X* ^3 q6 A% _
　　} rect_t;
: m+ y. t8 d6 }3 z6 _! m　　/* gets extent of vertices */ * t' W1 n3 Q6 [4 [4 q; r
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
0 i+ W7 x8 X$ q! d$ m* c　　rect_t* rc /* out extent*/ )   n8 I5 ^' G0 |: @6 b
　　{ 5 |( w5 ?$ P4 e4 q1 h* K: F" g
　　int i;
% @/ J/ h% w! G% x& |+ c" @　　if (np > 0){
6 q! ^6 S5 \6 \( n1 N, j; i! |- F　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; 3 s" U) W3 K' i! t3 Q
　　}else{
- s, g# ~$ c' h5 |9 q" b　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
/ y# p. {4 Z* X5 m" J* v+ T　　}
7 ?- S4 I7 B0 S6 ?$ B" |- v2 m) F9 C. z　　for(i=1; i  
, z7 `6 \9 N* D' {; y1 B$ g　　{
: _# S9 X# r3 n& ?" v6 L4 `　　if(vl.x < rc->min_x) rc->min_x = vl.x;
( x& ?% O6 [1 L4 V' y2 y　　if(vl.y < rc->min_y) rc->min_y = vl.y; % b+ I- |/ n2 [0 m8 y8 W' E9 U
　　if(vl.x > rc->max_x) rc->max_x = vl.x; 7 r/ Y6 j, }/ ]0 S
　　if(vl.y > rc->max_y) rc->max_y = vl.y;
/ j+ |' r6 f! y3 h% r　　}
* S, S0 J8 I. A( T7 _! s- A　　}
; y& q/ Z: m6 @4 o7 y/ u9 @+ e- s4 [: e
5 d. v4 I9 [+ S! _
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。. V$ C' R& W* u' p3 H/ t

- A3 r  `9 k$ \/ B　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
4 l" q  @( K$ ]
1 Y5 _9 D! T, g+ k  a3 O8 W　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;0 [; y% s; M4 M" @* t5 |6 H
4 z' _. Z  @; v4 [0 j
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
' Y( l4 {3 w5 r1 C+ @/ k& y( W, h0 g  }% n. u5 {: I
以下是引用片段：
1 k6 j1 F8 U  p  }+ L　　/* p, q is on the same of line l */
2 ?1 B8 V: p3 D- m7 K7 Q　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ 8 u/ p; S2 u. w6 S
　　const vertex_t* p, 0 T! z6 S0 K2 s1 Z
　　const vertex_t* q) $ b5 [4 _% c& |: I8 g2 w
　　{
. v3 \2 V+ d9 `, t/ d/ }! P% t1 J　　double dx = l_end->x - l_start->x; : |1 I$ M1 ^% O
　　double dy = l_end->y - l_start->y;
1 m8 I/ J2 i2 D8 A$ Y$ ]　　double dx1= p->x - l_start->x;
2 }8 ]/ v' S5 g　　double dy1= p->y - l_start->y;
6 l" i, ~# h. u6 M% h　　double dx2= q->x - l_end->x;
! r' a. ?+ {1 S) s　　double dy2= q->y - l_end->y; + Y8 B- s9 E' a+ C* ~5 q
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
7 {7 ?6 U* a' c$ ^: m$ u　　} 7 Z+ I; f4 Y$ e5 p, \( S* M/ H
　　/* 2 line segments (s1, s2) are intersect? */ + i! A6 P% I4 B+ V$ y
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, , X" v6 s& k) K5 d9 s
　　const vertex_t* s2_start, const vertex_t* s2_end) ' |; \6 k! o3 T) U' y5 y
　　{
; p; w! Y  H& t1 m4 A　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && 0 q. [1 }+ x1 N) p; J; c
　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; 3 d( G+ u) Y* o% l4 F% Y: t! E
　　} % z0 ^# b4 D! b1 Z+ k6 \/ ?1 `- }

% d) K3 t; n) j  v3 G3 y' y2 v( @5 e  X  g% V5 k. s
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
" `: [  l. \9 B2 Y; I9 k* `/ L# j% r# P& l6 c- r! i, U
以下是引用片段：7 l: u+ m% F% Z  ]- n- p, Y- c
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
, \0 d0 G3 y/ m. b　　const vertex_t* v) 6 i# h( X6 z! k% z& E% I
　　{
; d; `1 n; Q6 |) x& M4 o　　int i, j, k1, k2, c;
# F4 E4 U, B; p5 k; Y　　rect_t rc;
/ @2 e0 [" d$ W1 ]% ?7 d) n　　vertex_t w;
& S* D" I3 M1 Q' o7 N　　if (np < 3) - M- J. v& P- V) e3 I  U* W; ~
　　return 0; + K- R$ }0 A& s$ }4 Y* p+ L
　　vertices_get_extent(vl, np, &rc); % ?! t( K2 k+ T+ \
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) $ |2 a2 p8 z* [  C: O7 K5 O1 h3 j+ ]# o
　　return 0;
3 s2 x0 \4 E* I　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ 3 d* y5 L- Z5 N* {( a4 a
　　w.x = rc.max_x + DBL_EPSILON; 2 N5 m/ y' q2 @4 a! k0 R
　　w.y = v->y;
; I; |" y  J5 [9 ]2 ?2 H　　c = 0; /* Intersection points counter */ ' T; z" O/ r5 z. q) \; R0 W
　　for(i=0; i  9 H+ L) a) a* |4 Q% }/ o5 o
　　{
* [* E' D1 p  q1 G$ T1 x5 v　　j = (i+1) % np; 8 P  t+ Q: e2 ~
　　if(is_intersect(vl+i, vl+j, v, &w))
; z+ }; ^5 W! [* j/ r: ]　　{ : b0 g+ W. B, p2 l6 K
　　C++; , q* U+ _- k5 g" _5 Q  h( M6 j+ ]7 w# F
　　}
4 u9 E7 a5 W5 w9 j% f　　else if(vl.y==w.y)
9 [4 p5 B( o  W" B' v+ t8 q7 D' ^　　{
4 b: z% d5 e) G, r0 {5 q　　k1 = (np+i-1)%np; 4 v+ W" ~7 s" L4 K- S
　　while(k1!=i && vl[k1].y==w.y) , }! s" c# |/ q  `7 A" T$ O
　　k1 = (np+k1-1)%np;
' |$ \: {) Z+ G& o: D! r" }: r* f　　k2 = (i+1)%np;
3 c5 ?! x* F# O8 B" e　　while(k2!=i && vl[k2].y==w.y) # h) H: V; e7 J: J
　　k2 = (k2+1)%np; 8 C5 }% |$ _  H9 h. d
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
4 p8 K* `* g. i　　C++;
. J! S( X/ n) W' j5 [6 \: l6 L; D　　if(k2 <= i) % o/ D/ [/ o/ g1 z' o2 w8 ]
　　break;   }2 N2 Q; A$ ?/ Z: N
　　i = k2;
" T6 b: ^. T8 o- n$ ~7 H! N# A　　} $ u2 ^2 ^6 d7 M8 c% c# T$ a3 ]/ [
　　} 9 A. J$ g; C2 @
　　return c%2;
! q( R/ H3 [5 j/ \0 s; J  I3 u& R　　}
0 r; O# n( D$ E# O6 A7 }) B( s$ T: I3 p' \2 _' M
& ?& }+ _, }) A6 g, x
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。