标题: C语言中显示 点在多边形内 算法 [打印本页]

---

作者: zw2004    时间: 2008-1-21 17:20     标题: C语言中显示 点在多边形内 算法

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。1 L9 m, f, A6 P3 n' n2 Y
4 L' l6 R% j6 ]# b
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。( A7 z5 w& y- I( L  b

. |7 ~( Y" A+ @　　首先定义点结构如下：. p5 r2 z" V+ Z; `  P( ~9 |0 g& s8 M

5 I6 N9 v  H* w) \% B; i以下是引用片段：% |  Q4 d$ G) a+ j0 `
　　/* Vertex structure */
5 m$ X& p8 ^$ I4 O5 Q5 r2 k　　typedef struct   o7 O% H$ N! {8 w  P
　　{
% s+ [' L. ~3 F' E) R# L　　double x, y;
9 C- k8 Z  _: L, V　　} vertex_t; 0 i+ P1 f* z5 {" q  V
" U9 i. n9 Y/ o
4 J, Q" c9 I& P3 X! {: [) C1 A+ t
　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：% ?' ~1 b5 i2 C" A  [- o% S# `3 s4 \

9 W! o8 Q) I! ]7 r: `以下是引用片段：
3 t6 y& W  k% x/ @; W: y5 V* u　　/* Vertex list structure – polygon */ $ J& ?8 z4 M% ~+ F! S+ q. I% m
　　typedef struct . U" B2 e! h+ s
　　{
5 O$ J* b& c" W5 T7 K( ^0 o3 f　　int num_vertices; /* Number of vertices in list */ # S( t( N$ T* s# t, `% S) T: h7 v
　　vertex_t *vertex; /* Vertex array pointer */
* k& C1 `/ f, I- ]; s( t# Y  s) h6 X　　} vertexlist_t; * y1 V# P' g9 |6 n$ u9 G2 W( Z4 l

$ H, T' [9 b2 Y5 M( W* c3 M; F' g5 t" {. p- f: K! l/ u
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：# |& L3 e, d2 t
; z2 J! U+ U& z0 R9 o# k
以下是引用片段：3 _* I! g9 l0 _7 U
　　/* bounding rectangle type */
( x! C9 }+ L+ C5 H" v: Z' W　　typedef struct 6 K) b4 h, _6 R- z  T1 L# x
　　{ ' C# P" u# D1 L1 N  W
　　double min_x, min_y, max_x, max_y;
( f3 D5 D$ j9 P' e　　} rect_t; ' R7 y. y4 V5 J; t4 m
　　/* gets extent of vertices */
, Y  C* L1 v! F0 J* h9 p　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
. Z9 r2 z: H/ S4 w　　rect_t* rc /* out extent*/ )
) e5 w+ [/ q# C$ e6 X　　{ " W2 ~2 K. w9 ~5 |' J
　　int i; $ T. N- j: G: z; j1 v
　　if (np > 0){
! b' C# `, q7 h& P, w- w  u* N( i, B　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; : y! K& F& Z" S( }' r0 z' P9 p
　　}else{
+ D3 s$ @8 ^! d8 e3 c　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ ' T. K0 @/ ~* o" h, J+ L% U6 `4 ?
　　}
6 I4 n) _5 Y- ]0 |) i　　for(i=1; i  
4 C, g6 {+ `4 p+ n# v% z: k　　{ ! Q7 X; W6 L5 w: C: V# @
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
/ z% R6 H' ]* y) H2 y- x1 ~　　if(vl.y < rc->min_y) rc->min_y = vl.y; 4 B' c. y. V& r$ F# n+ ~# u
　　if(vl.x > rc->max_x) rc->max_x = vl.x; - b3 S7 ^5 A3 `4 B6 X0 t
　　if(vl.y > rc->max_y) rc->max_y = vl.y; ! d+ n, l  ?; A# d" E
　　} # F- I  |- c2 l: L- h% {
　　}
$ ]( \0 q6 Q1 b$ ^; @! |6 t1 [
8 v2 E; \8 E3 l& e. G' X
- }' X; Q" P/ O( @+ M( ?　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。  O7 j9 L; ^5 P1 T  b8 B

& r% _3 B8 O8 p$ _, R1 J% c* h　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
8 s4 w" e: ~: A7 d) R
& v" b, c& a5 N; Y9 j　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;& `9 J& o' H( j- y. C

, K! Y( k- z/ T　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
) J" T; D1 i% U% l8 j8 A- C3 k: Z' V) w- q+ Q5 ~
以下是引用片段：7 {: k8 C7 Y: P; \# b2 Z
　　/* p, q is on the same of line l */
( Z4 j* J, X% F& ~/ z" D- T  j　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ % K" G! o* y" M
　　const vertex_t* p,
* V" e, k# n" l4 ?　　const vertex_t* q) 7 ]/ u: @5 D# n+ R( M
　　{
0 Z4 V7 {. O7 u( C& t　　double dx = l_end->x - l_start->x; / i/ X) G, ^% J- }4 p
　　double dy = l_end->y - l_start->y; 1 E# n  A9 ?8 W- L6 S% g
　　double dx1= p->x - l_start->x; 4 R1 n* Z* q5 |8 o5 c8 ?
　　double dy1= p->y - l_start->y;
  ^3 a. e( ?' C: g) G2 h/ _4 }2 n　　double dx2= q->x - l_end->x; 6 f$ Y7 D3 _6 ?: m) [5 y
　　double dy2= q->y - l_end->y; * D0 h% L1 s+ {! O) A
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
' M/ l( q8 Q* n5 Q　　}
$ ]  J$ C7 W$ T/ A6 M& \' c　　/* 2 line segments (s1, s2) are intersect? */
( m  b8 ]$ I) y5 y　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, & d. a/ b; Y7 p) A! P
　　const vertex_t* s2_start, const vertex_t* s2_end)
4 A" B3 V/ v0 a4 s7 Z: d- a　　{
& y: D  w! H8 I" L5 U* E　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
1 U8 B4 [9 @$ x/ l) Y4 s　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
" B0 X( ]# X# z　　}
, K! f4 W- s/ t& x9 B! ]# F. S! C7 |" q5 s% z8 z' [
% X9 i4 D7 ?( j: f: I* k' b
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
$ M: c  D" W8 u- {+ N( k" `- O
7 a, `7 |( g& U5 Z以下是引用片段：
& q8 e$ D0 k1 j1 h　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ ! W6 t5 D0 B+ {7 Z( D
　　const vertex_t* v)
1 _* A- d2 @8 b0 [　　{ ) |/ v) f/ }1 h+ }! ~+ F" y
　　int i, j, k1, k2, c;
$ B5 v" x( ~, r3 J% t5 h' a　　rect_t rc;
9 {' M0 t1 T' t# q% L5 a　　vertex_t w; 9 B* T" o8 Y0 j) V: B7 u
　　if (np < 3)
$ G& @, D" T7 f7 a# @, s　　return 0;
  o  M7 h3 n; X* Q3 B　　vertices_get_extent(vl, np, &rc);
! Q% g7 R* F3 R　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
- M! u* p5 c/ C* S; R/ w　　return 0;
& \" F8 ~* H7 ]　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ * @9 u' {% K. Q0 I4 _4 j, l
　　w.x = rc.max_x + DBL_EPSILON; 2 `: O2 d* t1 [5 f4 v9 p* F  Z
　　w.y = v->y;
6 d' Y: R) k) T5 L% u　　c = 0; /* Intersection points counter */
& M0 v' i9 d* y9 j: Y+ @　　for(i=0; i  
+ U! Y: L3 ?7 s  B6 d　　{ " ~: F1 p* A0 W$ \
　　j = (i+1) % np; + z" v1 r. G, t1 ^
　　if(is_intersect(vl+i, vl+j, v, &w))
. t: B. w- l7 o* s* I# l9 t8 P　　{
' |  n7 O6 S, y" @  S5 S/ O　　C++;
; J! ^) W2 C- j( i  I# ~- m　　}
4 f' z3 {( ~4 {　　else if(vl.y==w.y)
% Y9 O6 {2 p/ A; ?" I0 x. K5 B. N$ _　　{ 8 H. N7 V0 d9 H( k  i5 {
　　k1 = (np+i-1)%np; & f' b! E) F; \3 b" Q" B! e7 I
　　while(k1!=i && vl[k1].y==w.y) : a9 u/ o9 C. [( l
　　k1 = (np+k1-1)%np; ( r  O% A" E6 A# ]. @  d
　　k2 = (i+1)%np; 1 Z! q, j2 v: X. R) U0 @! F3 b
　　while(k2!=i && vl[k2].y==w.y)
9 i9 V4 X) e# l. j2 g0 `- u# P　　k2 = (k2+1)%np; ( \) S0 f7 G: f2 m
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
6 q5 j; z* l! }: i( E9 n6 D* R　　C++; & G: ]. S6 u+ `& E5 ^7 r$ @; n
　　if(k2 <= i)   K" N" u, }6 j) p
　　break; " ^8 U" K$ c) W$ Q7 M3 T
　　i = k2; + `1 F6 N$ w6 g; |9 A/ t* K* [
　　}
* N5 u# T' ~0 B0 R7 O9 N　　}
: I+ q. P5 ~8 T6 i. G. Y　　return c%2; $ \2 G! k' E9 v: m% r) V+ g
　　} 6 ~3 t) F$ p8 `% M+ H" ?/ w

% N/ h4 \1 D/ |3 W( m
* {/ x, z% `+ l* t0 ?! j+ X　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

---

欢迎光临 捌玖网络工作室 (http://www.89w.org/)

Powered by Discuz! 7.2