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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。+ \: U& E( a1 h" P4 v* I. F
' P& ~; S8 i+ \
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。/ s. s. m. @1 X, ^9 u) {
3 P1 q3 c# ~7 g
　　首先定义点结构如下：
7 c0 T  w! D6 J
以下是引用片段：
　　/* Vertex structure */ 8 y8 {0 R+ t# c8 J. ~* f
　　typedef struct
　　{
　　double x, y;
　　} vertex_t; 8 @' [) e! ~; g& O+ d0 `4 S0 @

4 ^7 D) D( U5 R4 I0 M& C0 w, ?4 y$ p
　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：' v9 }( D+ y3 v/ G% M  g$ }
+ m& _5 g* m8 Y9 l  S
以下是引用片段：
　　/* Vertex list structure – polygon */
　　typedef struct
　　{
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */ ' _2 S4 f( T( S6 ^
　　} vertexlist_t;
" g$ X; K! J' V% R9 b: I$ i7 \" m

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

以下是引用片段：
　　/* bounding rectangle type */ % M. E3 o+ ?$ b" R
　　typedef struct ) @5 e% {1 V/ L3 F
　　{
　　double min_x, min_y, max_x, max_y; / M! e$ e: _+ Q
　　} rect_t;
　　/* gets extent of vertices */ . l2 c. X3 F$ R9 l
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ )
　　{
　　int i; 4 B9 p( E% U# Q* D
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; / X' b& X- [# {3 F. W
　　}else{
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
　　}
　　for(i=1; i  ' D5 W2 z* o  P6 x+ C8 H
　　{ & w. r5 Y5 C7 L5 w
　　if(vl.x < rc->min_x) rc->min_x = vl.x; 2 e% o& y6 l% N2 l8 F- C3 {, X. \
　　if(vl.y < rc->min_y) rc->min_y = vl.y;
( ?; x7 `  h: K2 `6 @　　if(vl.x > rc->max_x) rc->max_x = vl.x; * e8 ~, I# M4 {% V6 J- ]) H! T' }
　　if(vl.y > rc->max_y) rc->max_y = vl.y;
; M0 J5 c+ i3 _: J0 o& E2 [) E　　}   P1 \' \, \- y4 S  Z
　　} 4 [+ y5 l( ]% x4 o6 i8 l2 ?
0 H% ]5 ~4 l& M* Q" l
" D' i4 s0 y  s; ?/ h+ [
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。! x5 s* s$ @5 }6 \' A+ W
+ n% F& F& _; H* ~/ f3 k! Q
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：# m  Y. v$ E, v+ v
5 m2 h) A, N% f9 v! u
　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;( ~0 y, B! W+ V0 J
9 Y4 _, M/ B4 a8 u# L' c
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;  b9 U  Q6 `& h3 H$ S

, H2 J# j$ v9 [& b! s以下是引用片段：
: u- E0 }4 R4 c* g　　/* p, q is on the same of line l */ + e- H" x4 H( f; G0 h/ J
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
! @4 ?6 }2 p. r( Q' }　　const vertex_t* p, " w" w1 z) Y7 V" b' z
　　const vertex_t* q) ) a% Y; s, O) a
　　{
+ Y& ^7 M1 ~: T3 ~- L. M# f1 U　　double dx = l_end->x - l_start->x;
3 z6 U2 `: \5 F& J& p  M　　double dy = l_end->y - l_start->y;
( d5 z$ x2 `/ o- s　　double dx1= p->x - l_start->x;
2 F+ P- x2 p7 |! Q3 L6 K7 M# X　　double dy1= p->y - l_start->y; % v" D- T6 L  b. a3 n6 p
　　double dx2= q->x - l_end->x;
- u4 S- p4 W5 S- P　　double dy2= q->y - l_end->y;
: W6 D* N  w2 x4 A% U% p　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); 3 q  d6 G. g( s
　　} 7 B% F9 Z0 M' \8 {- f% K/ q
　　/* 2 line segments (s1, s2) are intersect? */ 8 l; O- c! j& |
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
1 O9 @6 F  C+ u* m　　const vertex_t* s2_start, const vertex_t* s2_end) ' _" @1 h" b- J2 l2 ~8 U6 m
　　{
- S7 L3 T9 {; j/ H9 L8 m　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
7 G7 Q  T" w$ N! ^1 Z+ T# F　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
( t4 s) _/ J  A# L1 U　　}
1 Z  J0 k3 \, n% `/ l0 |' r2 C% W* J6 e$ S! Y) ]
& G3 {. w( s+ Q6 s9 z1 t- y
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：: @; v3 J6 [: Z+ y; P4 ]( ~5 B+ W
8 @$ w5 O# y9 U( U. _
以下是引用片段：
. E; y% W( A- [5 l3 x　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
* ^. C% B' J' Y' o1 K* v" P　　const vertex_t* v)
7 D& B7 d7 [& h1 [' M) q　　{ 3 h8 }3 E: u- H) A* Z8 M2 t  @% K
　　int i, j, k1, k2, c; ; f' M* a0 Y0 f4 Y. A1 ^
　　rect_t rc; 3 Q+ L& N; q1 }5 K: B0 G3 ?/ S
　　vertex_t w; % Z# F- Y$ S: ~3 E, }. g+ C( {
　　if (np < 3) ( \" d, O3 a7 g- Q8 z( J# `
　　return 0;
# R+ m$ Q8 j: b; @　　vertices_get_extent(vl, np, &rc);
3 l- {* y6 x% p; o　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) % H* r3 e8 }6 r+ {, Y
　　return 0; 5 b7 u9 y  N% C$ g3 `& z: f! k( M
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ , a  B. b+ b! j0 R4 O7 R! s
　　w.x = rc.max_x + DBL_EPSILON;
4 o5 m# d6 u" x8 `　　w.y = v->y;
# V) {. n, j) M7 I" X8 l　　c = 0; /* Intersection points counter */
: m3 ?& b, T+ h( j8 |　　for(i=0; i
9 R1 `* d7 y8 ?3 s　　{
/ |8 u! c% E- X7 f3 V* R% Y$ F. }; q　　j = (i+1) % np; , O" G0 A- X" \2 F; V7 U
　　if(is_intersect(vl+i, vl+j, v, &w)) : O. A; V  J% ~4 J8 Y
　　{
0 ^! d* Y# u) E  a- A& x　　C++;
2 O& g: x' T$ m/ t　　}
" N" O6 D+ }8 y; q　　else if(vl.y==w.y) % r5 ?3 L+ e: [  V: f8 F6 \# w0 c7 G
　　{ 4 D/ s/ I' t, B5 J/ U. P# {
　　k1 = (np+i-1)%np; + r5 ~/ u6 l( n/ D2 b
　　while(k1!=i && vl[k1].y==w.y)
0 S& U. s1 M4 g9 j5 {! w" g　　k1 = (np+k1-1)%np;
4 f( f( }: ^2 y. k5 ?7 Y　　k2 = (i+1)%np;
; \5 X& b  W+ [% D1 ~　　while(k2!=i && vl[k2].y==w.y) ! p. _/ H2 H) X$ R, r9 M
　　k2 = (k2+1)%np; 3 v0 j. @0 o% n
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) 9 b% F5 A6 U, g% w0 G& X* V) f
　　C++; 0 J! n% v1 z. O9 O
　　if(k2 <= i) ; w! H+ K! w, c  @/ O3 h
　　break;
1 {7 O& f. f! _  `2 G' F: D$ Q　　i = k2;
; {3 U# y1 a* \& B, H+ l) r( \　　}
9 ^% A( \, _, p% |4 h9 i　　}
1 i" [% N2 g8 T0 [0 k) m9 x" U　　return c%2;
# A" v* Q) M9 i6 g' d0 B9 h　　}
; f" |! h3 G5 N9 A; B" v7 k* |
' Y. P$ e4 s: m2 \3 M3 [# B9 U) u8 v! F4 A+ D
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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