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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。' D1 r/ o" O: q7 O' Z
+ A! |0 F/ n* `& I
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。% V8 \3 p8 s% ?+ n

　　首先定义点结构如下：7 P1 D. Y2 P/ S1 }& s
( j+ }' [/ M- Z8 R/ O; h
以下是引用片段：
　　/* Vertex structure */ 8 b, D5 {1 k( k# z& Q6 |! W! k
　　typedef struct ( x) }8 K1 K" k! z* T
　　{
　　double x, y;
　　} vertex_t;

3 g; J& Y5 p9 A# v+ }" h
　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：* N; [2 B, G, B# ]: z' W6 R
8 ^& C# _4 i. y) c- `
以下是引用片段：
　　/* Vertex list structure – polygon */
　　typedef struct & m4 t: f- ~) u- g; r! }
　　{ * F- N' {& z8 e
　　int num_vertices; /* Number of vertices in list */ 4 g& n0 @% u. }# `! `2 ]
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t;
& q# y2 L$ p; U1 \# J% M
, R% Q: K9 ~* X! Q% H" }
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：

以下是引用片段：
　　/* bounding rectangle type */
　　typedef struct
　　{
　　double min_x, min_y, max_x, max_y;
　　} rect_t;
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ 7 _: b" g( Z8 Z" l: t& C4 s4 O- m
　　rect_t* rc /* out extent*/ )
　　{
　　int i; 7 z0 @2 s- z8 k* r4 z
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
　　}else{
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ & v: h/ U- A: q0 U  b
　　} * U9 Z1 ~5 V7 I/ t! i
　　for(i=1; i
　　{ 9 h* j, ^3 j! q: s/ k
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
1 c4 V* l/ b. r2 z　　if(vl.y < rc->min_y) rc->min_y = vl.y;
8 z2 |% E6 j7 y* @　　if(vl.x > rc->max_x) rc->max_x = vl.x; ; R0 Z- @; _1 o! A$ Z  U; R
　　if(vl.y > rc->max_y) rc->max_y = vl.y; . A5 W8 h8 D/ ?/ o, B& j
　　} 3 N8 G2 q$ V6 u- y1 ?7 I
　　}
# Z) o% I! h1 P5 b/ }
9 j% j* A: L% [) D3 G5 h$ f( S. w2 N& Z5 T9 n1 N5 z( p5 S
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
) x7 X4 B! q7 J# l; p$ V) e: a' a' b" ]0 w+ ~6 t. X. u2 t8 J$ Y
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：- n. y  k  q/ N
% T4 B, N6 d) \
　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
. ^' T9 }) G$ H) ?3 V6 u" p! `
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;; {3 c  Q( C( K

/ Y. t7 g# [- |; Q1 d以下是引用片段：8 B, m& O& [1 l7 {. m% Y% v* E
　　/* p, q is on the same of line l */ ( @/ ~" f. C+ F% c$ ~: A
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
7 a- r2 i" _5 A, `: }　　const vertex_t* p, 0 p* E1 r  v9 U0 z) C$ j7 n
　　const vertex_t* q) : c  s* ?* ]# b9 T: g* }
　　{ 2 `' I7 t5 p% m( o0 v$ T- h
　　double dx = l_end->x - l_start->x; % x0 y' A- R( V: t1 A6 \# y
　　double dy = l_end->y - l_start->y;
0 D5 |7 ]& c, X　　double dx1= p->x - l_start->x;
0 b) M" O) E6 Z; R! I　　double dy1= p->y - l_start->y;
% M5 t, z4 e  o- P' }7 _5 v　　double dx2= q->x - l_end->x; - a& }! e% _& q; c0 P/ n, V' v
　　double dy2= q->y - l_end->y; , G9 H8 D3 ]1 C7 ^' z5 ~. a1 |
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); * {% C8 B7 L6 C% H6 I
　　} ( U( ~& [& h, u
　　/* 2 line segments (s1, s2) are intersect? */
3 L1 J# o$ q" H% ?4 Z+ S; \　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
+ e/ T5 I2 H" d' V4 R' u% M　　const vertex_t* s2_start, const vertex_t* s2_end)
8 `* k' J. K; w: Y. H7 e　　{ , c% V2 U# P+ D& R
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
, L% C3 X6 `0 F& n3 V& T4 a　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; 4 h5 S% r2 u$ b6 @$ g( ]3 z
　　} # C( [! G/ k. ], Y2 k7 `9 A
2 z) Z) w) {) _. e- _/ `: w2 E& W1 q
8 y7 q  ?) i7 a
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：$ w* e6 ~, u  t
- H* c, g8 r/ A
以下是引用片段：  {5 U0 G( @% i! C# E
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
" H5 h4 k$ G) J" M9 m+ i( v　　const vertex_t* v) 8 A4 d/ P7 ]$ |) O
　　{ ( a8 J8 _) f+ B% p! S% \* C
　　int i, j, k1, k2, c; # y1 R% A; O% z* }# x
　　rect_t rc; 0 @/ R  U) {% j5 f+ K' b' ?
　　vertex_t w;
: h. d* p1 [6 S5 w; |( C; [" Z　　if (np < 3)
" C5 Z( W" o+ m$ P# r/ E. W6 `1 y% w2 ~　　return 0; + ]9 m& A$ E$ h4 s+ w+ i
　　vertices_get_extent(vl, np, &rc); # N6 P9 ^& H$ ~1 h9 E
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) , S/ A! }% I2 ]# C. l! g) I
　　return 0;
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
3 [5 f" ]  B9 ?0 @! q, E　　w.x = rc.max_x + DBL_EPSILON; ) H4 X; V3 f4 [$ Z8 k; B
　　w.y = v->y;
  s2 O, K4 R/ V& f2 [" F　　c = 0; /* Intersection points counter */ 0 u/ b7 X! F) v1 P9 @% D$ ?' o
　　for(i=0; i
/ v( K6 i  X5 V1 N& i　　{
& P- \3 J1 i3 i5 X　　j = (i+1) % np;
& [$ Q7 N% E) q' x' m　　if(is_intersect(vl+i, vl+j, v, &w)) " e  y7 g" x3 O, ?+ M" m# g; i
　　{   Z" c. V4 @# \5 F: d* q8 i
　　C++;
8 w6 M3 f" }& A7 Q2 w　　}
  A/ R8 `4 e# z8 h　　else if(vl.y==w.y) 5 T5 f- q( O) @% E( w( Y
　　{
" K( a: A6 Z/ s. Y　　k1 = (np+i-1)%np; ( I& o6 ?2 B. X/ m
　　while(k1!=i && vl[k1].y==w.y)
1 u3 [  P( x- e0 r5 e　　k1 = (np+k1-1)%np; - N1 h. q  A& L
　　k2 = (i+1)%np; 2 p( }) J( A6 x# N2 Y
　　while(k2!=i && vl[k2].y==w.y)
+ b& o- Z9 d6 u  p0 O　　k2 = (k2+1)%np; ! {1 W% @, V* C) {
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
/ Q7 I# l" e2 q4 o6 e* A8 P　　C++;   [" d* o5 w; m1 w
　　if(k2 <= i)
6 W) X( h2 |. U# N* P/ C& d　　break; 1 N- Z/ w) `" s  O, G
　　i = k2; ( c4 c" O/ X& @2 Z
　　} 9 J2 ]1 |, U% ?6 F$ f6 s  j
　　} ( E& I) M$ W3 r( e) b1 q& S; W7 \. h
　　return c%2;
+ i3 }8 _( Y0 M# W  P6 d" c　　} + d! b4 @5 @4 U6 @. S8 L/ b1 U8 }
# F0 }- h; u  l

: A+ D) K, `! L* C" w5 ]2 _; W; f　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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