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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。

　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。; S# x* y3 B! C, l$ z. m& T
, h; E8 m5 b2 }9 R
　　首先定义点结构如下：
' u0 e8 ?2 v. K+ J4 g
以下是引用片段：2 {: C6 m) k& z& s: ]: K8 L2 t
　　/* Vertex structure */ / ]4 l4 |  u$ G, ^; s+ s/ z+ o
　　typedef struct
　　{
　　double x, y; 2 {4 o% M& g4 M9 J0 I: u+ k2 Z
　　} vertex_t;

4 _* i! j& B% [  K5 N* \& C9 o8 P
　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：

以下是引用片段：- u4 D* s; t- i  p
　　/* Vertex list structure – polygon */
　　typedef struct
　　{
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t;

- B8 {# z9 }; ^! n5 B1 G
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：

以下是引用片段：
　　/* bounding rectangle type */ / k# _5 m2 a5 ^6 ~# o: f
　　typedef struct 2 }8 }( v) j, x% B, y% V9 s
　　{
　　double min_x, min_y, max_x, max_y;
　　} rect_t;
　　/* gets extent of vertices */ 8 `9 Z( ~1 F+ U8 ~/ |' }
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ $ N4 u8 V; S' h" M5 ]5 t9 T
　　rect_t* rc /* out extent*/ )
　　{
　　int i;
　　if (np > 0){ ) d. y" W% w; O' m7 R
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; / y& J# V9 E; G. i. v3 j3 U
　　}else{ . P2 l3 h( J8 _
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ $ \4 v4 R7 C* k. y0 u
　　}
　　for(i=1; i  ( T, p0 ?; J$ {' q  s" K4 O( w- V
　　{ # \7 e7 f( z# M: T2 h
　　if(vl.x < rc->min_x) rc->min_x = vl.x; , K; d% y% z9 J3 s  \. A
　　if(vl.y < rc->min_y) rc->min_y = vl.y; + l8 F" s5 D6 |, H: D, M: w; g; S
　　if(vl.x > rc->max_x) rc->max_x = vl.x;
& e1 `3 \$ t0 R/ d　　if(vl.y > rc->max_y) rc->max_y = vl.y; 7 n  x3 J8 V9 l% n- z! |
　　} # R& V3 n* L3 Z# \' w% f! R
　　} ) V/ L* c0 R2 z! m

