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

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

　　首先定义点结构如下：. B, d1 b* h, J4 }
$ v8 R) i& N# h. }# F8 v, D
以下是引用片段：
　　/* Vertex structure */
　　typedef struct 9 Z: y, X. a0 C& k1 o
　　{ - w6 z* P# m  e: A: z
　　double x, y; 9 M: v: r1 p' n" M: L5 I
　　} vertex_t;

7 X4 n& E3 g6 ?+ @
　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：% d: s& v$ p- \. _
' X; x9 q: O" U. p1 U
以下是引用片段：, l2 d( T0 \; ~) M& o/ Y2 C
　　/* Vertex list structure – polygon */
　　typedef struct * a% P9 C* J: B5 }4 X2 _
　　{
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */ & X- [0 ~' M2 I7 c, Y+ e
　　} vertexlist_t;

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

以下是引用片段：
　　/* bounding rectangle type */
　　typedef struct 4 ]* h3 J) ]2 X8 k
　　{
　　double min_x, min_y, max_x, max_y;
　　} rect_t;
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ )
　　{
　　int i; . j0 r- ?4 i) ?3 W; y' F5 R
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; 9 g* Z9 E+ l* ^
　　}else{
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
　　} ! d/ H. g) ~7 Z) R5 n
　　for(i=1; i  8 M. h; z1 h9 ]. k( X* l
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
* G6 S4 Q; T- U: _2 m6 X) d5 d　　if(vl.y < rc->min_y) rc->min_y = vl.y;
7 h7 I& [$ A/ B8 [# n; {　　if(vl.x > rc->max_x) rc->max_x = vl.x; - o# h' q0 W0 d7 t2 V
　　if(vl.y > rc->max_y) rc->max_y = vl.y;
1 B' S5 I" k/ x" i* @9 o　　} $ W0 E1 j8 y  X( t, y7 N
　　} ! V1 A% a$ z6 S' Z2 D! F8 m

' P, c; Z4 k* |) X8 j1 D/ H9 T6 N4 u3 V( R
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
% Q  r  m9 k* ~+ j3 o& T
3 L  Z. z) ^( E; d( a0 B+ J　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：6 h1 X* L7 @% Q/ I0 ^& A

: o- \& L, F3 ?* [　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
' Q+ r) `; y) O2 Y( E3 K
0 @# D# Z- b0 W" t. v+ G　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;  r+ x3 A) C# P" d* p4 K

: l' ?" ?7 W9 O, R4 X6 b2 g以下是引用片段：& G8 e9 [/ z/ g2 ~2 {# x0 W0 M) e
　　/* p, q is on the same of line l */ $ ~7 X6 n/ U( W0 j- Y  S7 H
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
1 g4 O- a- K4 Y+ w　　const vertex_t* p,
: j3 Y4 q- i* V( P2 W& ^　　const vertex_t* q) 1 T% _$ ^8 X6 Z8 l% A. A% R! K
　　{
; }1 w, h7 t. M8 N" _- J　　double dx = l_end->x - l_start->x;
5 h! ?) y4 ~8 p. ?1 Y, E　　double dy = l_end->y - l_start->y;
+ _4 E' Z4 w9 _3 t5 z　　double dx1= p->x - l_start->x;
6 w" P- j5 W! t' f/ S　　double dy1= p->y - l_start->y; 2 R2 x) y+ i7 O
　　double dx2= q->x - l_end->x;   h& p: E' I* B; s" E
　　double dy2= q->y - l_end->y; 8 H4 |! Z( H5 R! a* Q
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
! S; C4 u" B  f  C4 B: x1 ]　　} 3 {+ t7 E# i+ e' ^) T6 ~( B3 e
　　/* 2 line segments (s1, s2) are intersect? */
8 p* o* h; F. h9 b+ b* s: O- o　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
5 e5 p, i; Q$ Q9 `. Z2 f8 p　　const vertex_t* s2_start, const vertex_t* s2_end) 0 C- W- P8 K( e2 s) O5 F
　　{
) u8 r2 S2 T; H) Q$ B1 |3 j　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && 0 w: p8 b% t7 K( s# P9 ]  M8 {
　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; # E8 \% \/ D' u4 N& n+ _2 }
　　} % l2 @9 I; ~$ r8 D( q
, z& N4 [" ~$ ^& z. ^* \, r

. s  B( Y9 n" \: T　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
: Y9 o( |- v5 T6 F& N4 `& s, ^6 u. A* }+ E' O, G6 J/ d
以下是引用片段：2 N5 m! u& I9 R9 q: J
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
* x, V9 a/ b9 @7 k$ T& _　　const vertex_t* v)
5 V' u7 R: z! {$ Z' g　　{ 8 D# }' S2 I8 E! p& ^$ H9 @9 T
　　int i, j, k1, k2, c; ! e; X" L( `5 ~. x
　　rect_t rc;
$ |7 l8 H5 ]0 s" b3 o; f( Y　　vertex_t w;
5 ?) Y1 P+ b% o( ^0 _" w　　if (np < 3)
" M, @/ S, k3 Z+ l　　return 0;
+ H& x& c2 J5 s1 Q% f0 ?( O　　vertices_get_extent(vl, np, &rc);
, Q, [% U1 {8 ]( q0 F# S　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
4 C# G! Q1 K5 U$ v　　return 0; / \  o: d- n. F: r; R
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
: o. v! P6 d1 v/ y" P　　w.x = rc.max_x + DBL_EPSILON; 6 q' l% ^5 h" y- l% J
　　w.y = v->y; 0 i! w) T3 t& a( V8 q
　　c = 0; /* Intersection points counter */ 5 G( Z" P0 V  G/ Y, H# Q
　　for(i=0; i  3 C) _( d) o1 B$ q# w1 _
　　{
6 c" h6 {' n! N8 @　　j = (i+1) % np;
/ E& Z# q2 J' `9 M' e+ K9 {6 j7 R　　if(is_intersect(vl+i, vl+j, v, &w))
  H+ Y/ {+ S3 A$ z+ r- C, X　　{ ! |4 o# Y' ^* t+ \
　　C++;
+ A$ t  o. x5 `　　}
6 Q2 z1 F2 G, ]2 \8 Z* b) o6 n7 F0 O　　else if(vl.y==w.y) & T% ~% ]' [) G' j, ]3 [. A/ S
　　{
# E9 w5 k; r) }& u0 A/ b7 O/ g" K　　k1 = (np+i-1)%np; : f0 w) w8 e3 t9 o, w9 P$ |
　　while(k1!=i && vl[k1].y==w.y)
" M/ S0 O2 l- ~+ p/ Z6 d, B　　k1 = (np+k1-1)%np;
: C, e& o% y& _1 O　　k2 = (i+1)%np; 0 X: D4 [7 J2 k4 J! r
　　while(k2!=i && vl[k2].y==w.y) 6 O& L& ^- `4 ?/ |! q4 T
　　k2 = (k2+1)%np;
4 |' W! D* l% d+ H　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) 1 M2 B; G3 A2 N0 G0 J! |
　　C++;
4 @' q) M- X. y! |　　if(k2 <= i)
0 U& t! {% [# s# J4 D* V+ n% _　　break;
, e& \+ V  v1 ^: k1 s$ C　　i = k2;
& I! g) Y0 |& b2 E　　} 1 n1 k) E+ g* H6 B0 j
　　}
0 \# s1 ?; H: }# d　　return c%2;
6 B1 Z9 r, d# E, G# @- w' h! Q" R　　}
. }( m' m* d% {. l1 k# k  W$ S' Z7 S1 K* {! L# |6 T, V. n/ w
8 I+ m' n7 f; B$ O
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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