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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。- B  A0 z2 I5 w7 p
: `( e8 L2 K+ E- G) d8 S
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。

　　首先定义点结构如下：
# a: E$ ~* ^2 n
以下是引用片段：
　　/* Vertex structure */
　　typedef struct
　　{
　　double x, y;
　　} vertex_t;
  ^; ]$ g7 I  v( s; Y6 Z4 f" @
  k8 q: Y" z  G9 H. b% J( w
　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：
2 n& |5 ~- v& D! o% Q* L  E
以下是引用片段：
　　/* Vertex list structure – polygon */
　　typedef struct
　　{ : [. [9 u1 r' J. d9 M
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */ 4 [' Z$ i2 S2 u, ]
　　} vertexlist_t; 5 P: l! p' s7 H

　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：
3 F/ h: u! ]; S  \3 z& i: l
以下是引用片段：! m$ V5 ]6 t5 [3 Z2 O0 P# X
　　/* bounding rectangle type */
　　typedef struct
　　{ " U2 v. z  ]- m0 o1 n0 X0 n. r
　　double min_x, min_y, max_x, max_y;
　　} rect_t; 1 u. _+ K5 D$ F5 M8 {
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ 4 M: I7 V( C; ?! A% t" P
　　rect_t* rc /* out extent*/ )   ^, @. _8 o0 d: z( D, p) R" @7 A0 q
　　{
　　int i; / y' r' x( _" h, g! k: R
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; & E% q, I7 \, f( g
　　}else{ ( F9 p$ r* c+ p! g5 G# [
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
　　}
　　for(i=1; i  1 q' A; x( R; H- `* M' F, A
　　{ ! e4 _3 Q6 G" K  x; t# N$ b
　　if(vl.x < rc->min_x) rc->min_x = vl.x; : r+ J! g( h& ^! p9 X+ w  u
　　if(vl.y < rc->min_y) rc->min_y = vl.y; : k! U. M' T- d7 X" g
　　if(vl.x > rc->max_x) rc->max_x = vl.x; - A9 W9 ]6 K+ `; e8 p8 c1 u
　　if(vl.y > rc->max_y) rc->max_y = vl.y; + F2 X% Z9 N* [
　　}
  B, _% f6 M) m　　} 5 E2 s4 k' @! y/ ?0 Z( @% I

- Z6 W. |* H0 a+ [
6 v& p! n: F. H8 ?( e9 Y8 q1 |. |　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
9 @$ Q' M( N% B; c. _0 o
# W6 ~  m) q6 H5 q6 \3 L　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
, d( z6 d( U1 `  q# [! o
: ?4 @5 x7 h' y# V　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;1 q# e% h4 h! f6 `! b( }

$ o4 z  ^, ^, |$ p" L　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;% c3 I" r; w5 z: ?1 S# ?+ O5 _
: ~0 i6 g  e) a. H
以下是引用片段：( J1 n7 |  h7 w  W
　　/* p, q is on the same of line l */ 4 R; `% F5 x, B4 b/ L( R
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
$ O. X0 F: n) W' K% g) |# b6 U　　const vertex_t* p, - J) x4 F$ U6 S; T7 j/ ~; j8 c
　　const vertex_t* q)
0 E$ \6 }& v5 }) j　　{
. W0 q$ S7 \- _9 {4 q　　double dx = l_end->x - l_start->x; " _/ k" d* g& P" q
　　double dy = l_end->y - l_start->y; " H" v2 `' L  U  b
　　double dx1= p->x - l_start->x;
) S3 b4 O$ ^8 w& {# h9 c　　double dy1= p->y - l_start->y; ; l' b3 k) C8 x/ Y  n: `& Y
　　double dx2= q->x - l_end->x;
3 d& o/ k+ h* O) q" _  Z　　double dy2= q->y - l_end->y;
+ ~6 S% T* l+ D1 A7 l' N　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); / `0 H( [  e: }5 [& s
　　}
1 K5 {  D4 u* g$ o) O% f　　/* 2 line segments (s1, s2) are intersect? */ ' S, z% L: ~  y
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, ' h2 K, X2 i8 _  Y( `" p! B4 H
　　const vertex_t* s2_start, const vertex_t* s2_end) 7 t8 X9 r* Y  d7 u) P) m, u
　　{
* y1 G9 f; P8 z% }* q$ T+ H: L　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
6 `) j! f$ V7 \' H& i　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; ( @1 M0 p- b0 f) w( R
　　}
7 N9 b- {( l( W4 P
* \+ P# Q. }6 W  F# h* W- E) ^; u1 |! h& U
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：0 h* r( B! _% [; p; o

- i( f7 s& Z2 z% ^: g4 Z) ]# L以下是引用片段：
( R, L. E4 L* @2 t/ ^) w　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ 3 d7 m& m# C8 ~" `
　　const vertex_t* v) % V& }3 Q, B, p9 N  k* M
　　{
　　int i, j, k1, k2, c; : H$ ]# H: _: P/ |* K/ q
　　rect_t rc; . q5 M6 Z, z1 j
　　vertex_t w;
) I& y0 X! A2 s; |　　if (np < 3) ( l9 B* Q( ^; D, x
　　return 0; / c% V1 I1 @9 n2 @0 K
　　vertices_get_extent(vl, np, &rc); 3 Y' f3 T. j% ]
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) 7 @; E2 z" M- P  q8 J; N
　　return 0;
! T% H' O0 p, o' a: C　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
3 ?3 ^* K- q4 @* ~- O( @; E　　w.x = rc.max_x + DBL_EPSILON;
0 }* i# _' k9 `0 m" y7 C( w6 Z　　w.y = v->y; 2 M; r& U, X0 Q; m7 ?5 b5 c2 j
　　c = 0; /* Intersection points counter */
' d+ g" E* o  M　　for(i=0; i
3 W; S7 G; ]6 W* I; T/ S* K　　{
4 A' y7 c4 T+ P/ i9 |! I　　j = (i+1) % np;
5 {1 Y* R" f. h* V" K# Y5 k　　if(is_intersect(vl+i, vl+j, v, &w)) 3 |' _' v* j5 `- d2 K) t" v
　　{
# e* W. {; {$ Z) \1 h( K( J　　C++;
, T% v$ T& b0 x; Z$ {$ t4 x　　}
4 D! t$ c6 Z7 ]; D. a& x　　else if(vl.y==w.y) & G0 C, ?% _! P. R* v
　　{
" d! b: y, [# d　　k1 = (np+i-1)%np; , j- j" `, k: \& {
　　while(k1!=i && vl[k1].y==w.y) ) N. w3 J( ~! o6 d+ f
　　k1 = (np+k1-1)%np;
0 b( Z- P7 m+ |: O% x' J; R　　k2 = (i+1)%np; : `" O0 l7 Z2 Z+ \: Q# q% P
　　while(k2!=i && vl[k2].y==w.y)
# \0 ^  ^; ^( g! S　　k2 = (k2+1)%np;
$ P+ D0 F* [; X　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) 9 w( h* t0 ^' e, Q* Y( g. [' r
　　C++; " y3 L/ k3 M0 W0 |- ^' g, h
　　if(k2 <= i) 0 s' X* r5 s  V8 I3 I: M9 @
　　break;
* a9 H3 y9 S. i　　i = k2; : S6 ?) S( m! B) _
　　}
( n7 X* k! a; r0 O7 t　　}
" ?$ P8 Y3 u* h5 Z' X+ r4 ]　　return c%2; + {: c' z7 ]( Z( q: G, M9 y
　　}
0 a: Y' L8 e' s) a( P! X$ [3 n; B" z7 C: Y+ ~
$ C: q6 t. g9 n; W" _3 k" g
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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