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

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

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

　　首先定义点结构如下：
. S9 |  |+ q2 d
以下是引用片段：
　　/* Vertex structure */   b+ h+ v* J1 e0 V+ K
　　typedef struct
　　{
　　double x, y;
　　} vertex_t;
0 M0 T& x% _' @+ N8 n

　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：
, C2 I9 `' z- _" S: f8 v+ o8 B
以下是引用片段：
　　/* Vertex list structure – polygon */
　　typedef struct
　　{
　　int num_vertices; /* Number of vertices in list */ " d% N7 K  P; l, `
　　vertex_t *vertex; /* Vertex array pointer */ , r  t- W9 g; Y' O% ~
　　} vertexlist_t;

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

以下是引用片段：- P0 L! @$ U8 f1 c$ E- [( j
　　/* bounding rectangle type */ ! C: L7 J" C' i6 @9 Y+ K
　　typedef struct 0 `8 b7 G8 X; s$ M" _# U$ N) x. \
　　{
　　double min_x, min_y, max_x, max_y; 3 _- B3 ~: `7 U6 m+ T4 X' L
　　} rect_t;
　　/* gets extent of vertices */ & B( H- s! K1 h3 F9 ^  ?5 A$ @
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ ) 7 q  T: E+ H4 }# U7 I* @
　　{
　　int i;
　　if (np > 0){
　　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 */
　　}
　　for(i=1; i
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
: _/ t$ q2 a7 C& Q, U3 q　　if(vl.y < rc->min_y) rc->min_y = vl.y; 0 |, H& _8 }8 c! r' y; r0 @/ u
　　if(vl.x > rc->max_x) rc->max_x = vl.x; 0 w; ~" ~  _2 V9 }$ A
　　if(vl.y > rc->max_y) rc->max_y = vl.y; / p: N) \' {- ~+ g3 C
　　}
, o# e; P  B! g+ C0 S　　}
* L6 [6 L$ x3 o
: }4 K* I9 D6 n" o& y+ |$ N, Z! x) G. P5 `" }# B' c
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。5 K. h9 s* s8 m0 f% X
  C* }+ Z9 Q; f3 X- a1 o
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
1 j1 {' I( B7 T1 Z9 F# i4 e# k" S3 v0 g- i( v2 {: m9 q6 C! o
　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;) |3 l' Y! U$ {4 X3 ?
7 s5 J7 |1 _3 |2 U
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
( ]  r) Z1 @- K* ]
" ~; P# ]/ F8 u9 {2 c以下是引用片段：
0 {& }( c1 J8 U) n7 @2 O　　/* p, q is on the same of line l */ " P  O2 J# b& S& p
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
2 Y& s4 M" x5 k9 S% s) X　　const vertex_t* p,
7 c3 o0 E& J- d  y7 e# {" _　　const vertex_t* q)
( s6 y+ f+ w; g! @+ P4 q8 E- ]1 @$ l. }　　{ 0 [( w0 P8 {+ d# |7 e( b: `
　　double dx = l_end->x - l_start->x;
0 J' b# b2 T  L　　double dy = l_end->y - l_start->y; # ~! Y/ s, Q* y9 N& p+ M
　　double dx1= p->x - l_start->x;
, P0 S: V6 q2 l# G9 L; ?　　double dy1= p->y - l_start->y;
$ V+ L% s* G# f( m& Q　　double dx2= q->x - l_end->x; 5 [0 W  S! o. R" F% C  s
　　double dy2= q->y - l_end->y; . N9 j$ {! @9 n, a
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); ; E, M; e! r4 j1 R) T9 k3 f4 ~
　　}
. E* b& W; ~# l& c7 `& A% I0 ?　　/* 2 line segments (s1, s2) are intersect? */
  j1 e( n- a" ~! O　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, 6 ?/ s& ^2 M% t' d
　　const vertex_t* s2_start, const vertex_t* s2_end)
: y: x. J/ b% s1 j' ~( W# J2 i　　{
& r$ t+ X) b; Z/ `; `　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
2 K( E, _3 d1 x- Y0 t: F. ?　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; % p% ~7 z% `+ n
　　} $ ~- V( E( L" Q, C
) W: z2 a- N$ j( ?

) e! n4 B* n) Q　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：/ T8 [2 q9 M/ ?) M& O7 r
" c0 }+ Q# d# Y0 N) g
以下是引用片段：  f1 s% A3 q8 w5 a$ I; g, P
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ 5 W2 G$ d( z" J5 M; }
　　const vertex_t* v) ) L' \7 x5 E& }/ V5 A
　　{
0 U7 Q' |8 d: m0 a0 N2 g6 R　　int i, j, k1, k2, c; + t0 \' T3 W4 N6 D$ d4 b3 N- ~  Z
　　rect_t rc;
; D' I& I5 g$ }  _$ w　　vertex_t w; # |+ f. q2 R, C  e, m) _
　　if (np < 3) 2 g" r" D0 H6 a. T, k
　　return 0;
" o# n# \1 P+ |* u: R+ G" m　　vertices_get_extent(vl, np, &rc); ' T2 T# y" Q) |) E% a" n
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
' `# D% L% s* L) s& [) o, F4 p　　return 0; & }* f* ^; s  ^" O8 ?
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */   i/ G6 q! {& v' L
　　w.x = rc.max_x + DBL_EPSILON; 6 w7 ?6 E1 Z! a2 w: M, ?9 R7 J
　　w.y = v->y; 1 b6 ]  K1 Z5 Q1 H, p1 Y! N
　　c = 0; /* Intersection points counter */ " r! q, Q+ q1 U8 k# l) f" O
　　for(i=0; i
0 u! C# `/ a( F. `: a9 Y　　{ 8 b4 m1 o1 l/ ~8 {
　　j = (i+1) % np;
3 G& K( M+ p5 j　　if(is_intersect(vl+i, vl+j, v, &w))
, b# E$ N6 i: d" m. c" j0 o　　{ % l$ ^' |$ B! l. S" ~8 Q
　　C++; ; N2 e+ n, ]" Q" ?' b
　　} - b8 i3 `* p- D8 @5 b/ S+ [
　　else if(vl.y==w.y) ! y% f8 a/ T, M! N
　　{ $ _/ H+ q8 X$ w5 e7 t2 j
　　k1 = (np+i-1)%np; ( r! T7 D1 l; A/ ^  Y8 X) D( E: H4 G+ V
　　while(k1!=i && vl[k1].y==w.y)
! h# y' Y% [1 [　　k1 = (np+k1-1)%np;
; _" y0 R! Z3 |8 }: e+ o　　k2 = (i+1)%np; % n7 c$ D+ ?% c* y5 |
　　while(k2!=i && vl[k2].y==w.y)
- a, x0 K2 y  N/ V! }　　k2 = (k2+1)%np;
$ Q: a2 c8 p5 q4 c　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) % }9 H& O, D& M/ i0 M6 Q
　　C++;
) D+ F! o2 ?% v6 Z　　if(k2 <= i) 5 c+ [+ Q2 }  j- L. f- X
　　break; 1 Z$ {6 O1 ~# O- A& Y' Q
　　i = k2;
6 q- }) o# K: f  v- a　　}
" K% V5 W+ o, [) f0 ~; u! x; U: Y　　}
. t7 e. x( U" k0 K& ~1 o  R' m　　return c%2;
- l% R, j7 y# `( k　　}
, e& p- L6 S9 c+ [$ v
1 X# J* q2 w# ?* N) t/ X# J2 B2 l
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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