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

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

　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。  C/ w/ E: C9 S# Y' }3 C
& k3 F/ S' c7 X. ~# \, Y2 }
　　首先定义点结构如下：$ }1 K5 F0 |+ l9 n4 B$ [7 a
6 j  `( u* C. x6 g' ~0 }0 I0 q
以下是引用片段：2 U- \: y% Q; @+ \( ]5 ?( z6 `
　　/* Vertex structure */ ' |9 P" \8 {6 }4 |# z# ?! l
　　typedef struct
　　{
　　double x, y; . F* M; _" E" W" {0 J( [# f
　　} vertex_t; 0 R2 r/ P# `: M

) S- f( s; w  `! h" s' U7 g0 |0 Q8 K0 V/ s
　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：
1 s+ X! g) T4 t- M# q5 W! @. R
以下是引用片段：
　　/* Vertex list structure – polygon */
　　typedef struct
　　{
　　int num_vertices; /* Number of vertices in list */ / @; D$ e0 @6 n
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t; 2 f# p) |5 k/ z; g
& ?: e. b. M8 N9 s1 I
! u7 b+ D& t: N% y  F5 v
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：0 `# R% P# J9 O9 {: b# \7 u6 w/ H
- }/ p: I4 k4 }5 c0 h! Z
以下是引用片段：
　　/* bounding rectangle type */
　　typedef struct
　　{
　　double min_x, min_y, max_x, max_y;
　　} rect_t; 2 d" ~2 }4 b4 ]% U6 {, |
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ ! d8 S$ d1 x8 N4 A
　　rect_t* rc /* out extent*/ ) ! `) I  {7 i" A$ J+ A  R- V
　　{
　　int i;
　　if (np > 0){ . l+ Q5 r, V6 J2 S% ?0 V; b4 I# u! \
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
　　}else{ - y5 d- }6 k' a+ ~; n
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ 5 ^; W' r! i6 m& v6 y' y' ~# ~2 m! h
　　}
　　for(i=1; i  6 u5 \: l  I5 w/ s- C
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x; 7 c5 W1 q& L; h8 x
　　if(vl.y < rc->min_y) rc->min_y = vl.y;
5 t1 K, ]$ U- l. ]$ c) I/ O2 B) Y　　if(vl.x > rc->max_x) rc->max_x = vl.x;
! a& m' j: _* j- s4 v$ F　　if(vl.y > rc->max_y) rc->max_y = vl.y; / n" \7 \- L, w1 }9 w% e  |' R
　　} 5 @" f8 ^7 B! W2 V+ R2 R$ P
　　} ! s4 U2 w* `  K' m7 J( |. L2 Q

) ]/ @; o1 X- a1 T5 f
1 j- T% A. @+ Z　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
5 o+ j2 P2 D$ L, y( c8 k8 M& m; f# P
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：; p) W( G: ^3 ?  L) Q

