标题:
C语言中显示 点在多边形内 算法
[打印本页]
作者:
zw2004
时间:
2008-1-21 17:20
标题:
C语言中显示 点在多边形内 算法
本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。
+ l3 S- H1 |, h& d0 a$ [
% V% W' t# p1 Z% {( m7 c5 V
这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。
2 E' q, l5 _0 V' v Z- s
+ a8 j( i5 g2 f/ W
首先定义点结构如下：
1 G% Y- C5 Z2 N
, X2 L% y8 B# h: d. T5 U
以下是引用片段：
]6 H, x8 t, T# x5 h4 _. d7 ~5 ~
/* Vertex structure */
( G' q+ A9 j: F- D- W( G$ h
typedef struct
5 S$ v. y, b2 F3 |, e
{
! F4 T9 G2 ~: o' x! D: V
double x, y;
1 a8 O, c, }/ M3 w$ T8 n
} vertex_t;
& m' O. S c( o! F6 l1 \& F# P
/ F* z- I- i0 h& \7 n- j7 ^# t
8 E9 a8 f5 _ A. t3 Z5 {# U
本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：
8 k( R! `, n8 P
( U" Z) }4 J0 C! L' @
以下是引用片段：
, X1 W: o3 k% y
/* Vertex list structure – polygon */
% k! g" s2 s1 Y/ y% r
typedef struct
6 X" M' S6 g- J6 }( V* z
{
- x5 \) S0 m. ], U; @6 g+ ]
int num_vertices; /* Number of vertices in list */
* w& {$ b1 v$ ]/ q3 G
vertex_t *vertex; /* Vertex array pointer */
/ X1 \+ @, w' Y% E
} vertexlist_t;
% J s( }% y8 n- }
B4 Q3 F+ C" Y; \) z
* O$ f, H; r4 t$ z9 A
为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：
! S) O5 d, A/ w; V7 P( S& f
I' s0 \: }* I8 A
以下是引用片段：
d* U0 G' ~, V
/* bounding rectangle type */
, h2 i- Q) `/ Q
typedef struct
4 n( e$ @# z1 d
{
- `& l$ ^5 w- P7 x% U& I
double min_x, min_y, max_x, max_y;
! x, C# t7 X$ a- _4 p2 |8 |) w
} rect_t;
% C5 e O# L( S r1 r' d4 t
/* gets extent of vertices */
& g" e7 G+ [# S
void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
+ E- N5 L0 A6 [0 p8 N( g D
rect_t* rc /* out extent*/ )
6 ]. O+ A( [$ k, G" d' I! G
{
0 {6 k3 J* K7 X) ]
int i;
9 h, e8 R- p7 m/ u' Q
if (np > 0){
% B$ |, k V% q/ [& U/ H+ X
rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
; V c9 K6 J& g
}else{
$ E5 @" W4 t {% E/ ~
rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
+ A, |& |5 q7 Y t( d
}
( X) U( n K7 ~% l) I
for(i=1; i
: ]9 b, c9 V% b
{
/ t0 F8 i/ Z0 |) r9 b7 P$ a
if(vl
.x < rc->min_x) rc->min_x = vl
.x;
8 x2 ^: I" N. W9 r# i5 ^# t
if(vl
.y < rc->min_y) rc->min_y = vl
.y;
0 t$ _/ Z8 A5 j7 r
if(vl
.x > rc->max_x) rc->max_x = vl
.x;
( _4 c2 a1 O7 m- i' w8 b
if(vl
.y > rc->max_y) rc->max_y = vl
.y;
2 S2 [5 P% ~1 h
}
9 j5 x `; G7 k( z3 g
}
# o a+ ]) ?( u
; T6 m7 w* a5 D i, \
) B! v. e w7 l6 V2 o
当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
& e: T) \% W2 a$ Q! ]! h
# A& n2 z; P( |: ?5 s
具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
, U! U P+ n5 ?0 B! V8 ]
* B4 W0 }. @8 x) e6 `' l
(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
1 i N: p* w: b M. _. p
7 P* J! D3 l# B, y, k
(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
& q% w2 u5 r1 G1 K7 D% W7 [
& X9 m$ e' U1 {
以下是引用片段：
0 a/ O* X) H( \0 t- I4 \
/* p, q is on the same of line l */
! j1 K7 n1 O f. i, e
static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
3 n2 E' ?1 K: m0 {# O
const vertex_t* p,
v1 }: {) C4 r& x
const vertex_t* q)
q" w) S: a+ \2 s8 P
{
% }6 Q+ ]9 |. N' K
double dx = l_end->x - l_start->x;
/ l# ~) O4 ?8 q( k
double dy = l_end->y - l_start->y;
7 D) I) b1 T! G
double dx1= p->x - l_start->x;
( b8 t9 R1 R7 |) D% s
double dy1= p->y - l_start->y;
) y: A7 S V' H6 D* `6 R) w2 J5 _9 L
double dx2= q->x - l_end->x;
" M& y4 V9 k& c& `: J6 n' }
double dy2= q->y - l_end->y;
+ V/ r% H! w" Y
return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
2 u& B) B7 j* T/ I$ F' d# x7 W
}
- s/ \+ [6 N+ M/ G
/* 2 line segments (s1, s2) are intersect? */
8 X; P. ?9 [0 a# M5 v' A! k, ~
static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
; q: }8 ]$ {# G J4 G) a: ?
const vertex_t* s2_start, const vertex_t* s2_end)
4 S- z4 c+ P' r; k; M
{
! K2 _# {! [1 C9 m7 w' W! @ e
return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
3 y+ n( C$ Z' M" ^9 P/ b
is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
% \! k; r, f+ A
}
% P/ \9 x* h0 c3 M) T
. b' u: O% }0 i g3 y. h4 v. ^
* `8 j: I" z1 w9 ^4 F) x7 S5 K' H ^
下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
! w! {% x; U3 i7 z2 n
& _* c. O2 u9 [3 u+ t7 m, y8 S+ Y$ I
以下是引用片段：
; j) z9 q/ [" N( }
int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
' {+ D, F- D6 i k" s3 K
const vertex_t* v)
# \7 s4 s- R+ b% o- k; @, M9 b
{
7 G8 m1 X: V3 [+ w% |
int i, j, k1, k2, c;
4 c5 g8 z! |* y. |; [3 k/ g
rect_t rc;
7 j. b6 Y4 }6 W5 ]
vertex_t w;
$ n& b n+ D' L. W
if (np < 3)
5 y0 B+ D" u r& t
return 0;
5 h, l1 \! ?& W* ^- L' E0 ]$ F
vertices_get_extent(vl, np, &rc);
+ w$ S1 p: q; R% i7 J) Z. M
if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
# f b1 Q) T3 f. N, e
return 0;
, G6 _- Y9 J- e9 w
/* Set a horizontal beam l(*v, w) from v to the ultra right */
& G( ^1 |6 l7 `! Y1 n+ J, }
w.x = rc.max_x + DBL_EPSILON;
7 |7 J0 h/ u" E2 I, {! `4 K0 m6 U
w.y = v->y;
( n' O1 C4 Y! s/ Y5 {7 [' ?
c = 0; /* Intersection points counter */
9 ^- }4 f x1 E9 l, g& k" r% s
for(i=0; i
* k* {( a8 b, R# `& [
{
( q1 m- b4 c3 m0 I3 p
j = (i+1) % np;
% A# M5 g$ b% G' f* y9 T/ A4 u
if(is_intersect(vl+i, vl+j, v, &w))
: J) c5 V' o" F h A- Q3 g1 M
{
/ ?3 i! K% B8 B$ }6 B0 _. _6 s
C++;
* T9 V2 S, ]9 u- |3 l
}
$ I! v. F, L, k2 Q! E
else if(vl
.y==w.y)
7 m8 f: G0 n" `& b. L
{
- J6 @- G# t% \2 e; {4 X
k1 = (np+i-1)%np;
& G2 ]1 g- T7 ^; R* j
while(k1!=i && vl[k1].y==w.y)
2 Z3 m0 g" F- G& _$ Q
k1 = (np+k1-1)%np;
2 E9 H. m1 W' ^
k2 = (i+1)%np;
- m5 @" t8 @# H( q! j
while(k2!=i && vl[k2].y==w.y)
+ E' M' {% T) s# q+ k
k2 = (k2+1)%np;
5 q% D) e# L4 H8 @
if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
9 C7 d) R- |- G! {3 V+ o/ e3 K% r
C++;
' S c/ h- P; D) M9 Q2 b, h. [9 }/ H
if(k2 <= i)
y# G8 G& A4 b6 B; s
break;
; l( S+ \* z X* i5 e
i = k2;
8 B% S; v! k' C, w6 `, X
}
; W2 G- y4 i2 {, V
}
5 E0 D7 Q! t3 C3 Y3 Y
return c%2;
. z2 f3 z R( a' W9 w
}
0 U- [" d* Z1 E$ L% z
' R# g# W9 ?. t: i( B
& F! @( S7 n# Q" h9 ]1 T
本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。
欢迎光临 捌玖网络工作室 (http://89w.org/)
Powered by Discuz! 7.2