! p8 k! r& X& M$ F9 g2 L( m9 h- f
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。: Z1 x3 f1 Z  U

# a5 z5 q7 M1 J! o/ y) o6 J　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：. _6 D% U8 T3 ^' n5 S
6 g& C( w7 E3 b$ B- ?, g( g
　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
& Q2 \5 r5 [7 {$ q7 g2 L( J8 n$ K% [$ A5 x* H! E6 k
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;3 p0 R% m* C/ I2 i! x

( C+ x7 x) j2 J以下是引用片段：2 r' n. S& t# v- g
　　/* p, q is on the same of line l */ 0 [7 A! S9 M  m* o- k
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ 2 W( B% U: b# l0 l7 N
　　const vertex_t* p,
) S7 x. ~1 T  }' @" z( K7 \& a　　const vertex_t* q)
1 e/ F* x1 y) _* k# Y　　{ + y/ ^7 b; A' S7 \1 {2 d2 @4 C
　　double dx = l_end->x - l_start->x;   J2 m2 V* W: q) w, H8 h5 s9 K
　　double dy = l_end->y - l_start->y; 9 z7 ?* a2 H+ i/ D9 O
　　double dx1= p->x - l_start->x; ! t3 e- x4 B: s
　　double dy1= p->y - l_start->y;
  h9 ~+ f' s& N8 G2 `, }　　double dx2= q->x - l_end->x;
: m- w5 Q' e" ^% Z6 g　　double dy2= q->y - l_end->y; $ t7 A, u* \7 @- O4 I# p4 S% e
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
2 c7 q3 l  G$ ]) r: o　　}
& ~& Z6 w1 B2 ]# H) H; D% V; s$ z　　/* 2 line segments (s1, s2) are intersect? */ + I, W& a7 H' U% s1 O4 J
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, 4 s; V9 m: j% D# H
　　const vertex_t* s2_start, const vertex_t* s2_end)
7 s# j0 u) p0 b9 Q, t　　{ 1 |# O1 u  y; X7 C& L* a
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
8 b& w4 y3 i0 ]- }, Z　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
* |% t2 P# H% l2 \& c　　}
& c( C' r! f5 n( t( w4 b4 J- x! J! {# \* p0 V9 E3 J
8 _& L4 M4 G- n/ ?# w$ W
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：( z7 _5 {: T- ~! o7 }: I' t
3 X  O) T* r0 d% e1 B4 `
以下是引用片段：
/ o% X1 R7 ^  ?; v$ h2 b% \* |1 u/ e　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
9 `/ _/ i3 Z2 G. @1 i2 @" z8 |; `　　const vertex_t* v)
. E6 o( P& c( N　　{ 2 f: q% w3 c! |( l
　　int i, j, k1, k2, c; 3 @2 f# z2 I. L
　　rect_t rc;
. S/ U) l; ]7 Y+ H8 g　　vertex_t w;
/ k. f) }( K# u% j8 X7 t　　if (np < 3) ! r  a1 a5 f1 p: B7 v0 N
　　return 0; " W! x9 ?# m7 B
　　vertices_get_extent(vl, np, &rc);
8 d% V( Q+ e! y9 v　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) 5 f& |( s" d/ B1 N
　　return 0;
4 l: K& U8 e: Y- V　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
' u/ I( i8 o1 Q( U9 t! ]$ ~- z　　w.x = rc.max_x + DBL_EPSILON;
. _0 p# W# c: Z1 N& P% J　　w.y = v->y;
. d& x3 o! P( b* C　　c = 0; /* Intersection points counter */ ! u& l. ^2 T" m+ v! w! y" |$ x2 H
　　for(i=0; i
6 H0 h- r" J6 Y& k' H1 G　　{
& i. e2 d/ \' @1 n　　j = (i+1) % np; ! O1 a: E# s# A, f
　　if(is_intersect(vl+i, vl+j, v, &w)) % y  [( U. l7 b% ?
　　{ ; D  e" F% M9 h: D) [# `8 b
　　C++;
# z& j7 _: y7 @. C& L6 A　　}
! K$ k' A# V1 [7 M8 ~$ S　　else if(vl.y==w.y) ) K8 ?' ]9 T3 e- w. n# T0 A
　　{
( ]8 l) {6 t- w( v5 S　　k1 = (np+i-1)%np; & k9 ~/ J; c9 q0 Q
　　while(k1!=i && vl[k1].y==w.y)
/ }, }0 E' @/ g8 o$ K, m7 u2 ?, e0 D　　k1 = (np+k1-1)%np;
6 N9 k1 J1 R* a, W3 S$ t7 M　　k2 = (i+1)%np; 5 |6 |6 ~0 M, W+ T4 R& \
　　while(k2!=i && vl[k2].y==w.y)   e* O7 N' N7 n5 c3 x
　　k2 = (k2+1)%np;
/ o% X( H& J" x5 G* g) s　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) ( n8 [* ~9 {  L  ^7 g
　　C++;
# z; D  d6 u2 a! |& j: `# v　　if(k2 <= i) - E6 B4 h3 s, e- c* c
　　break;
9 B3 l5 ]. @" E. z$ u: }　　i = k2; : n3 i0 t6 i4 K( b/ v2 P' n
　　} 1 W' s, ?; K; N$ v. v- I* V
　　} % T0 K' {% Y& c2 e# [
　　return c%2;
" j- Z$ V( P4 h* N6 l　　} / m- M' J6 P* X( v. L8 s. k/ L

+ s8 U# E: l) c8 J, [
: A5 V, p" l; r/ h1 X　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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