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

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

　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。
3 |3 y3 b. Z+ B) X
　　首先定义点结构如下：

以下是引用片段：
　　/* Vertex structure */ 7 Q- e3 R  v4 p- w# _* l. ^
　　typedef struct
　　{ # L5 C: C. o. t
　　double x, y; 1 B# [. X5 `+ j# h6 ^, K: _
　　} vertex_t; % e" }; C6 H, E/ W, M% i, j
6 A2 s# \8 @9 v2 q2 F0 v6 r" f

　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：
8 \( `  l) d, F! c: a+ Z
以下是引用片段：
　　/* Vertex list structure – polygon */
　　typedef struct ( A( \3 K! q- l; k" o
　　{ 1 M' K* M$ j. U7 C8 h8 ~
　　int num_vertices; /* Number of vertices in list */   c% S/ e; D& W" t( a$ O! ?, B% k
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t;
4 a5 ^9 M! R8 l
. \8 T# S) i3 X
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：) [2 m2 o7 P& ]/ p% k* }

以下是引用片段：( ], _- [/ I( ?- q
　　/* bounding rectangle type */ 0 h, F" _  _* s5 D
　　typedef struct 6 }4 F1 a8 \, `) ~4 y5 Q; z
　　{ ; @, T3 C5 n; C+ v2 I
　　double min_x, min_y, max_x, max_y;
　　} rect_t; 5 m. Q) W* Q/ R
　　/* gets extent of vertices */ 9 S5 l3 {! }" g0 f' i$ ~" W1 R
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ ) 0 X$ B. k% W) I& m2 D$ i7 p! l6 [
　　{
　　int i;
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; & C6 ]) Y  [& s3 G  e2 R! k
　　}else{ $ Y7 q$ n! T- b; [
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
　　}
　　for(i=1; i
　　{ 7 [* ?- H# k2 {+ U& T" {
　　if(vl.x < rc->min_x) rc->min_x = vl.x; ' J; x3 w, z" v$ s/ Q
　　if(vl.y < rc->min_y) rc->min_y = vl.y;
9 `& Y! @! h3 ]8 d　　if(vl.x > rc->max_x) rc->max_x = vl.x; 0 j3 P! M. l. f$ E8 x) I
　　if(vl.y > rc->max_y) rc->max_y = vl.y; 2 W2 i# B$ H+ @% w- z4 r
　　} * ^/ z8 @$ R9 L" G
　　}
3 t# \4 v: p3 N3 w, o9 h
: O5 V' ^+ `) p* E" I, |% G
- R+ Q9 J6 i: w% `/ [" Z$ t4 k　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。- Y( X9 R& ?, ]7 B& M# r# u1 ]
  \  h3 C# m" z1 {# Q( V0 U' K
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
) C" b8 Q0 c/ z& x6 r
! D. `  [$ E/ l6 C0 ~　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
" {! B* R/ H, Y6 t1 S0 H
! l$ r) }3 A# t- C. E　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
! u) E3 ~7 u) o3 U) S3 V/ @0 k4 R9 `/ p
以下是引用片段：* J7 g) x* Y1 _/ v" Y& U
　　/* p, q is on the same of line l */ ( }, j8 ~( _3 R0 ]# i
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ & b1 A+ V$ B2 l
　　const vertex_t* p,
5 V. E3 _$ b; T; W# H/ S3 L　　const vertex_t* q)
3 v8 k4 s& [: u  {3 W　　{
5 b. @* E% I- j# j: n& s　　double dx = l_end->x - l_start->x; * d! {" j$ M* T3 ^4 m- K
　　double dy = l_end->y - l_start->y; 0 |" [+ z2 C, Z
　　double dx1= p->x - l_start->x;
8 O/ T* H! r$ l% l3 {　　double dy1= p->y - l_start->y;
% k& c+ u( L) t- d　　double dx2= q->x - l_end->x; 2 I: _7 R$ Z) y- d3 d
　　double dy2= q->y - l_end->y;
% j/ l5 |+ p9 y" b3 D7 J1 x　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); - f# @1 ]- V  n9 ]( y
　　} ' k# `6 U& a1 k! t" q1 w: E" q
　　/* 2 line segments (s1, s2) are intersect? */   N. O; c( h5 f) E! Q1 Y
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, 4 D8 ?  K  Z) r7 n& G3 N9 q; Y! C
　　const vertex_t* s2_start, const vertex_t* s2_end)
" M# i: {% a! m) j9 L9 ]0 z5 i　　{
( I9 s( z- {  T! M　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
. q# e5 ~/ }. a! A6 @/ k　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
2 x8 M- p8 t7 ^3 x( E　　} $ p- M0 D7 d( p" a

& S$ O: L' p6 U" y
' k  A8 q4 W8 l' H. P6 X8 h% O　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：% A0 Y+ }$ I; Q! ]/ g+ o

, c8 W! \( H& i3 i  [" R/ _7 o0 V9 v以下是引用片段：8 u+ ^, Z5 J0 j5 |
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
- R+ W' ^1 M+ a" r　　const vertex_t* v) 2 v: P4 W( q( g# X' u$ [
　　{   P4 C. G6 j6 i4 [( ^0 Z4 Y
　　int i, j, k1, k2, c;
6 x/ E& `  j" b  F; J8 L　　rect_t rc;
! L' ^& s1 Y. ^　　vertex_t w; ! m' Y. v( X/ {- ~# _8 k+ `$ i
　　if (np < 3)
' g5 u0 p6 Y, t# b' \( u: h# L% C* j　　return 0;
+ I- D& ]7 B- m　　vertices_get_extent(vl, np, &rc); 1 f; [, X2 \6 O/ n& u1 B
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
/ z% s1 |% N  Z5 I8 ~　　return 0;
3 R+ D$ T" L* D1 M( E6 h　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ * V; Y7 y. O& ]& G# P0 P' Q9 i% Q
　　w.x = rc.max_x + DBL_EPSILON;
9 {7 d4 g3 D# q　　w.y = v->y; ( y; n* D2 Y+ V4 W; E1 q" _
　　c = 0; /* Intersection points counter */
" j% K2 ^0 }3 U1 m) e　　for(i=0; i
' h9 }, L8 Z% N& g+ f　　{ - \. ?, A$ y+ p2 ?# J
　　j = (i+1) % np; 7 k5 \6 B+ a/ X3 |
　　if(is_intersect(vl+i, vl+j, v, &w)) , U  l  k/ i( k* g7 V7 q
　　{
6 I# @7 f. M4 I9 C　　C++;
' U8 ~( ~( J3 z4 ~　　} 9 W3 E- s6 ]: O  X
　　else if(vl.y==w.y)
: {  M0 |0 k. z　　{
+ ^! D  {9 E5 T　　k1 = (np+i-1)%np;
) f1 B' {: Y& T, }　　while(k1!=i && vl[k1].y==w.y) " A5 j" L7 Q6 O. c. [
　　k1 = (np+k1-1)%np;
* u+ A9 R7 C' C* H! p　　k2 = (i+1)%np; * B  G$ o) N( t7 `9 l+ s
　　while(k2!=i && vl[k2].y==w.y) . h" U1 P# m+ z# m5 P9 l, G  T
　　k2 = (k2+1)%np; # i' D8 B) c# `6 N/ l0 G
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
5 ^9 M. t: i( g  T) h/ L　　C++; 4 s5 S3 H) F' i  g
　　if(k2 <= i) 9 j/ H3 K/ K- {: C
　　break; 7 c6 e8 @6 W% b/ f* \
　　i = k2;
5 L& f2 S9 D. O3 {4 k6 K　　}
. x: b4 W0 F. ?) u4 @3 _: h5 X  ]　　} 1 K: M+ t- v4 P3 t# n
　　return c%2; , B" y7 d# ^5 [1 k
　　} # w( w; f+ q8 o0 W( Q
# t. L% P. t9 G5 o- u7 ]# H

4 f! i3 }# U- r1 i- Y9 y+ b　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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