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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。) v6 k9 }1 Z+ P) f4 Y
" C- n. g& g0 r/ U! X6 R" M
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。: l8 ]0 f( l+ p5 ~

　　首先定义点结构如下：
6 x& x1 X5 y- `% B7 K5 K! r
以下是引用片段：0 L6 b6 A5 N% o" Q2 L
　　/* Vertex structure */ & _* U3 x/ s) ~' A1 `' b% F
　　typedef struct
　　{ - G7 @& Y4 d" I) T2 j, W% s
　　double x, y; 6 s7 `' _( D( V) [/ x6 i* J* F8 M8 B
　　} vertex_t; ( `/ w$ A& r6 o
; G: L( _  W. \& N6 q
' ^, ~+ F: i0 v& W9 w' J. _
　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：% N6 F' R& j4 G3 |$ F8 v. a4 b

以下是引用片段：: w+ J( r. e1 B3 e5 h
　　/* Vertex list structure – polygon */ & O- j: ~; F. c/ }. B; u# y. M& t- e
　　typedef struct ) ~* k1 n% D4 _0 o6 ]
　　{
　　int num_vertices; /* Number of vertices in list */ . ~! q/ w* z3 f6 }
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t; $ e# h& z6 p- d5 w

6 d/ }* O2 ]' p/ x: p) x6 @4 l% X
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：0 [# g& k/ B1 ], r" z0 O
4 H: ^, Q  {0 ~7 e; K' u
以下是引用片段：
　　/* bounding rectangle type */ 7 y; e  ~+ i) e- a  W: p$ I
　　typedef struct
　　{ * q& D) N' M7 U- Z! l
　　double min_x, min_y, max_x, max_y; ' y% L! }) \5 m' t
　　} rect_t; / Z. ~0 }. |4 {( E' ~
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ ) # s9 Z! p* Z/ l+ t2 W7 m% Y
　　{ 7 I8 x0 w8 Y% V# Q
　　int i; : i% z: [: `( E
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; " ^; g: Q: V! @  i- K1 [
　　}else{ 5 r) |- [0 N$ Y# b1 E
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ $ t  }& h# y- }
　　} . p; q8 S& l; M. d0 K1 D
　　for(i=1; i
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x; 3 W* I# I3 I: Z, Y
　　if(vl.y < rc->min_y) rc->min_y = vl.y;
8 @& e+ M  a8 U& V7 k. u. f$ p" m( }　　if(vl.x > rc->max_x) rc->max_x = vl.x;
! p" p9 g4 p$ N$ A  B" O　　if(vl.y > rc->max_y) rc->max_y = vl.y; ; ^1 A1 R. T# C2 a5 Y4 A+ K
　　} . _+ p) i# B; Z& X# w# M' N
　　} - U1 D% q" n) u. k! |
- v: V9 K/ r0 D6 e# a0 C7 w
( c7 M. T/ V; Y
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
+ P( T/ |$ h% D4 N2 l: R# k4 K, J: H% s$ {- J1 Q$ C) t% o
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：- T; e& g1 y! \" b0 e8 x+ Z- l5 \& k+ }
5 ]' s+ L# q4 E- Q2 P0 B
　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;: M. a- y, _  j  H
5 U& W. i. f8 q
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;, }% o+ t7 T5 P$ A, [1 @
- L; h. `0 r, r
以下是引用片段：+ f' _+ {: ~" l0 i
　　/* p, q is on the same of line l */
6 k5 A: s! A, e, i# y　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
, N  ^+ @: ~( V$ a0 N　　const vertex_t* p, ! X' ~7 r5 O0 Z* p' P6 W( j
　　const vertex_t* q) ( {, E& r1 Q0 [" P4 r, K
　　{ - r: }$ l7 v  V" }
　　double dx = l_end->x - l_start->x; ( V& M" t' R, a& b. ]
　　double dy = l_end->y - l_start->y;
  d  m8 \6 R: g2 m% B　　double dx1= p->x - l_start->x;
9 s3 {$ Q2 I& q4 P+ w* d　　double dy1= p->y - l_start->y;
8 k% |8 g, \/ E　　double dx2= q->x - l_end->x;
" t" ?' P+ N* f1 t" j. m　　double dy2= q->y - l_end->y; . w7 k; O1 P( N) [: V) d$ ]
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
3 e% U' v2 K% a1 {" U2 J7 v　　} 7 b2 @  q8 Q* d5 F& k
　　/* 2 line segments (s1, s2) are intersect? */
) a( g, I( D" v: o* a( q/ ^$ }5 ?　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
. i9 f) U: T. C　　const vertex_t* s2_start, const vertex_t* s2_end)
. l" u6 l! A( K% S3 ^6 F　　{
. D% o- p: x& C+ w　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
, c3 u! f' D8 b  Y1 h　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
0 H/ G  I8 G5 l- {" B4 q　　} " h( [9 X6 U8 g  i! V
3 O: r) d6 P  r

! C: L  E4 }4 |( z& p7 E5 n　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
5 q5 N: E+ ~9 j: i8 `$ W" v& N" C' N, h, C5 Y9 D3 [% U1 ?
以下是引用片段：
$ [+ o2 K2 w; ?　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
. P! E4 l1 G3 Q+ m　　const vertex_t* v) $ ]6 z, d" |' `4 z4 ~% R9 ?2 h
　　{
% O! P. I5 E/ g7 G+ R　　int i, j, k1, k2, c;
7 G: ^9 w; C. B　　rect_t rc; / N( Y; o0 Q; f* e# s2 x
　　vertex_t w; 3 h; r* i0 H$ k
　　if (np < 3)
3 J5 k& N: Q: g　　return 0; 2 E+ D1 H  x$ {3 r/ M/ V
　　vertices_get_extent(vl, np, &rc); 9 g4 B& C* B& }
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
$ j8 v, I% d, p! d　　return 0;
  V. L% Y- W! \# V( U　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ ; U% E# E; F4 d9 D4 k9 M
　　w.x = rc.max_x + DBL_EPSILON;
8 u% ^3 Z1 u5 g　　w.y = v->y; " \! z6 _( W1 ^! |; n
　　c = 0; /* Intersection points counter */
/ R9 m) [( i- U# W# `( f; Q0 w　　for(i=0; i
6 m6 l1 f7 }5 q& m* }3 [4 y　　{ ; n7 i5 w& J/ R; H
　　j = (i+1) % np;
: U' U7 P4 [' ]$ s　　if(is_intersect(vl+i, vl+j, v, &w)) 7 {+ M2 P( B9 K4 w* x
　　{ 3 ^8 Y! `% \- p3 {  y. ]
　　C++; , w4 a( f( {, i) B$ r
　　} / X+ {$ \6 ]& y  H# ~( x5 s+ Z
　　else if(vl.y==w.y)
' a" ]: S& |+ f- @; ^　　{ 9 i& G! T4 c. V+ ]) E
　　k1 = (np+i-1)%np; + `; }5 O0 N2 @9 q8 m. B- I
　　while(k1!=i && vl[k1].y==w.y)
- D0 p- n8 |! x$ m6 [5 D4 F, x) Q+ V　　k1 = (np+k1-1)%np; + o6 u% e0 V+ i' d
　　k2 = (i+1)%np;
1 K! e+ Z: u/ p　　while(k2!=i && vl[k2].y==w.y)
/ B; j; E) c4 G8 D; J　　k2 = (k2+1)%np;
- R: a& B* g3 a: J! n- Z7 g4 m　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) , z# G; U% G7 v
　　C++; , q# P, \% H, Z% ]1 ?3 J; O
　　if(k2 <= i)
' n3 c0 |2 _  q& F; X　　break;
4 a6 K( K% i7 I0 r0 d7 R　　i = k2;
7 h' f% l" r0 _- T2 }　　}   `" a9 r/ e" U$ m, I0 i
　　} 3 C: }, l( B( e: H; s. E1 K
　　return c%2;
& n" }. |) l* ]" v7 a　　}
5 _. W- o5 z7 f' @! O% V1 k  T+ K4 @) p) z, ^
% d' \! ^% Q* b( m
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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