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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。8 o( f% d( _" @0 ]2 e6 `9 l
3 d0 k8 k1 M: N
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。

　　首先定义点结构如下：
% Q  P  z" G, p( k6 o5 r3 T7 u1 K
以下是引用片段：) T0 F5 H" e# w* o) F: t
　　/* Vertex structure */ 2 P0 A6 D4 |3 T6 C/ I
　　typedef struct
　　{
　　double x, y; ( w1 w& Z8 x* E! Y: O. g+ `
　　} vertex_t;

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

以下是引用片段：% k$ `0 E' F. d! i- q1 s+ j2 {; d
　　/* Vertex list structure – polygon */
　　typedef struct
　　{
　　int num_vertices; /* Number of vertices in list */ 9 J' ?* A/ `! U! E) N' K9 P+ i0 u
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t; + y8 ^7 d2 [& _8 m6 w
2 C# M- m2 C. `6 V/ u; T' n; M

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

以下是引用片段：
　　/* bounding rectangle type */
　　typedef struct , }5 I) ?+ E7 |# |
　　{ ) V; o- [: A" M, R7 a* S
　　double min_x, min_y, max_x, max_y; 5 m5 o6 T+ O! j: i, x: @
　　} rect_t; / P. }2 G* D: h9 `" i' h  W% ]
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ ( J$ [8 g/ p3 C
　　rect_t* rc /* out extent*/ ) ) n+ d  b" t! g- r$ i# j/ V  q; [
　　{
　　int i; 7 p; T: z; h0 O# Q
　　if (np > 0){ ) j# C/ ~, p( x) Q
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; # L* w- J5 M/ `" o- G& V
　　}else{ 1 n. T+ N+ d' J) j5 N5 \
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
　　} 7 G; z5 L  _; h5 D  N3 M% f
　　for(i=1; i
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x; ' K% e7 r0 ~$ R6 }* x
　　if(vl.y < rc->min_y) rc->min_y = vl.y; 3 [# ]# q. b( F# f, Z" Z, ]6 [
　　if(vl.x > rc->max_x) rc->max_x = vl.x;
: c3 l6 a! y& a　　if(vl.y > rc->max_y) rc->max_y = vl.y;
) |4 w; M2 `5 Q　　}   N( L( N* O0 u5 U. |+ I# a! B
　　}
/ }. P7 E2 y/ ]% T* _6 i
6 Z, P) v" W8 u; p3 z# n
5 |0 I+ v5 a! A3 x: e* t) z　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。% J0 m9 l2 H8 V* ~' s& o. A

% Y' U, i* M1 C8 P7 ~& `3 U5 z1 H/ D　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
4 H. \) C) z9 c; n6 T
% R! j. G8 u; T3 p0 X% W, ~　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;0 Y7 P! b! E9 q  T+ K; Q. k

/ N( D& |7 C* h6 Y+ q4 l　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
. \1 P# o2 C- \7 J0 f9 _- Q% V
; M1 [. E! Y" ?  [  U0 @( P以下是引用片段：3 K2 j6 G" e$ f+ j5 [* d
　　/* p, q is on the same of line l */ 9 l" \" L6 D& k
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
7 I0 N1 s' I, U0 S( n. u0 f　　const vertex_t* p,
) J3 ?0 c) g& g, v　　const vertex_t* q)
2 M3 J% q* W1 _- ]' w　　{
, ]* j/ x( J# S- o& p　　double dx = l_end->x - l_start->x;
9 s) G: O0 q8 H. m# g! r　　double dy = l_end->y - l_start->y; 0 S0 g% o# f- r! X6 A3 ^- m
　　double dx1= p->x - l_start->x;
  n5 j+ n) N2 e) Z: G' v& Q- ~, m　　double dy1= p->y - l_start->y; , d, T2 x$ u% G0 l6 v, {: r
