2 M' ~1 z. c$ n2 F以下是引用片段：. n5 Z0 Q, C: z6 i0 U+ n
/* Vertex structure */ ; C. t7 F" D7 C* i, B4 @# e
typedef struct : ]+ X1 k" k- W) t
{ + ?0 r# N, @( ~ double x, y; 9 E; s3 i# s/ s } vertex_t; & G/ }) M7 P* W$ u# |+ @
K% C/ k6 h0 H
6 Z# M; w! k A! G) R9 y% [ 本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：5 D6 L4 ~/ v G- v+ U1 j5 F# f- B
4 w, h# y \. i2 w5 K, \* o以下是引用片段： , p) o6 Y/ q% m8 C: u4 @ /* Vertex list structure – polygon */ 3 ~, x! X v7 E9 n- r( O; C typedef struct 2 g, q( T9 \' _1 l% ?4 p
{ 5 p' T* h1 J9 e6 x6 B- h: W# ] int num_vertices; /* Number of vertices in list */ 6 }9 W/ w& F, i5 D( J3 x5 v vertex_t *vertex; /* Vertex array pointer */ % m; u+ |! m( t) S
} vertexlist_t; $ o- ^4 I7 {7 Z; ?1 ]' a2 q
- B0 o& k/ V! ]7 k( p* L. W8 F2 O+ t" D( r) Z- ]- V8 ?5 D5 S$ R
为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：( _4 \3 m& D' I, y a
3 t8 h" P m" D" y8 ?以下是引用片段：6 x9 z. N/ A" O0 B/ g
/* bounding rectangle type */ # G( e$ j' t g* h0 B4 H/ E8 ^1 ^
typedef struct & l0 D4 h* A9 D7 Q) o { 7 `5 q1 s# z% E- D& i; T: A, B double min_x, min_y, max_x, max_y; `, n' o# |. D0 x2 n& t
} rect_t; * C* `: h, w( G+ K* Y1 ~ /* gets extent of vertices */ 4 p# T) q4 K, m- i void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ ; ^5 G) F0 `9 j! |3 w' A8 o
rect_t* rc /* out extent*/ ) , `4 W- s. E2 f; D" f% ` { ; Y x( |) S: |; h8 {4 g int i; : B* G# ?( n2 [: t4 @: j if (np > 0){ ; [$ M) C" R0 q
rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; ! T5 _& o+ o" c) y0 J7 |: T
}else{ % o2 W% R: g; W% ?3 V% { rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ 2 M* c: V. G* G5 d, `
} # B( \; ]* {/ T7 o5 u3 t1 D
for(i=1; i * `# B. x) z( n8 |
{ |6 f) x$ `9 a6 a0 X+ c) d if(vl.x < rc->min_x) rc->min_x = vl.x; 4 N# T5 ~* @, c
if(vl.y < rc->min_y) rc->min_y = vl.y; + `, Y7 H+ ~" v if(vl.x > rc->max_x) rc->max_x = vl.x; ' ]; R4 T5 H1 ]! X
if(vl.y > rc->max_y) rc->max_y = vl.y; . I! c2 V6 I/ i } % \0 \4 F+ s5 y8 Q3 O3 }
} $ v: A$ i. n; B* Z 7 E5 j0 z/ }7 q4 f8 ` 5 T0 ?4 m T2 m% S% ] 当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。 4 n3 E3 P' O/ ?* Z4 P+ U6 ~/ D. `4 `* }8 B
具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：7 \# `; h2 W1 S" S0 N. F
$ E4 t' A% Q1 p" w) o7 r! D
(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧; ; l& `6 K, |* x7 w: Z$ H ! l- L$ X+ |, t& ?1 _& Z (2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;5 J" ^, {0 F0 m5 B8 f( |7 }
/ H# {9 K8 \' K8 B* B以下是引用片段： 8 N9 g" {! i1 {9 y& q /* p, q is on the same of line l */ 4 l) Y& ]. k M static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ & X( r$ z. k& S# q8 G+ \
const vertex_t* p, % f m. R# E- E const vertex_t* q) 1 N; e8 {+ J8 l$ C" b: A { ( J! K2 g; `3 {2 M. g# P } double dx = l_end->x - l_start->x; # v% j& n& L) n; N$ a q
double dy = l_end->y - l_start->y; ~/ o0 J ?; X {8 r double dx1= p->x - l_start->x; 9 f9 s% Y# m. R! J: l. c
double dy1= p->y - l_start->y; - n' d! S3 [; P
double dx2= q->x - l_end->x; 4 T9 v: ]" a- e: q' U4 g( \
double dy2= q->y - l_end->y; ; l: D0 e5 G7 H1 \, p9 c+ f return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); . R1 t) N; R1 }$ F" o
} $ k( i5 _; Q6 G v. j- W6 @6 v /* 2 line segments (s1, s2) are intersect? */ ) z$ T$ `7 ~8 [0 R( S9 X% u; z static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, + T7 W- Z8 h0 V# K
const vertex_t* s2_start, const vertex_t* s2_end) / B' S. t% B. l( I* ^! J6 g( _ { 7 C1 T+ V, P8 Y$ q return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && k5 q- ^" v. L is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; 2 W; }8 g$ g2 J: h } p1 H: m6 E8 o7 o! ^3 S( R- a$ Y" ?3 [3 z- A+ ^
- ]1 M7 ` \; |: g4 I 下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序： ' G5 d( h) q4 h/ X" T0 U5 A. |8 ~6 b
以下是引用片段：& \/ @2 G( b9 n) D1 H! f) u
int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ 0 O8 ~$ ~2 K( f. e7 J
const vertex_t* v) 1 o a' [3 R, E' ]( }8 L( s4 \ { & L/ `4 t5 W' a W k int i, j, k1, k2, c; * t% R" n; f6 |) b4 M/ Y# F
rect_t rc; / }+ {, T. j6 N3 ]' ?7 b! } vertex_t w; 5 I% ] h! ~7 w) O: F if (np < 3) 3 A( G7 v$ }" j- g
return 0; 4 A, l+ x. J0 `, G" t: L8 X
vertices_get_extent(vl, np, &rc); y G( ~ N0 T if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) # G9 |2 O9 V$ Z$ t, ~& w
return 0; $ S; c4 E; O2 a2 c6 u$ x; T* ]7 f1 V /* Set a horizontal beam l(*v, w) from v to the ultra right */ 5 S# f+ P ~7 q w.x = rc.max_x + DBL_EPSILON; ) ^+ v+ f* H% [ S
w.y = v->y; " `8 H) E6 d& } Y8 \8 N( i c = 0; /* Intersection points counter */ ( ~& ?% D' s5 ] for(i=0; i - c( o u2 M, A3 N; G4 V
{ 3 @& f( P2 N4 i4 x
j = (i+1) % np; 9 ?& n1 a+ v4 t
if(is_intersect(vl+i, vl+j, v, &w)) 2 z% B) Y7 }* g& p/ F7 J# u
{ 0 V' f; ]! u- M' Z0 x
C++; : |9 A' K5 s- E, v0 j
} 5 p7 b* C" U( D) ] else if(vl.y==w.y) 5 C* H* T# c. X8 u$ J" f0 B
{ 6 e7 ^; {) W* r O4 d- ]+ B \ k1 = (np+i-1)%np; / ~+ @! D+ T# y$ n8 ? while(k1!=i && vl[k1].y==w.y) 7 S+ o R) [) j J, z k1 = (np+k1-1)%np; * I A. X9 s/ ~ k2 = (i+1)%np; 5 J- K y" Z: T" |& ^2 }( T ^0 @
while(k2!=i && vl[k2].y==w.y) & [/ j* g2 @2 ~' @1 { k2 = (k2+1)%np; & ^6 t2 b: c! B L% N. ^4 W
if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) & h. {) P3 x- H/ P, r
C++; 8 y2 \2 U* _. |0 h if(k2 <= i) ! X2 l5 M: t# ]3 t8 U* f2 Z
break; $ Y3 K2 {6 t Z$ _ U9 s% s/ F
i = k2; ! }; @0 d4 L+ n. C+ I+ ?: m } 2 f7 O, Q X# k% P( E! E; g } " |. u; a2 C3 R: e9 s& ?
return c%2; . k4 j. c: ^! R8 O9 a } 3 g, [3 W/ k, g+ L: G: \) b H0 \+ C* a; W$ _) u$ B & ^( Y+ ^- o, H6 i' s" X 本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。
