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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。: @8 R8 |" s7 C. I; v

　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。( |+ I& }8 g2 {. g/ J" L9 E& f! G
3 n( n9 U$ h1 n/ N, N
　　首先定义点结构如下：7 _$ D+ C1 \' J% ]: t* u
( M2 [) l) F- L% D* j0 d, `4 E
以下是引用片段：
　　/* Vertex structure */ ( Y& R) S1 u+ W, f; g/ O
　　typedef struct ; j- b  d& t2 |) z# o
　　{
　　double x, y; ! q) \% _* J" E" c
　　} vertex_t; $ h. D$ I4 `! i( T% R  H! |  p( q
, r" @" H" N# f2 M% _2 x
6 d7 u5 M# P8 b, \: i! |
　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：

以下是引用片段：1 J' q9 k- Q/ y
　　/* Vertex list structure – polygon */
　　typedef struct
　　{
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */ 4 M, Z" R+ [1 v& O- r2 f2 [( G
　　} vertexlist_t;

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

以下是引用片段：- n7 T9 r  e8 Q: m5 U" p7 A
　　/* bounding rectangle type */ ' q* T$ v6 I+ x) o2 U$ C* ^' U
　　typedef struct 5 w! H: G$ a! L  Y. G- `
　　{ $ q1 ^1 \& B% o4 k. y6 ]( m
　　double min_x, min_y, max_x, max_y; . H& ~! f7 G! B" @% c5 R* z& W+ n
　　} rect_t;
　　/* gets extent of vertices */ 5 T- D1 t% q0 F4 ~6 K4 G
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ ) ; U' V% l! D  u* z& [
　　{ ' P0 e4 z7 N! c# D
　　int i; $ d, J5 @: q/ d" P+ f; V0 L
　　if (np > 0){ ! p) [* t" \  s8 B
　　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 */ . n" D( u4 x$ [3 E$ X. R% i
　　} 9 a: ?- Y( C7 i1 T
　　for(i=1; i  2 F8 l4 p* {* C9 p9 a. p
　　{   k, |; `; j* W" w+ \
　　if(vl.x < rc->min_x) rc->min_x = vl.x; 0 ]( i; \, T3 A2 \
　　if(vl.y < rc->min_y) rc->min_y = vl.y; ; i, {8 Q# G. K
　　if(vl.x > rc->max_x) rc->max_x = vl.x; 6 U% u% }$ U  ]4 f! F# M
　　if(vl.y > rc->max_y) rc->max_y = vl.y;
* O5 I: {  Z( ~& x　　}
, b* n0 c% c) M* X0 _　　}
/ w8 [5 y& m6 N$ T
" `" m$ A+ Z, j) O8 _1 H3 _
* \& b$ Y. E' d0 l2 J9 D　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
, K7 V) @/ L* r0 \% @7 |
( ~4 u# [3 Y5 l& m　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
; d8 E3 ]# L9 t7 z- W
% O- W, ^7 D9 n- t! Q/ \　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
& P, r* s, P: B4 g
( g1 y8 R. h; L' ?; }0 v& `　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
' P# L8 H% K4 C! C) T7 \0 j/ a9 N/ s& t5 j, k) \  _: w
以下是引用片段：: G3 j& I7 g5 v5 M
　　/* p, q is on the same of line l */ 8 Q, j2 n  M$ ^+ D3 k0 d, W3 t
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ 9 p# t% i& R+ L! j0 U
　　const vertex_t* p,
$ `6 T5 a: t5 v; @3 e/ [5 r  c　　const vertex_t* q) 8 q  z( o1 f/ Q$ p9 r) Q. A  ]! }
　　{
9 x- O, b2 R4 v* N; N1 O9 s) z; C- J　　double dx = l_end->x - l_start->x; $ B6 y* L6 e* L; o* E! P
　　double dy = l_end->y - l_start->y;
: Y# m1 t2 n6 z4 D$ u5 f　　double dx1= p->x - l_start->x; # _4 c! Y" G6 R, u
　　double dy1= p->y - l_start->y; 8 i+ A1 |" x: r6 |- d4 B
　　double dx2= q->x - l_end->x; ; l6 n$ P8 {8 ?8 h- t9 @+ V. [
　　double dy2= q->y - l_end->y; ; Y$ r$ N# \" K( `4 {8 w
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); 4 K7 i4 `' W3 [! S! l* S
　　} 6 ?# M' r8 l, z& S
　　/* 2 line segments (s1, s2) are intersect? */
) |& y. P# G& C0 v( e　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
1 M  F1 u+ r0 h" p3 d　　const vertex_t* s2_start, const vertex_t* s2_end)
4 n3 }" r8 \! @$ D" S7 G　　{ - @& w8 l. F+ k' h% F
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
- A% X, \, w) f! U, R4 @　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
' D6 [  M* G/ ~* T1 |　　} 0 y& ]5 X- ^) b) f! N/ x/ Z
$ e& Y/ L" {# o, q4 N! O7 [
2 l5 q8 o" u3 t" k4 ^; C, I/ ~
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
+ f* T0 B% n$ n8 o7 @5 l% B* p, O* y9 ^: q0 E2 n/ C! M! B+ M( G
以下是引用片段：- d3 n; L. [2 U! j% l
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ # Q  @9 X1 h0 v2 V0 H
　　const vertex_t* v)
6 D+ a" b" o1 u8 n  K, j- w　　{
: i0 O5 S$ J  q" U; H: M* D　　int i, j, k1, k2, c;
# {; Z1 }& a& c# }9 x　　rect_t rc; 2 M. v+ ]4 {$ w4 S9 M0 j
　　vertex_t w;
) V: H) C: D6 h: h' }4 U7 O　　if (np < 3)   \* g  l/ O' v* v: M
　　return 0; : Q; I* W4 \) N- F( B" j
　　vertices_get_extent(vl, np, &rc); & F9 K+ w2 B$ H4 V+ M
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
* L3 r( n" H' C: T# r2 ]5 X+ g  m　　return 0; 5 T& t, a3 a$ D( N0 P+ a6 S: k
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ 8 ?7 C- D: }; X7 s" z/ o
　　w.x = rc.max_x + DBL_EPSILON; 3 K  E. |( a, L& A' F+ r
　　w.y = v->y; + r& ^/ W2 c0 Y6 `3 _8 n* S( G4 F
　　c = 0; /* Intersection points counter */ 4 ~* _# @& z% d8 I+ T+ T+ Z' \! {% C
　　for(i=0; i
! h! A$ [) I' n8 F( Z　　{
- ~# G; c* x: E& V2 P, l　　j = (i+1) % np;
( x( Q; t) G+ I　　if(is_intersect(vl+i, vl+j, v, &w))
& g% I9 p: J( J1 T　　{
- K4 Y- \0 D$ C+ C# U! y1 h　　C++;
. Z/ b# S0 H! H* a　　}
4 J; |+ E" t/ A( i, F　　else if(vl.y==w.y)
9 F+ o+ o6 I0 N- ^　　{ / b, d! L6 ^( d6 U. {9 v2 k
　　k1 = (np+i-1)%np; ( Y' p8 R) h" g0 p6 W( s
　　while(k1!=i && vl[k1].y==w.y)
8 I  {/ ?, z8 j6 w7 N　　k1 = (np+k1-1)%np; % {! v, n1 S0 F2 a( _4 j
　　k2 = (i+1)%np;
; G4 Q& r8 }+ y" x6 K5 @　　while(k2!=i && vl[k2].y==w.y) , f' D' C9 z" i4 d+ Z9 m6 P( B) Z" u
　　k2 = (k2+1)%np;
; v, n+ r& a# v　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) 9 h8 W) @$ g0 G+ ~$ ^6 `2 o
　　C++;
/ o+ R1 s- P+ Y, z/ o) `　　if(k2 <= i) + l9 }$ |# V- A! r" @
　　break; & V- \$ z8 c0 h1 i
　　i = k2;
7 m# e8 ~, S  i. m, G) T) `　　} / W3 A0 p9 F3 b: J! S3 _  L1 I0 ~' R! s+ ~
　　} 2 z8 v  D+ l7 x  G$ ?' Q  U0 R8 W
　　return c%2; 0 G& D/ e1 }8 |
　　} 7 k8 s  d8 t2 i+ c
: }% m1 w) F9 `7 r% o' D
: ^+ S. Q% u) U0 C6 P
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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