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

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

　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。

　　首先定义点结构如下：. `1 Y1 ]5 S5 q
# d1 u* k7 b' p# X+ ~) Z
以下是引用片段：, d# z8 R1 z! v3 U1 i) R/ P" j
　　/* Vertex structure */ 6 X' X# d/ g( Y0 r
　　typedef struct
　　{
　　double x, y; % o3 f8 j$ P/ j' N- L: [* C9 w
　　} vertex_t; ) n+ M. z1 [: K8 o8 I! W% U, F# D
" J  F' k1 C& z* I& _

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

以下是引用片段：) @( y/ k3 f- w
　　/* Vertex list structure – polygon */
　　typedef struct
　　{
　　int num_vertices; /* Number of vertices in list */ 5 n$ k: l' W* V8 B6 |$ v7 u, a
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t;

　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：
, k4 J4 u) q4 O, m
以下是引用片段：! |% E% `2 B( D7 m4 T6 T, R
　　/* bounding rectangle type */ ; `$ ~! E" T4 U" a! j# }* S9 I2 J
　　typedef struct
　　{
　　double min_x, min_y, max_x, max_y; ! n2 q8 j- `+ _. a% {/ B
　　} rect_t;
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ ; ^: w3 D$ z8 f  Q* N0 f' t) M
　　rect_t* rc /* out extent*/ ) 1 S1 R$ j) ?3 d" M9 f
　　{ 9 l: y- H: v1 C/ l9 D
　　int i;   g; N% c% u: }2 h
　　if (np > 0){ , z. I2 U0 ^+ l; ?
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;   Y+ U- a0 y/ D6 |% t. R/ L& Y1 t
　　}else{
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ 3 X. d4 t& |6 r- @
　　} * [+ u0 Y2 o& y9 W, H: K
　　for(i=1; i  2 Z" H! L, [9 b" G1 }" T
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x; 1 f0 y' W/ z9 |  Z# W
　　if(vl.y < rc->min_y) rc->min_y = vl.y;
7 \1 n: F. d) h　　if(vl.x > rc->max_x) rc->max_x = vl.x;
0 y1 ?/ l. q* r$ w8 ^- Z( ]" c% P　　if(vl.y > rc->max_y) rc->max_y = vl.y; & Z$ Z6 W0 L+ ^3 S
　　}
. I9 B2 ~$ [" Q% q　　}
  Z- Q; W+ G  F0 x( _0 F. O3 E- t0 _5 M1 G

& W. k3 }0 F' i0 J$ C6 s, g　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
; L. {, G# ]* v7 o& I1 U/ V) d
. {# Y# E& S7 e0 k. m; \　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：* z8 l2 _! O. z0 E/ N: u

8 k. m; a+ {9 }* x. s6 h: H- X　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;+ M# s- n! l( u9 W- E! C! W) J

2 `* E2 {) ~- `2 d9 y% Z　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
5 H$ t" k% J+ q- U' e/ P  T9 z& m6 S: {
以下是引用片段：
$ [( f3 C6 g' A+ U　　/* p, q is on the same of line l */ 1 \  l1 n( r5 I% V$ y
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
8 _* t. z# t) @5 P　　const vertex_t* p, 0 k5 D: C; U$ O, |
　　const vertex_t* q) % P) v7 u0 E4 Q. U' @6 o2 v6 v
　　{
) u/ \* r% q4 x+ v　　double dx = l_end->x - l_start->x; 4 t8 G) T. `# T
　　double dy = l_end->y - l_start->y;
+ V  O% H, f; f& S1 c　　double dx1= p->x - l_start->x; 7 a& I; P. x, |: W5 l5 a2 D
　　double dy1= p->y - l_start->y; ! N3 k  d* c* O; f" ^, H) C* Z
　　double dx2= q->x - l_end->x;
7 u& |7 a3 P, Q* M' l* E　　double dy2= q->y - l_end->y; " ^3 ^  I/ x! Z, C- V
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); ( e* S* {3 n  O) ]: R: e
　　}
0 b2 Q  M) {5 k- E, G' v) l& \- p　　/* 2 line segments (s1, s2) are intersect? */
6 m- F" q1 e/ g- N5 \0 l& W" c4 X　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
4 w7 Z% V- c! |( z# c+ @2 ~7 a( g　　const vertex_t* s2_start, const vertex_t* s2_end) . D" C# \$ ~0 e! c" ~
　　{
* N! K8 y- t1 v& W# i9 X: \6 r　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
' H/ E% m5 M' F/ b　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; . Z+ S0 i4 ^- y7 A0 e3 n3 p" `
　　}
: x$ S$ \0 U9 T4 Y. u( c* N
1 G* D: \, d" V$ ^
; k1 l1 x! P& }　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：) L, U% d- c: S+ B

