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

zw2004

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。
$ M2 Z6 f, K9 v2 c: }2 P3 P1 l; |5 h. L2 C. ]) c2 x5 G6 |
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。
/ N4 N( M8 C2 y$ }$ P* _- V2 Y' g- \/ o" T6 K  ]' a; \
　　首先定义点结构如下：
) R) K' R- m2 p2 K( g* q. R% s
; v. y5 u4 _1 n. a% G  i$ O5 [' j以下是引用片段：" z8 A. c2 ]  @: B1 }8 h% ^
　　/* Vertex structure */ . @' T$ Z# ]& x2 X0 |0 `
　　typedef struct
4 N1 }' k& B+ d$ P2 T/ `6 c　　{
' I/ t- s& D5 d4 l8 D! s7 V# r　　double x, y;
" e# g. W% ^0 W　　} vertex_t; # D* T2 M5 B: f. U4 g4 w) j8 n
* _# C1 o, X3 D4 Q0 A+ F

% y( A: a& i+ j1 b- U# G　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：- U7 k: e8 a2 T
; I1 x% v+ u# n2 m5 I
以下是引用片段：
& N" N7 z2 c8 I* o　　/* Vertex list structure – polygon */
3 s' B  z6 \& o1 Y4 q  T: w. _/ @　　typedef struct
  x  M- X" s: X! [, [　　{ / W8 _5 `6 l( b' ?- {9 q+ {
　　int num_vertices; /* Number of vertices in list */ $ k4 p, J. \- S) V- D
　　vertex_t *vertex; /* Vertex array pointer */
- X6 T$ ^  \1 S0 G/ h　　} vertexlist_t; ; U* b0 V9 U) w$ p8 m5 b

