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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。0 X4 Y) p6 w. w6 ~- `
: M. `( }* f9 C- V
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。4 c; y$ {; l" x/ S3 `: P9 `/ M
0 z2 ]" J& _8 \- i6 Q2 Y4 J
　　首先定义点结构如下：
* f% o* Z* P: K% n& j
以下是引用片段：" [3 X, V8 e! s& b4 c
　　/* Vertex structure */
　　typedef struct 4 a+ [/ i* P. }$ ]+ `' m
　　{ , M* M. E% `& T
　　double x, y;
　　} vertex_t;

4 d6 M9 O+ C3 n' U( I
　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：
* d* w) ]# b1 U( [0 ~( a7 x
以下是引用片段：4 y9 j& m! r2 N: R
　　/* Vertex list structure – polygon */ + ^; Q" r" e# A
　　typedef struct : R& d8 ]& m  i
　　{ 3 @3 {7 p7 x( L
　　int num_vertices; /* Number of vertices in list */ . {8 G7 m% q6 `
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t;

　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：. E) s, l5 u' F9 Z7 `9 n- N
. m; A0 W& ^6 P* R  C
以下是引用片段：
　　/* bounding rectangle type */
　　typedef struct
　　{
　　double min_x, min_y, max_x, max_y; . Z% p% @1 p) E+ u6 H
　　} rect_t;
　　/* gets extent of vertices */ 9 O- a& J8 ~/ V) n& m
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ 1 q! ^! h8 {8 |1 Y: y
　　rect_t* rc /* out extent*/ ) 4 ^, m0 Y7 W2 {5 j0 W  Y0 K/ x
　　{
　　int i;
　　if (np > 0){ - z8 h  N' l+ |5 {# o4 e! M3 Z
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; . o3 R6 Z( }2 j. }
　　}else{
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ 7 H1 L8 B: V4 y+ h+ l
　　} / d3 k" e4 F0 z; c3 E1 {
　　for(i=1; i
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x; " |. H+ L; |- N6 O3 u6 ?  g0 O
　　if(vl.y < rc->min_y) rc->min_y = vl.y; - z6 h" p9 M2 y9 x1 R& I" e3 j% H) h
　　if(vl.x > rc->max_x) rc->max_x = vl.x; 0 C: r. Y0 a7 A% G
　　if(vl.y > rc->max_y) rc->max_y = vl.y; $ G& {+ j6 O+ T' q) c8 B6 T
　　}
# K2 k+ d, ], D* g2 V: y　　} 0 V0 k# b2 \' H+ T" c+ `1 B
7 T1 s: E. T- n* c
3 t3 N% t! B' ?# ?7 ]5 B% z
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
  o; Y, _; T* }- }/ t
/ Y7 I" u3 d' x+ s8 G+ H　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：: k7 e+ g9 v7 M( _  \
3 C$ `+ O3 D, c) l7 X% b
　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;5 q+ f' v8 e* C$ N

" c# |4 e8 B  X$ z7 o" P# Z　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;* A4 K5 ^1 q1 Z7 U7 p3 a
7 z$ w+ A; Z" D5 m8 X' Z
以下是引用片段：
' ~7 {, q/ @7 k1 N4 Q3 v　　/* p, q is on the same of line l */ / f/ Y# R; D0 ~- U
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
1 s, Y/ T4 k; I$ H, ~5 U　　const vertex_t* p, 6 g* _+ B5 j1 r, k  E
　　const vertex_t* q)
7 N; }3 g, t/ E& l　　{ , p- ?3 p* H% m: Z: {5 V
　　double dx = l_end->x - l_start->x;
4 m! N/ r1 F0 x　　double dy = l_end->y - l_start->y;
0 ]  J! V: B; D0 `% m　　double dx1= p->x - l_start->x; ' s  w9 s7 s( G, M. z
　　double dy1= p->y - l_start->y;
# T% l% P: v: C/ ]+ Q　　double dx2= q->x - l_end->x; 7 j" N& h5 l6 g: P" W" ]1 Y( @
　　double dy2= q->y - l_end->y; & S" V3 `4 o& C4 g1 Z
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);   a7 }% \( ^6 S8 r- w0 @/ D
　　}
% `8 l, \+ P( T9 Z7 _% ]8 Y　　/* 2 line segments (s1, s2) are intersect? */
7 H  e2 Z: X& ?; h9 s: g4 V1 W7 |8 o　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,   Z, [4 n4 {. ~* A# Y5 o- L
　　const vertex_t* s2_start, const vertex_t* s2_end)
5 i' [  q# b% L; _* [# j& R* X2 t　　{ 7 {7 Q  V5 L$ x) r! \
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && - v6 \. V$ @. X, Q  W3 {! q
　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
8 y: r& t9 F8 W  J5 E　　}
" C! [# `2 b" |' r: k
& G' L+ D9 t- {7 p
. F4 ]! k# q9 i　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：1 i+ u7 X- m$ n& B0 h$ _/ g) [