2 _6 Q2 E# Z; @  X# G& y以下是引用片段：
7 W4 W# K% u, N$ X　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ 3 i- B9 W3 T& I1 W
　　const vertex_t* v) 6 X2 N/ H- j; l( Q* s. D( {" ^
　　{ + V- \* G7 \8 J
　　int i, j, k1, k2, c; ) _6 h' f! e% b/ Z  o$ r
　　rect_t rc;
) d( m- r: x; R( f/ M　　vertex_t w; 2 P1 J2 N6 W' o* S
　　if (np < 3)
9 _# d& I  h. q4 _1 T. T1 c　　return 0; 2 F9 c9 U& r* j8 q4 C" i
　　vertices_get_extent(vl, np, &rc);
2 [8 v7 |6 d6 l　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
" d5 E1 R0 ?3 ]2 Q1 I) T　　return 0; # A, J5 o( Q6 x! n# g
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ . a% ?) j" D5 c
　　w.x = rc.max_x + DBL_EPSILON;
$ G! t. h4 U& V+ z6 j9 T- |. b　　w.y = v->y;
' B8 N7 c( T% G" [. A　　c = 0; /* Intersection points counter */
* L/ k$ E# n2 b$ b; J& X　　for(i=0; i
2 r4 e5 T( B4 `$ j, K6 K% I" \　　{
. E; h# j- h- t2 x　　j = (i+1) % np;
+ r5 `# S8 e& d* Z, r　　if(is_intersect(vl+i, vl+j, v, &w))
& [7 I% a% D4 s! `　　{
8 Z8 ^, V' ]7 M5 @　　C++;
5 ^; e/ M1 }* a) F2 H' b" \　　}
) {. p- l( @8 f; v- c2 k　　else if(vl.y==w.y)
! P$ O# C  s& n& y9 s9 u　　{ # q* Z2 T# t. H0 l% g
　　k1 = (np+i-1)%np;
! R) K' V: q. J9 l　　while(k1!=i && vl[k1].y==w.y)
, }  h9 e/ C7 |- c2 ?) K, @5 K3 @　　k1 = (np+k1-1)%np;
$ X/ x! ^( {4 m  }　　k2 = (i+1)%np; , m& n% q' a9 Z1 b, X4 R* m' L0 v1 K4 r
　　while(k2!=i && vl[k2].y==w.y)
$ A6 \' l. ^, o( ^　　k2 = (k2+1)%np;
0 G' b% |) p9 H　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) ) y# q' Y. a/ W' @; I
　　C++;
9 r: L9 o  B# ]& b) A) |4 |　　if(k2 <= i)
& d* x" J: j7 K" ]　　break; 5 o6 q2 B( G# E' ]4 n8 H2 R- _9 g8 K
　　i = k2;
1 F( ]' d0 ~1 f; k' x! e* E! M( Z　　} * o1 @" i& V. u% }
　　}
+ ~/ J; w- \* k: y　　return c%2; & ]  @  e( i( b6 c) a
　　} ) {/ i" |& V! H' y

. [; `' e0 U$ p6 R- Z6 y- n; b& R: G8 U& Z
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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