|
  
- UID
- 133
- 帖子
- 51
- 精华
- 1
- 积分
- 186
- 金币
- 55
- 威望
- 2
- 贡献
- 0

|
C语言中显示 点在多边形内 算法
本文是采用射线法判断点是否在多边形内的C语言程序。多年前,我自己实现了这样一个算法。但是随着时间的推移,我决定重写这个代码。参考周培德的《计算几何》一书,结合我的实践和经验,我相信,在这个算法的实现上,这是你迄今为止遇到的最优的代码。- G2 E* {0 D! T6 M
9 i5 Y" p& r$ B5 c4 @" C' V; P 这是个C语言的小算法的实现程序,本来不想放到这里。可是,当我自己要实现这样一个算法的时候,想在网上找个现成的,考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心,所以,决定重新写一个,并把它放到这里,以飨读者。也增加一下BLOG的点击量。- T! |2 p! Q( @: v( ~5 G
; w8 j; {0 b( F' B 首先定义点结构如下:# g8 Y' U9 c+ I1 _8 h
/ {) M4 E& P, E' m8 L; E6 h, E, S以下是引用片段:
8 I, H! J3 Z+ T4 k" d- A; p8 \ /* Vertex structure */ , l7 U8 N3 e. V# F% y) V# J9 l* H
typedef struct " B8 }: X8 ^. n% Q I
{
; L/ h" D& w8 P! J0 \. ] double x, y;
3 _( b6 k: a6 k3 P! q/ o0 `8 z } vertex_t;
; T/ U, h$ a, I8 U# V- M# @( F" d0 P- ~& o3 j+ D
2 v5 T5 j" F7 @* s _9 p
本算法里所指的多边形,是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的,包括多条边在一条绝对直线上。因此,定义多边形结构如下: f5 t$ D, I& H) T9 U; y
/ y+ U/ p& v) K% {# D! @以下是引用片段:
7 v9 `' {; Z: Z! a /* Vertex list structure – polygon */ * Q' `! A8 q4 v& @
typedef struct $ p) N8 K' X f# E8 U
{ , B# Q# m, U* `3 q" V+ x1 |2 T
int num_vertices; /* Number of vertices in list */
$ I2 h: E* N8 ]1 y p, X7 R vertex_t *vertex; /* Vertex array pointer */
. V4 D# n# G- i$ y } vertexlist_t; * G/ V# Z! P `2 k7 f
- p6 C: `# d1 ]# U& T0 f1 }) b7 H# ~( |8 P3 g
为加快判别速度,首先计算多边形的外包矩形(rect_t),判断点是否落在外包矩形内,只有满足落在外包矩形内的条件的点,才进入下一步的计算。为此,引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent,代码如下:- p' B+ q* y' W8 |6 B
' O% M3 T" o' h+ {以下是引用片段:) X2 w0 U* J! g% C
/* bounding rectangle type */ * ^' X; d$ L5 {( ~2 Q; T$ p3 L
typedef struct / ~% [9 x; H6 }( K
{ 5 r) d" `2 u+ z6 D" x; S' j
double min_x, min_y, max_x, max_y;
' u5 V j8 O9 \! ?; R4 C+ V6 F) s } rect_t; ) f4 ?8 |0 Q& X4 ?
/* gets extent of vertices */
1 \, `' }! d' T void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ 7 Z! |( `; P% Y; F; r
rect_t* rc /* out extent*/ )
% \1 o/ y" E/ W { * v) ?1 j; y1 g& ~. f `" C5 G6 k
int i; ; _6 G( `% f8 z2 [7 T! e; I s
if (np > 0){ # d( m9 y' @; b9 t2 _$ W/ C& ^
rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
, \# T& z1 O" Y X }else{
* z+ Z% n5 ?, T+ ?* Q! J/ S% c rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
& j! U3 ~. b8 p2 ]* B. Q }
/ O1 v! {# [! c% H o- C for(i=1; i
; G# l+ b' Z. v) } { : M3 `& r' _1 }
if(vl.x < rc->min_x) rc->min_x = vl.x; . L6 V% U1 I/ {5 v5 _( U( l4 a$ N
if(vl.y < rc->min_y) rc->min_y = vl.y;
* n4 q2 O! {3 l/ d4 m: @ if(vl.x > rc->max_x) rc->max_x = vl.x; 2 E! J0 P2 p# r- m Y
if(vl.y > rc->max_y) rc->max_y = vl.y;
, F. R+ u1 D2 k }
% x; _0 ], E4 o7 t0 L' u }
8 q% ~6 o0 t0 W K9 g8 I, }2 J
' \8 c# F6 h D% p* i" X% q# `% n3 Q. U) t% x# e6 K
当点满足落在多边形外包矩形内的条件,要进一步判断点(v)是否在多边形(vl:np)内。本程序采用射线法,由待测试点(v)水平引出一条射线B(v,w),计算B与vl边线的交点数目,记为c,根据奇内偶外原则(c为奇数说明v在vl内,否则v不在vl内)判断点是否在多边形内。7 H y- u b( q8 X- u7 E
* P8 Z( a+ x& W* o: C& Q 具体原理就不多说。为计算线段间是否存在交点,引入下面的函数: H" M5 |9 n5 m7 J* k& r
5 x- U2 L8 e& Y [; u8 k8 B
(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start,l_end)的同侧;) `4 \* Q! Y6 ~' P* a
4 h0 X& q6 X* w# l2 z (2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交; l2 j- }; v8 y1 |
( v. h' y- Y0 _+ b! d- o. R
以下是引用片段:5 u2 l1 M* F4 v X R. I6 N" V
/* p, q is on the same of line l */ 1 D# O/ `' a. \ L1 ~3 v( `% t
static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ 1 }) ^, M2 A2 t/ e0 j+ x
const vertex_t* p, ) W0 _+ \9 q7 b( }' u1 o2 Z
const vertex_t* q) # z/ j p- U& I0 j# c4 T4 J; H* X! R
{
! J" U0 v: R. f3 ` double dx = l_end->x - l_start->x;
- N: T a( X2 Y# ?' }3 M double dy = l_end->y - l_start->y;
5 l( C0 B7 ]* h: ~ double dx1= p->x - l_start->x; 8 Z9 X0 O6 P8 y, P+ ~
double dy1= p->y - l_start->y;
/ v! g$ Z U7 G' f! W0 C double dx2= q->x - l_end->x;
1 f" x* M" ]6 n% I* u! p double dy2= q->y - l_end->y;
& d9 x& `$ w7 t% l return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
) q4 v- }- P h/ D6 t+ c }
8 S: a$ E3 J- Y" u. R /* 2 line segments (s1, s2) are intersect? */ 9 ], Z& a) @( g, Y( a, k
static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
! { f5 ~5 N3 c const vertex_t* s2_start, const vertex_t* s2_end)
* N: r H8 ^& k* G1 e1 ? { * }/ ]. A6 l8 i) x! t
return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && 4 v# i/ S9 C: O3 t
is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; - R1 \3 p5 V8 H" }
}
" o2 L$ r/ X" b9 W( G& _4 t; k8 i% ?# `& T7 K/ o
: W! v1 x# j6 }: S* I
下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl:np)内的程序:
: s( j$ l/ h1 a% A6 G$ R; j
9 p1 j2 }9 T" E! y以下是引用片段:) N4 B9 K* M6 W9 g6 q
int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ 5 `. j3 V, n6 H3 Q( r. ]# G; E
const vertex_t* v)
$ ~4 k3 v+ a$ e- h8 H' X { 7 m% v# B1 H4 D" U
int i, j, k1, k2, c;
8 ]- P7 x) V& C% l6 }8 T& i6 E. y& R; n" p rect_t rc; : O( y/ }$ Y8 ^! m( k# A
vertex_t w; / ?0 Z4 [8 u9 A0 {) s% d
if (np < 3) ) {0 `5 h3 K2 v& B8 `! y) n
return 0; ) m4 q- M; |' u) p# P- E
vertices_get_extent(vl, np, &rc);
. Q( s7 G2 n; A( B& ^ if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
* C3 w1 R/ T' Y- G2 i5 D j return 0;
4 B* Z9 G6 ]) }& {* K! w /* Set a horizontal beam l(*v, w) from v to the ultra right */ $ a$ i+ O. m; h U7 b3 U
w.x = rc.max_x + DBL_EPSILON; " r! n: v, B3 h0 P5 @
w.y = v->y;
( v1 F* ~0 ]0 Y \% D, x0 L7 {2 N c = 0; /* Intersection points counter */ 2 y: a2 l* o6 d! k
for(i=0; i % X% t4 h S$ [- y" ]! L
{ + _1 W6 s: v' D& D" n' L
j = (i+1) % np;
" ] `/ h' M7 m# v" f if(is_intersect(vl+i, vl+j, v, &w)) # t0 K2 J* m$ _3 D6 ]& _; B' c
{
8 z: x- e8 O$ Q- B0 r. \3 j! r4 r0 w1 p C++;
) s% `3 u2 K7 _" h; b( O) Y }
0 }) D! i+ C+ s# P* b1 Y3 Q else if(vl.y==w.y)
y* K" K( |+ I: @' q a {
# R! ^; I1 Z. v6 u% O) g k1 = (np+i-1)%np;
! E5 }1 D; [. @$ g: c7 P while(k1!=i && vl[k1].y==w.y)
@& G1 k! S8 m% y, U k1 = (np+k1-1)%np;
: n1 B# Y2 ?" A1 x+ H* T4 w: R k2 = (i+1)%np; ) b) C1 A2 F- x
while(k2!=i && vl[k2].y==w.y)
/ z3 {$ i6 l* N* n5 y. B6 F k2 = (k2+1)%np; 7 t; k9 Y2 q. u3 N8 I
if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) ( @; W$ J) ?5 b* N
C++;
) l- h# N/ O: Y# n9 @ if(k2 <= i)
' N Z* x3 O) z break;
% t* }/ `& p5 ^ i = k2; ' E5 [0 m8 h( C- u% j% n
}
9 }9 H% `5 ~3 h$ O } / O$ [. `- c- Z8 d2 H, l. {5 o
return c%2;
* [: R! ~9 j7 }* v7 l& R } - E! J: A* L7 E! e2 _
4 X( r* g! P- A9 J
7 P h- {0 f ?7 L0 M9 {' P
本想配些插图说明问题,但是,CSDN的文章里放图片我还没用过。以后再试吧!实践证明,本程序算法的适应性极强。但是,对于点正好落在多边形边上的极端情形,有可能得出2种不同的结果。 |
|