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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。4 q6 A1 o' o: a1 r) z  T
% B: T1 K+ ~, r  V9 p
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。) O3 O. z+ W$ H3 l. t$ k

　　首先定义点结构如下：+ R# L2 P9 ~$ e1 c6 ~' N
( w1 G! E! G$ l6 _$ O
以下是引用片段：
　　/* Vertex structure */
　　typedef struct
　　{ ) \* N# w1 d. R' e8 @6 @9 l# F% i
　　double x, y;
　　} vertex_t; # R3 W, D5 z* \& k
, `" N, J+ A$ |  @2 K* m; ]
7 D: X5 N/ l7 G8 o  L7 J" L
　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：% x5 ], d  `0 z
/ p5 N, v* n. G- p/ l; t1 W* [( h
以下是引用片段：8 X' N7 x& `1 x: t! Z4 t8 e: r
　　/* Vertex list structure – polygon */
　　typedef struct
　　{
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */ 4 J3 ~' h$ B1 j. G  n
　　} vertexlist_t; & [; c! O" G$ X0 N

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

以下是引用片段：
　　/* bounding rectangle type */
　　typedef struct
　　{ - h; |* H9 |4 w" k; k
　　double min_x, min_y, max_x, max_y; : l: J3 V/ |! Z* g8 e1 s
　　} rect_t;
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ )
　　{
　　int i;
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; 2 d) r# u# I0 j, T3 c
　　}else{
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ ( @; h5 `2 K% O
　　} ) g2 c3 Q; b" l% A8 s
　　for(i=1; i
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x; % C; k% U( J8 n9 F7 c2 D* Y& j
　　if(vl.y < rc->min_y) rc->min_y = vl.y; 1 ?( N" x# z5 O$ F% b. g$ D$ H
　　if(vl.x > rc->max_x) rc->max_x = vl.x;
7 x" E6 E# h6 Q% W& K* _　　if(vl.y > rc->max_y) rc->max_y = vl.y;
! r, \; s, w" k5 s6 q. ]　　}
8 L/ a+ k7 B% ?$ f　　} 0 Q1 C9 x: Z& {$ E
1 n) u. _% [) ?4 ?% Z- P6 ~4 P
  P# O4 \6 d. t  o8 d
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
1 k; m$ _9 A2 C# V+ {
2 @5 B( Z$ G. P- c( C6 [0 B　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：( E7 R# b9 T- u. T! }9 g! l4 W% y/ l

  y* x! g/ `! |　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
# ~9 n' n- O; ?
: K4 b6 u* `+ v* d　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;8 H( Z0 _$ y% _# }' h1 P
- J6 J1 t9 k) a
以下是引用片段：
# i) d+ A+ P6 h% p3 N' h( t; W　　/* p, q is on the same of line l */ ; P/ T, i  d4 E3 m: C3 d1 r
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
6 e4 z+ E" p' g2 M, h) z6 E' V: A　　const vertex_t* p,
9 u' G0 b2 p, ]( l5 P  X6 y1 u　　const vertex_t* q) ' h2 \# W4 d  b3 w$ Q/ ~* Y
　　{
9 V% g6 i0 B3 [6 i- J) h0 L　　double dx = l_end->x - l_start->x;
, g( A# z" B" j$ y" k' w　　double dy = l_end->y - l_start->y; : S: T4 b9 C; S/ a9 B4 [# `8 l
　　double dx1= p->x - l_start->x; - G/ x( f# z' @
　　double dy1= p->y - l_start->y; " l* Y, |- u8 y: M, O; G
　　double dx2= q->x - l_end->x; 1 K, b- b$ T  N0 g3 j: ^7 ~8 P) q/ q  R
　　double dy2= q->y - l_end->y; : q% B2 z; v7 H: Z4 }( J) j
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); 5 w8 w9 W7 t* l1 {1 Y
　　}
　　/* 2 line segments (s1, s2) are intersect? */ + s) n/ z7 I4 e8 ~
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
7 w+ c( h# H+ m+ c( \+ F6 D) O　　const vertex_t* s2_start, const vertex_t* s2_end)
- h* m* U3 N) T- w　　{
6 u! M5 Q% d$ e. Y% z9 r　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && & ~( k/ d3 g  d1 R
　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
  I- s2 d. u4 g* m3 L2 k　　}
7 ~% F% z* ~2 I0 ?  t1 @! c+ t" J- M2 l1 {: B/ |
  a) L1 v$ q& |" Q) d
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
( W2 B& z6 `' _: i+ k# g& z# ^0 S
以下是引用片段：5 }' o. _) R8 o5 m
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
& X6 D' O2 @6 B. g$ A) w　　const vertex_t* v) ; n- l5 ]) _/ f2 `  D
　　{ 6 E4 }6 |4 U& ~0 G7 ]7 @
　　int i, j, k1, k2, c; + h6 ?- k, X1 I' a* J& Q8 u9 i
　　rect_t rc;
: i, C8 E$ u4 V8 H　　vertex_t w;
0 r! ]2 t0 ]5 m$ d0 L' C, p　　if (np < 3)
9 u' E7 M. q) A# K, J　　return 0; $ w  b( ?5 G' E
　　vertices_get_extent(vl, np, &rc);
. ~5 p) m$ c: M' Y　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) , {, }3 u0 G5 }& g2 v* k
　　return 0;
  q  ]* v5 q. ~( Q9 P　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
6 q. o3 y+ A; Q, t+ M　　w.x = rc.max_x + DBL_EPSILON; 3 `* W& @- X  a( w
　　w.y = v->y;
1 b0 A* O. s' U% h0 i) Y' K3 ^　　c = 0; /* Intersection points counter */ % l: @1 M- n, \% f
　　for(i=0; i
; O/ c5 E$ D% A7 ^, s# v& _　　{ 2 U7 u/ `: V0 H0 X0 u+ Y8 J
　　j = (i+1) % np;
0 F' k+ y) ^0 {, h4 C; o　　if(is_intersect(vl+i, vl+j, v, &w)) $ P5 v/ e2 E3 c  }" Y& h
　　{ ) l( T% I* G, I* \
　　C++; + z( o, n0 t) x0 M; x
　　} ! q/ c2 ~- y! J( T( q/ b+ W6 Q
　　else if(vl.y==w.y)
+ S' p0 M& [( b3 C0 X. Z　　{   a# P% V" ~, {7 M0 m
　　k1 = (np+i-1)%np; # l& x7 Q! c% |9 t. ~/ X
　　while(k1!=i && vl[k1].y==w.y) # O" W0 W8 C! F. [3 X% @% v2 j
　　k1 = (np+k1-1)%np; + P* O; l4 w8 }: e
　　k2 = (i+1)%np; 2 Y1 }- `( W1 F. g
　　while(k2!=i && vl[k2].y==w.y)
) A' B( z. P7 e) F* O$ S6 f　　k2 = (k2+1)%np;
+ |5 _# M# Y0 |! H- y　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
5 O* B2 O+ y7 h# \8 t# s# a　　C++;
　　if(k2 <= i) 0 p8 j: j5 n2 z7 U
　　break;
1 c5 ?: y% {3 D% z* J, w" g) ^: x　　i = k2;
" ]8 f; m; S, I6 F; i　　} 1 o- p" x& H4 H, |, ]* B# l/ s
　　} 6 X* t2 w7 z: g# c: B/ L6 G/ w
　　return c%2;
- c+ v; y# O7 I/ c7 |* [" x　　} 8 _" D2 L- v, x5 s5 z& I" N
8 l2 g* h- g( h2 b/ J6 X; U" v

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

返回列表

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

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

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

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

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

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

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