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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。
) M" n6 g! D( a1 ?. u
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。: p$ \5 ^2 [5 i. s+ @

　　首先定义点结构如下：4 R! q5 Y6 h/ `* a1 N% w, r
0 q! a( `7 }$ w$ e
以下是引用片段：
　　/* Vertex structure */ ( g# e; `$ k. H( n8 ^4 a# ]
　　typedef struct
　　{   c, _# z9 c" I6 K& f
　　double x, y; . ^/ T& m/ u5 w# r5 p+ {# R
　　} vertex_t;   Z. {! t- ]  K' ?( s/ g
" P* f  m1 m3 ^- C+ K' o. h$ Q4 m

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

以下是引用片段：6 C& U! i- j2 w
　　/* Vertex list structure – polygon */
　　typedef struct : `, _0 P' v" z0 i- G
　　{
　　int num_vertices; /* Number of vertices in list */ 2 z2 C1 p" K5 \% W8 j$ V
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t; ! `" L( c7 j, J8 `! Q: p1 X

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

以下是引用片段：0 @1 [1 ?+ Q% ]& D1 I0 \
　　/* bounding rectangle type */
　　typedef struct # W4 H7 _1 S% n6 E
　　{ ; `/ Y5 c! U9 G# x; {$ T5 b7 e
　　double min_x, min_y, max_x, max_y;
　　} rect_t;
　　/* gets extent of vertices */ ) l8 V' c' U' f" Q* }0 _% b4 g# Q! U
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ )
　　{
　　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 */ + t& C6 @$ S9 Y: \6 b
　　} . D3 m8 h) F1 M  \, v; d- L
　　for(i=1; i
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x; 2 i* V6 s- i; B! E/ E* H! h5 O, U' V0 R
　　if(vl.y < rc->min_y) rc->min_y = vl.y;
/ u3 m. ]# ?0 h: m　　if(vl.x > rc->max_x) rc->max_x = vl.x;
" O. ?. v0 ^1 ?/ B　　if(vl.y > rc->max_y) rc->max_y = vl.y; # B; F1 b+ R) |& a2 ]
　　} ; X6 a* I" H  D, s3 w
　　}
0 L% e; D* s9 m; I/ {* K+ Z  x) q! Z0 Z- p# F
% ^7 [3 `8 I! ?0 B" R0 a
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
; e, q% Q& |( x- r% s8 @* l9 W3 `' L" {4 ]( E! A( F' y
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
$ v9 W1 E8 q8 J; K4 N
) E8 l6 O  |6 k: O　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;$ I. i1 K$ q! {4 x7 g2 y

+ D2 `3 N/ t4 K, z2 l- C" |* G: a4 a　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;9 E" z- K5 C$ p
& B  F$ e2 F* `# Y
以下是引用片段：8 W; y2 }$ o- _, {( g
　　/* p, q is on the same of line l */ : J  v4 e( ^# b5 R' f
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ 8 C. f4 S: }- E7 ~; t3 J7 [7 o
　　const vertex_t* p,
2 @+ L+ \* C- X& l8 K　　const vertex_t* q) & G9 L6 z" k+ I7 C6 u) d3 F2 o
　　{ ( P( K5 T" h9 v
　　double dx = l_end->x - l_start->x;
- B( d! p# W; E2 @9 D$ k& k3 R　　double dy = l_end->y - l_start->y;
) i' G+ x# b. ~* G# R9 a　　double dx1= p->x - l_start->x; 9 f' c) _$ k3 p# q
　　double dy1= p->y - l_start->y;
) b2 }, G- V; P4 Q: P　　double dx2= q->x - l_end->x; 4 k8 q/ X& k/ ^2 t- [& ]
　　double dy2= q->y - l_end->y; " P* q9 v; u7 b6 M, D
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); ( C1 v! U8 _- X3 S
　　}
. B9 T3 }6 l% m/ I5 `( g: m% E　　/* 2 line segments (s1, s2) are intersect? */
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, # _$ F9 k" x3 S7 H. Q2 E0 ?
　　const vertex_t* s2_start, const vertex_t* s2_end)
+ ~" b+ d; F0 L* i8 O　　{ 8 K8 C/ K* y* |2 ]) I: t  k
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
9 ~& R7 V5 M+ i+ L+ s/ q1 n! D　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
; U* u7 k8 s1 v) q: c5 ^- h% |( N　　} 5 T( v% j) ~3 X& I4 o7 l
* ]* e) [' m2 \% b

; c; c% s; |$ a% w, b0 r　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：0 g" q2 v  ~7 F+ m( A% I

& a* Q/ B. d# ^+ Z' V以下是引用片段：
+ [& W3 Z$ V3 G. g; ]; [8 E& d$ H　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ * W$ @7 L8 O# p9 q
　　const vertex_t* v) " f4 P# L8 }7 C! O# i7 J
　　{
7 I3 Z2 O. E6 j　　int i, j, k1, k2, c;
　　rect_t rc;
; C: W: H# y% E3 f/ }　　vertex_t w; , e1 }- N7 \, _: M7 E
　　if (np < 3) ; G) \, I) o7 E! G1 p6 a" z
　　return 0;
$ ~4 D! C2 Y! j* j$ B' q+ c8 u　　vertices_get_extent(vl, np, &rc); . R' J6 D; V$ J/ P2 b
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
4 I: U$ G: C2 D! {% B" p7 ^! E　　return 0; $ x! ]7 _1 T* n( P- W
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ 2 A( m6 x3 I" _( e* J. R. M
　　w.x = rc.max_x + DBL_EPSILON;
& @& M( ^  d2 S, u) i1 F: e+ {8 s　　w.y = v->y; $ Z& M! [- ]  ?3 {% K
　　c = 0; /* Intersection points counter */ : h- ]  f0 `. M+ ?4 x
　　for(i=0; i  8 H9 D3 b% n" e4 X0 I* b
　　{ , I3 d  ]7 b/ |. \  ]
　　j = (i+1) % np; ( M3 L  E' F. T, c3 \
　　if(is_intersect(vl+i, vl+j, v, &w))
3 c* L9 ^3 ~& c' V) A3 R　　{ ( e/ a. B# [( d. {
　　C++; & n, m/ A* I' H9 C# Q7 h
　　}
2 f, I7 a3 k; k( F- i; h% ]　　else if(vl.y==w.y)
: v- g% ^+ |: ]　　{
: Y4 O2 E. F1 Z* A7 Y# G　　k1 = (np+i-1)%np;
' W+ _7 A) e. D9 U$ y　　while(k1!=i && vl[k1].y==w.y) " Q9 w1 [% c- g; C! e- i
　　k1 = (np+k1-1)%np;
6 ~" T) [7 A& p$ N8 E　　k2 = (i+1)%np;
3 h+ ]( u! @2 |: E1 L" y5 n1 w　　while(k2!=i && vl[k2].y==w.y)
# D, P, z* X/ x: d# N( N　　k2 = (k2+1)%np;
* R! ~5 @0 U1 G1 Z& e$ x　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
( k# ~9 T" ~1 ]/ x5 ]1 O7 K8 M: |　　C++;
7 x0 }. K. w% e' t" D　　if(k2 <= i) / G' W$ @" K, v3 P2 \7 y  ]* r
　　break;
/ L9 u, {8 [# s& U6 }' h　　i = k2; . i6 Y, v0 K* Y  t3 x
　　} 0 g1 s& o0 f, j" t
　　} 3 x  k1 `' O4 X, e
　　return c%2;
) G  d2 v' m, h4 M: G0 I% u　　}
' T. E( s9 b2 U, p* d3 ~/ {& X$ Y* h1 Y* V6 Y+ i
8 E/ u4 O5 |0 C( B
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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