　　double dx2= q->x - l_end->x; 0 d( s/ g, w+ U, y# [& O
　　double dy2= q->y - l_end->y; / B- q5 o9 S& \& ~+ \
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
( r/ |: n1 u) {  r8 x& W" r6 k　　}
6 G$ S" S- q/ k　　/* 2 line segments (s1, s2) are intersect? */   u" E$ {& A; s3 b9 v
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
4 O, m: w8 a- {　　const vertex_t* s2_start, const vertex_t* s2_end) $ M" ~  ^/ B$ E1 s
　　{
9 s. d- h4 _. p　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
. ?8 d8 H8 v( e, U4 g5 k6 C, X　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; ( c8 v9 b9 n4 u- R. q2 H
　　} 6 E; J2 |4 P* a7 m) F

( {. V+ u( H+ ]5 @- a- R/ V; _! e+ W6 n' k( ^
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：( o5 Y5 M1 F8 e# a
+ p5 n) X! \$ f' _, N7 H; E
以下是引用片段：
+ g. l; c% ]; h　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
8 q6 q1 l2 {/ f　　const vertex_t* v) 6 K/ r1 S0 P9 I) G& @7 s' ~" m
　　{   {* Q6 [/ y4 x0 N
　　int i, j, k1, k2, c;   S# Z5 L: ^+ V' e6 n- ?7 b- h* K
　　rect_t rc; $ j* }; p& E" o+ Y; }
　　vertex_t w; - D) o7 e2 f, {" F! F: k2 b
　　if (np < 3)
' r3 M1 q! w' V　　return 0; : ~1 t9 h& r+ M' k3 W* x8 X
　　vertices_get_extent(vl, np, &rc);
9 `  v, N. C  t* m$ `! H　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) + q, c5 ^9 E! q2 G
　　return 0; # i* G* _4 V8 g
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ " p5 Y5 k$ o6 N% K4 a" n; O
　　w.x = rc.max_x + DBL_EPSILON;
7 Y0 J6 Z" \) Y$ _7 I, z! K- g　　w.y = v->y; ! `1 i/ d( c& o) B1 m7 \
　　c = 0; /* Intersection points counter */
+ D) [5 o$ u6 ^8 D# ^: R　　for(i=0; i
8 u( M: ^& M7 ^! E; W　　{
' U# O* {$ E0 {2 V　　j = (i+1) % np;
) y# ^& \# r) r8 D% [+ u' {　　if(is_intersect(vl+i, vl+j, v, &w))
9 h5 y" j0 |  T" ~/ D1 r　　{   _$ V& ?: M9 t: R5 S8 |
　　C++; 4 S8 n, B3 f  g" u% n% W
　　} % R8 X- Q% _6 P
　　else if(vl.y==w.y) ! w1 r$ C% N& D8 [( ]2 F4 R9 D% ~
　　{
% H6 L7 d/ J( C: ]; Y0 G! q* l6 y6 U3 N　　k1 = (np+i-1)%np;
+ X9 l* ]  D6 Y# |3 A: L　　while(k1!=i && vl[k1].y==w.y) 1 v; n7 j* \" P$ u8 t" V/ V3 H
　　k1 = (np+k1-1)%np;
3 ~* I$ K; p2 V: B$ o　　k2 = (i+1)%np; 7 F8 F) v6 b! |
　　while(k2!=i && vl[k2].y==w.y) , G# C2 U; B1 o& Q- \
　　k2 = (k2+1)%np; 2 W  e" _; d  {4 b% f+ q) X; q
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
1 a7 y6 T( o8 J; b3 K8 L4 p+ Y　　C++; " j# Q' {( p2 m/ w. s2 |0 F
　　if(k2 <= i) ) b! h6 d: y9 j/ `3 c
　　break; 0 \- `9 S. l# o! j( ~8 W8 i, @4 N
　　i = k2;
- Z5 x* D0 A5 }! T! x　　} 3 s/ M0 u3 a4 N/ o3 y- `
　　}
* f0 v7 ?6 S" Y　　return c%2; ) w7 c/ V+ M8 Z
　　}
- h* L! \, p: u" I: U2 d& @5 ^- ]+ x7 Y1 N
3 h# X: }7 }2 l* y$ ?
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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