$ s; v' t) ^2 H+ ~) q# q  J　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
# g9 O5 S, N! a" S# \- U2 P* A% v* ?. m. C+ s- q, |6 N& C
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
1 }! O- ~$ `" g$ B1 Z/ d# Q" a
" @5 N" o% [; [$ Z: z以下是引用片段：
1 G4 t+ s! M$ c; ~　　/* p, q is on the same of line l */ 1 B, Q" M$ f9 r- ^; I; ]
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
6 v/ B% q* J& Q% {　　const vertex_t* p,
2 w7 J# ]2 U8 i6 \/ J& s- I" Y- ~2 @　　const vertex_t* q) ; w& `5 T- o  F
　　{ ! p$ a. F; f3 e% J5 E! B  }  `
　　double dx = l_end->x - l_start->x; . X# N* S! b& B1 @
　　double dy = l_end->y - l_start->y; ( G2 b" T+ y' P0 s; R
　　double dx1= p->x - l_start->x;
: ^  m/ r: D; Y, D　　double dy1= p->y - l_start->y; : X. g  B* ?" i5 m! G* C6 j* w
　　double dx2= q->x - l_end->x;
; Q7 @' \* e8 E/ c) k) s- Q　　double dy2= q->y - l_end->y;
. ]* A0 y& B8 D! B8 c4 ~　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); ! n5 m. L9 l: O1 C: H
　　} 0 V, x$ M9 j- t" P; _; A7 N3 L
　　/* 2 line segments (s1, s2) are intersect? */
0 {2 ?) X, F4 G% {, {" a7 }　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, ; m2 ]9 f4 o9 s
　　const vertex_t* s2_start, const vertex_t* s2_end) # b' [  S% K' k7 E6 `
　　{
5 Z! H4 |6 [7 [+ y　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && , T( }/ g4 n0 u) o' _5 P
　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; 9 z/ q8 ~! f" `; k' n) s2 X7 L
　　} . C9 z- n, w! @% D  h

& K+ B1 A6 y7 k5 y6 `8 D
; l; z. s" a. p　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
6 b7 d- r4 r! s5 b$ u7 z( d3 r$ _9 Z$ O, c) B6 o/ q6 q
以下是引用片段：
; W1 U% q4 c( Q) L( |$ K& ]　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ 9 C7 g8 G1 z7 w+ ]5 B+ L' B/ S8 `
　　const vertex_t* v) : O0 _* s9 D$ v6 Y
　　{
, P8 G, l4 K8 }! j  f0 A　　int i, j, k1, k2, c;
0 {2 o3 l. n( s# M7 i2 [* l　　rect_t rc; # x& o) k6 Q" N9 h1 G
　　vertex_t w;
5 d: p1 S7 z2 x　　if (np < 3)
, e1 N3 y3 Z2 M: S& V  f  S　　return 0;
/ b+ [$ T$ a- h4 u　　vertices_get_extent(vl, np, &rc); 8 }; U6 @0 t( w- [
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
1 r; L, j9 g" w　　return 0;   z, @* b9 [* L8 `0 N* A* e
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ $ |/ ]; T' w7 l$ V
　　w.x = rc.max_x + DBL_EPSILON; 3 g  p9 {4 g1 s
　　w.y = v->y;
/ [  W1 L6 s4 h8 E/ j( b　　c = 0; /* Intersection points counter */ & r3 V- G/ V) p4 u. f' I. m; h
　　for(i=0; i
4 a! |% O. K4 Q3 n" g2 F　　{
6 [  D0 v9 c# ]9 ~* [% G　　j = (i+1) % np; * F; {2 B' ?% x, }  `: i5 ]4 b/ N3 J
　　if(is_intersect(vl+i, vl+j, v, &w))
: W2 P* N) N% k6 P1 h- X1 x　　{
0 W) T$ B  P( l7 |" W, u　　C++;
5 N8 j8 \0 E. e0 u$ K# _) W2 F　　}
! Q# W) b: S' k+ B　　else if(vl.y==w.y) 2 |& y6 }4 T3 @8 I: `9 c0 i
　　{ " V) m6 B0 v( K/ _$ S) E
　　k1 = (np+i-1)%np; ( z$ t: F3 U4 ?: c4 o( x
　　while(k1!=i && vl[k1].y==w.y)
2 X0 p$ S2 x, L: b+ X　　k1 = (np+k1-1)%np;
7 o5 X; |' K9 u+ ^2 _　　k2 = (i+1)%np; 9 E/ M+ a$ J- h* Y1 L
　　while(k2!=i && vl[k2].y==w.y) % ^9 _' p3 q% t& h! D) t
　　k2 = (k2+1)%np;
, M' e3 A3 @, R7 Y　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) 0 ?& {$ e: {: T# L! H1 M$ m
　　C++;
2 j! k* Z, v9 \　　if(k2 <= i)
8 \! H/ w& ^% b4 H/ R　　break;
) q$ n5 E& j( Z& G4 r　　i = k2; 5 y! @2 e2 I; H: x1 {
　　}
( U+ P0 D9 O" x1 B8 Q8 `　　}
5 }, }2 j9 D& B2 M/ }7 ]　　return c%2;
* y. N8 Q1 ]" `" R* u3 @' B　　}
/ O( E, V& Z6 r  M5 Q7 A- G) \( Z: U1 P1 H- ^! @
( X( O3 `2 Y6 s( \
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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