% G/ @+ D" l1 r- w! R) q
7 a( ~  z5 g/ _* c- F; }　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：
% W6 w: l7 C9 Z* l2 b$ q2 ?# o6 x6 S* D/ y- g: z% _, E
以下是引用片段：% I$ I: n' |7 i& t$ m+ ~
　　/* bounding rectangle type */ ( c. d0 E4 i4 J/ X) E" `
　　typedef struct
4 B& x+ }0 {! \+ q　　{ ; q5 ?' o8 U/ m# h1 I
　　double min_x, min_y, max_x, max_y;
* r0 s$ ~9 }) z( a+ S　　} rect_t;
# k. H9 P+ [- u' ], I: h　　/* gets extent of vertices */ - J( d, {1 G* o# M9 H3 s
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ * @6 p! d) H  q0 D5 n
　　rect_t* rc /* out extent*/ ) 8 G; g  w! p  ~8 ~+ D& u% f+ p, v
　　{
' v$ L4 N- I" Q% h" b2 Z  b　　int i; 6 e( O) l8 g/ f6 I2 F
　　if (np > 0){
0 E! V+ n" Y5 E& m8 \4 _4 v　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; & u3 _% Z, _4 U8 ^8 D0 N8 T+ _& v1 |
　　}else{
7 l4 B* z0 R9 m3 X　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ + s4 ~8 y" A7 w9 z2 K- B- Z3 a
　　} 0 M! W- D0 D; b7 |3 B# b6 Y
　　for(i=1; i  
" i6 z% p$ K) g$ j　　{ & O' _# W( N: s" A9 `) f
　　if(vl.x < rc->min_x) rc->min_x = vl.x; 7 S4 K! X- {- c0 \# ^( v
　　if(vl.y < rc->min_y) rc->min_y = vl.y; % M; v/ m0 ~5 [: ?, w% t
　　if(vl.x > rc->max_x) rc->max_x = vl.x; 2 w7 U' G2 h/ o. ]. y2 E
　　if(vl.y > rc->max_y) rc->max_y = vl.y; 0 d% @# t* Y* Q; |2 u
　　}
- ]& F6 ^, G( o& g! F　　}
, Z2 i/ V  _# t, u5 f% m
+ `% K: |$ \! G5 [$ F/ `: p  [* \  Y$ B* X7 V: A
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。/ _* C" w2 N' G1 t7 \8 [

# @* M- k1 P# r" C: }/ k1 k　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
$ F. h' J% g0 n( R7 o/ c9 Y
8 a1 k* A1 q# n9 u　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
+ p0 O7 d( W- `) A
8 m* O) O+ g% Q7 }8 P' K! `　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
7 E  l$ I2 B9 ]# v) A  N& |/ \8 L
- X" z+ P1 i, x以下是引用片段：
0 Z" B! T+ h! U. N　　/* p, q is on the same of line l */
9 \$ c  g- x' |1 S8 ~　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ 4 h! f  Z2 M% [  n7 J
　　const vertex_t* p, ; i7 F% p/ j# c- r
　　const vertex_t* q)
3 e1 u% ]! U! \% c　　{
5 y2 ?! |) _. n' T- h　　double dx = l_end->x - l_start->x; 2 v9 Z# s. @- e  w3 A
　　double dy = l_end->y - l_start->y;
# N$ m/ M* H# S$ S5 f& c　　double dx1= p->x - l_start->x;
) M, U7 h/ u  Z/ Y　　double dy1= p->y - l_start->y;
7 K, C% B  w4 @　　double dx2= q->x - l_end->x;
  C9 `& `' p# Z+ J- P5 b　　double dy2= q->y - l_end->y; # M" S, r  w- K5 T; \/ ?; H
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
0 h( A2 n3 M1 R7 r8 t5 V3 l$ t# e! y4 ]　　} : T- w$ _9 g0 c
　　/* 2 line segments (s1, s2) are intersect? */
( c2 f  W9 e  g# m$ L　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, 5 `9 ]3 W: ^9 L  p, ^& a
　　const vertex_t* s2_start, const vertex_t* s2_end) : q& R: _* n$ P# m) l! L6 c  l
　　{ 2 b- f4 h7 A; b( u' V/ q
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && . i5 I2 P+ I% x7 M
　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
) ]8 R- k/ r& {' S3 ~5 ?. T) d　　}
( v+ F# L7 R3 V9 R* n. S4 u/ K( P2 y

+ b# X6 ~# s: ~% [) c" x8 k9 R6 g( d* @　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
1 y, w% e' f7 r. e  L
0 c0 F. U$ U; ^+ E以下是引用片段：  x$ C5 f5 P: B% e' u
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
! C; N# w& @" j6 d; _. z: d　　const vertex_t* v)
: ]. Z* n% ?9 P, H7 g　　{
5 O! d% T: R" C1 Z5 F　　int i, j, k1, k2, c; 3 Z3 u2 ^! F% E/ J8 E7 `( \
　　rect_t rc; 5 r5 x1 K" g1 U+ n2 \* ?( G
　　vertex_t w;
" t5 X9 _4 k# J0 R+ f1 I$ y　　if (np < 3) & S( v+ S' h# ~
　　return 0;
5 N1 U! R0 B$ d4 R2 b7 m% o- i　　vertices_get_extent(vl, np, &rc); 0 L2 Y- h% {/ A! u5 }$ n/ ?
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) % ~" L9 T  M$ v" l
　　return 0;
* `( Q. g6 t3 Z' r　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ 5 _" x* N9 K/ V
　　w.x = rc.max_x + DBL_EPSILON;
2 ?+ G9 N9 e: r; |' r3 M6 W/ H　　w.y = v->y; 2 I; M3 Y/ A7 `6 z4 y- C& b
　　c = 0; /* Intersection points counter */ # O% F4 q, f8 p  v" M: V% x
　　for(i=0; i  0 Q" y' k+ W" f" d. d6 j6 j
　　{ . X. S& S8 ~" D+ [/ l5 r2 w' r2 V
　　j = (i+1) % np; $ o0 {  D! F/ P9 ~. u1 A
　　if(is_intersect(vl+i, vl+j, v, &w))
4 a9 T$ ~  r# ^. D1 q) q1 ~　　{ 4 c4 `2 {2 n/ l3 ?+ C0 X- k' H3 K
　　C++; . m6 |1 K! j7 v5 ^; E" y+ t1 @  z
　　} / J9 {& s$ a8 }5 o. o& X1 \1 B+ I
　　else if(vl.y==w.y) - R& |( g; p0 h" r
　　{
% _9 t1 ~- }, F　　k1 = (np+i-1)%np; - ~# x% h5 ^4 x3 l  Q
　　while(k1!=i && vl[k1].y==w.y)
: L5 Z& z  j: ]: A) p2 O# K　　k1 = (np+k1-1)%np;
4 @* u1 e4 J7 q+ K5 X　　k2 = (i+1)%np; 0 ~& z3 A5 h; e. n; t5 e4 j! t% \! F
　　while(k2!=i && vl[k2].y==w.y) $ t" o6 C+ n+ m! `
　　k2 = (k2+1)%np; 9 F) W- `+ E" l% Q& M( X3 }
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) 3 @( R. {- ?3 o$ V* g) F
　　C++;
' {/ I3 {) j# u9 F　　if(k2 <= i) 1 @: w6 _8 I3 }/ ]3 t% i7 f2 I
　　break; 4 s" T8 E( i5 u$ ]% O- e8 I, C% S
　　i = k2;
" Y4 ^  @  ^  ?9 Q, o　　}
+ ~$ Y! H# z. T1 H1 |2 z　　}
" }4 g+ j+ i4 O# n+ b$ S+ d　　return c%2;
) w  a/ H5 u# _　　}
# s# k8 W  B! ^9 T; U
- Y5 J5 i' C; z  y) N+ G  v
0 J' W0 x, ?: V  |6 s% r　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。