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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。
3 y0 I; v& I5 J; [! f  \
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。7 l3 o% \* I2 C: Z1 x
! V5 y9 g; y+ A6 a6 P) F. D7 _  T
　　首先定义点结构如下：
$ A. R/ D+ g  B4 V0 f, X
以下是引用片段：3 U0 O5 I2 U$ F" |- X
　　/* Vertex structure */
　　typedef struct % ?9 J+ P; g3 C- c( S
　　{
　　double x, y;
　　} vertex_t;

　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：# A' _) P0 Q) V2 @5 S: t3 `

以下是引用片段：- F4 S8 @, v1 v+ G4 X
　　/* Vertex list structure – polygon */
　　typedef struct / w- ?) \6 e8 J4 ~7 K: Z
　　{ 4 B# Q" D7 U* `7 S# j/ }, \8 u7 J" T
　　int num_vertices; /* Number of vertices in list */ 5 j  C* L( m4 Y: D" L4 a! K
　　vertex_t *vertex; /* Vertex array pointer */ 4 R# u" I+ k" E# H! Z9 w
　　} vertexlist_t;

　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：; v  k% ?  Y5 g

以下是引用片段：
　　/* bounding rectangle type */
　　typedef struct   w. d2 T- |2 l1 U
　　{ * g  b7 V9 U2 a& H2 g* x
　　double min_x, min_y, max_x, max_y; 4 Q( S  S# }: m! O2 D% c5 ?, t
　　} rect_t; 4 t9 t" }* M. s; E- j! f- d/ ?: ^( V* Q
　　/* gets extent of vertices */ ) X4 M+ m9 g) T2 |  t7 D2 d
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ ! H2 _4 W( _9 y% n" H+ A/ v
　　rect_t* rc /* out extent*/ )
　　{ * V0 f* R# W: G( V! J4 v
　　int i;
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
　　}else{ : B& t% }9 t  f) L) m6 `- U* e
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ % E$ S" F% b3 d' B4 `
　　}
　　for(i=1; i
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
# B0 @4 S, R6 g% C7 Z　　if(vl.y < rc->min_y) rc->min_y = vl.y; : ]  N  V; N3 T6 U, M6 y4 r
　　if(vl.x > rc->max_x) rc->max_x = vl.x;   f2 m+ Q; Q1 I, s" d  r- T* E% H
　　if(vl.y > rc->max_y) rc->max_y = vl.y;
3 w" H  V5 @! e  u7 V3 y" v- [　　} / x6 l* U0 g0 Z! Q% U
　　} " i0 s+ ^+ F9 _6 i  p
8 d! A: u1 R& m4 ^/ h: }+ ^
. f6 K7 ^, b0 P" S
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。% `+ N1 r* Y% H$ X- ^

. r7 G$ V$ V* R* ~　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：( {# p. U# Y" J0 a

' F* [& g* Z/ v) P　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
- d5 G  S& d' y2 k- ^" V' ?; i7 _) F% ]" R0 I* K7 q$ V
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
4 x" k+ R  d0 P5 ?1 W  Y5 P7 Q! R
7 n+ h0 s1 R0 n' f' T以下是引用片段：0 d. _' G% {9 K% t" N0 @
　　/* p, q is on the same of line l */ 3 F$ T* Q  ?$ n+ ?
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ 1 k5 n2 k  r; O! X! e% i
　　const vertex_t* p, 1 p/ O# ~6 F7 \  _
　　const vertex_t* q) ( @+ W' x6 t) }+ B1 W* Q; J
　　{
; }4 M. R0 L7 y7 z: r/ F' m　　double dx = l_end->x - l_start->x;
; X& @; P5 R2 g! ~) h  k& P　　double dy = l_end->y - l_start->y;
: [2 \& b; ^# u& {& R　　double dx1= p->x - l_start->x;
% a+ Y" d% S) n& k) M　　double dy1= p->y - l_start->y;
- B$ K1 A0 a+ H5 M- N* r　　double dx2= q->x - l_end->x;
% M. T8 z  l" Y. N9 `! x　　double dy2= q->y - l_end->y; 3 D) B6 O4 q7 t# X5 ^
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); ! ?: W0 \# x1 B
　　}
# `  z1 n, l0 p0 y　　/* 2 line segments (s1, s2) are intersect? */ 4 W3 ^& b) Z/ j5 g& i
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
( s& K8 R9 V1 K5 J5 v　　const vertex_t* s2_start, const vertex_t* s2_end)
7 g; u# W& Q! ^: S- ~7 L# w* |% [　　{ 9 S  U, _" ~( f
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
* b! P5 Z% a% Y* d6 k　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; ) m( q' O3 C) J+ p( `3 n
　　}
! U0 ?/ a1 O! Z0 o' b/ K6 o  H: F. V0 n+ ~: ~3 m
9 p. R1 `9 @8 g) T8 @6 T$ ^
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：5 W) w4 D: R8 t# `