2 D6 i' h: O" h& ?. U1 ~+ K以下是引用片段：# _- h3 m/ r& `6 C; V5 g, v7 s
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ 3 P7 J2 w! O: R( M# e
　　const vertex_t* v)
$ Q  i7 c. h1 ~* ]　　{ % ^+ D* ~7 I. Y) K- h4 m: N
　　int i, j, k1, k2, c; : _) r$ r7 ]  [, L0 W
　　rect_t rc; 6 k3 G6 o0 W  |, Y
　　vertex_t w;
7 n! k* W/ s! L1 P　　if (np < 3) . m/ d, y+ q7 V6 G( E) [
　　return 0; 6 N' r& o" i* [* \) X( }7 }# O
　　vertices_get_extent(vl, np, &rc);
$ l$ z& e& O/ w. Y# R2 c　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
! B$ W/ }5 o4 A- D& ~　　return 0;
8 E9 ~9 b/ \$ p2 Y( L9 B　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
5 Q: E+ W. O0 F& L" M　　w.x = rc.max_x + DBL_EPSILON; 2 w  o+ m( |  J) t
　　w.y = v->y; ! L/ A8 p+ {! ]( T( o# L4 p1 L& m
　　c = 0; /* Intersection points counter */ : e- j* @. ^" [1 ^+ o6 M/ k
　　for(i=0; i    w9 d4 P% T; ]0 s  g) G: l. {
　　{
. Q: ~+ w5 O4 m7 O4 v　　j = (i+1) % np; / O8 X% ]( S, ~# l6 k8 u
　　if(is_intersect(vl+i, vl+j, v, &w))
* D/ D. H( B; ]. o  c' K　　{
% b1 z: V- J- d2 Y+ T$ i1 k# j　　C++;
5 x% R  [8 H3 {' B　　}
' T0 G+ i/ W/ |/ P# M  n　　else if(vl.y==w.y)
5 l+ e" h! l' K8 r& E　　{
+ d7 f! e7 n- l4 l) R　　k1 = (np+i-1)%np; ' Z5 w/ b7 b* r" g7 Y
　　while(k1!=i && vl[k1].y==w.y) 6 m* X! j, N+ u* c' ?4 i
　　k1 = (np+k1-1)%np; 9 W; M: E/ g. W8 e9 @
　　k2 = (i+1)%np;
$ R% [$ M0 N& f0 y; Q　　while(k2!=i && vl[k2].y==w.y)
/ m6 ^2 W6 K+ R4 V" ^: o　　k2 = (k2+1)%np;
: t3 o7 o; O& \8 D* ?, [　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) 7 }) |2 }% O4 N% T7 C8 O" }
　　C++;
' U1 r" B- H% p1 o' |9 b# X7 e. v　　if(k2 <= i)
! A) M. [3 a5 a$ J, X　　break;
. ^- y  G9 B, ?7 b　　i = k2; + _% f% M$ ~  E( I  k
　　} ! J7 Z3 l. t. [( n! C
　　} 6 Z6 z+ m6 I" p3 C# M- Y, G
　　return c%2; . ]9 Q0 k8 y) Y
　　}
0 H' n$ U4 s1 x8 @
8 ^. J: @) k6 _1 L' b2 ^) _& ^- T7 A$ G; a+ a
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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