9 T! f$ N2 s  q5 G- p3 `以下是引用片段：  p& A+ P+ k$ u' P9 Z& D, |
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ 5 K7 c' d1 M5 q, f& w* k% i
　　const vertex_t* v)
9 a# }" a. W2 T& H  m　　{
+ v7 u8 H9 ?3 n4 T- W9 d　　int i, j, k1, k2, c; , ~+ K9 C) r7 n  M
　　rect_t rc; 9 a, m* o9 }0 K3 W+ u
　　vertex_t w; ' p0 _, H8 j7 I) H8 J
　　if (np < 3) 7 j+ N$ c$ q8 Z4 i4 J) A
　　return 0;
7 n# [+ T& w8 q7 _" A% T　　vertices_get_extent(vl, np, &rc);
  s. W" |  e) x" q/ R) y　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) $ ^- t3 J5 G, ]+ k3 v; a; s! g* p7 s
　　return 0;
0 m& g: }7 N* F3 j　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
5 v9 c. h5 K( {5 }" v　　w.x = rc.max_x + DBL_EPSILON; 9 @8 P6 a7 \! O; _+ B
　　w.y = v->y;
( G* e+ A; g: E' Q: f　　c = 0; /* Intersection points counter */ 2 }, ]0 q) ^* r' M8 x# M
　　for(i=0; i
" |2 X# r# {( h' |　　{   g) P" K, c) P' r. P1 |- z% M$ {. K
　　j = (i+1) % np; 6 E* ~0 S1 e! I8 H
　　if(is_intersect(vl+i, vl+j, v, &w))   `0 C0 G0 J9 C2 i. h
　　{
: |/ x, }  O+ r5 }0 G  ?　　C++;
" @% y$ D4 Z: I7 ?" ?0 b6 s　　}
8 x7 _$ u8 u" U& y+ _　　else if(vl.y==w.y)
; K! R8 C9 h& A7 D　　{
+ S2 I1 k" @# B: S0 y　　k1 = (np+i-1)%np; 9 u5 ]: {5 R. L0 \% u& t$ \- Q# l
　　while(k1!=i && vl[k1].y==w.y)   M8 ~( Q( T0 T# s1 B, ^
　　k1 = (np+k1-1)%np;
0 N$ ?3 a6 d! N& v　　k2 = (i+1)%np; * N  {) k$ o. Y; M) f
　　while(k2!=i && vl[k2].y==w.y)
+ V9 e8 z, C" I% i　　k2 = (k2+1)%np;
9 o9 b: v% I7 a' j# u& r- c  |　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
9 D3 e9 Q+ }- B( H# t3 }7 A7 s' I　　C++; 3 N' E- w% j6 S' F
　　if(k2 <= i) * F, T. q6 n6 `. C4 `6 u' L
　　break; 4 Z7 ?! b$ F6 ~7 g# }6 {6 V! N
　　i = k2; 9 X% q9 c* K. Q' n. R
　　}   N9 D# S& U2 w/ D; T% r9 t2 m
　　}
; p9 D- K) X. o6 s　　return c%2; 8 U6 T5 Z4 f0 Q+ o8 e; M& h5 X
　　} : [2 @- m- r0 V' W9 i
: c& C* Q) g3 |% \2 L* d+ y" s1 {

  G- ?; k- J$ O0 l　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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