捌玖网络工作室 » 网页编程 » C语言中显示 点在多边形内 算法

zw2004 发表于 2008-1-21 17:20

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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。
qs X^z!zW
6T3Vv7d*V#}5K8EdbM 　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。9? x%lK&u2L)@
1}H9wA? p!]
　　首先定义点结构如下：
C%\5Z \ ]le
8B}E[h
T,L1S 以下是引用片段：Y CRph@8i+k+R
　　/* Vertex structure */
_rn k9b@d 　　typedef struct jVtT
uqe
　　{
&S,bR"nTZ 　　double x, y; Sy%qd {+kS R
　　} vertex_t;
q!xruQ-{
){ ?4?!E@"M5|*h
(a:Cf;e7}3V0~ 　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：(k?'x N Ix~/nV

!uXFMd 以下是引用片段：d }"x1Yz*Zh$H.qD
　　/* Vertex list structure – polygon */ uba(ieA5| }+{ q
　　typedef struct
P4e;T"LLa;M5vX 　　{
5wAK/Q"uX(r 　　int num_vertices; /* Number of vertices in list */ V8B.KJ%DpE
　　vertex_t *vertex; /* Vertex array pointer */ &G2g.wA%et)l]/D8z*D(K
　　} vertexlist_t;
6N.j
rA xR.e
MO!S*O5p+_8Q` 9m)B [b!c
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：DB:V(KXg
*DU K:c}1p K#l(a;{
以下是引用片段：+B"p7o3W&}"@Q(Aht
　　/* bounding rectangle type */ n m6LM-G(t
　　typedef struct R i'^EHVD|w2[:g!J
　　{ *?U$X]-[2a
fPr
　　double min_x, min_y, max_x, max_y; BsxX I9w7PB
　　} rect_t; :j"^ De(uk
　　/* gets extent of vertices */ 1_amir1o#dI:@
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ wC/f0oH:w(?,`"N ?4r
　　rect_t* rc /* out extent*/ ) K
}A(@F @R
　　{
%LP_q@^No 　　int i; 8D{6QWG Ao
　　if (np > 0){ |~o_3K)tvX
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; %_f%VPMDC
　　}else{ EV/oO ]Ym`;p
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
mhr~Vj 　　}
5Uo[-J
qh-o Av 　　for(i=1; i  
s5i4C$u:iSv 　　{
+jKlB\hzWI[ 　　if(vl[i].x < rc->min_x) rc->min_x = vl[i].x; ib/Q,kc7PL
　　if(vl[i].y < rc->min_y) rc->min_y = vl[i].y; REB/s4Y$P3n
　　if(vl[i].x > rc->max_x) rc->max_x = vl[i].x; 9tS!vBi2R6BCU L`
　　if(vl[i].y > rc->max_y) rc->max_y = vl[i].y;
l1^.{.\Z 　　} m)UOVk{ {
　　}
X"bM)A ~*V2`
$FG;An6H 0Z'ZW)|hB
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
0b k RW8p9L/KRO2QM1A +FS
X6WA `
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：K'N V*g0qCB1r

@%X7|F0^ 　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;e)E5cse
F)PXJO
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
R[9_/aCG"Y-t'~a
0n5x"AU+Qh#J 以下是引用片段：lz!k%OP J3{
　　/* p, q is on the same of line l */ ,o%WL_!|F
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
1a4r
Mp
]&u 　　const vertex_t* p, W
d apz0l"iu
　　const vertex_t* q) #Q"akeh
　　{ .o\,N4GA7n0\X
　　double dx = l_end->x - l_start->x;
3U.T xT5\#c0J!K 　　double dy = l_end->y - l_start->y; (F*LKGJ:^-Vf$Fl
　　double dx1= p->x - l_start->x;
6m"iB"V$E:Gi2Fd 　　double dy1= p->y - l_start->y;
{Y_@0D:O+}
R:Go? 　　double dx2= q->x - l_end->x; Y;[S1B3Z(m
　　double dy2= q->y - l_end->y; hR6`4^2p\d)m,X
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); rkB vj'Ay
　　} ,y2QJ(sc6Qg
　　/* 2 line segments (s1, s2) are intersect? */
]N?'O&vMq?3IH| 　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
wcXf2Y{%]R'[ 　　const vertex_t* s2_start, const vertex_t* s2_end)

~\KC L3R+Z 　　{
)J/A~%hF9j#LX!p!Y 　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && 9x'tfRZ
j-R'tU
　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; 7S8q(e^q%{2z
　　} &ne6Ib1H|0Ta
v(]jR0`/}7P+mS

0jONza1l's 　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：(pG\ Bf| gR;x

zswwe$ut6K-](N[ 以下是引用片段：wuz t.G/P.mJ{y
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ n'{5^R0p]
　　const vertex_t* v) z~~1sdw'T^\
　　{ V'`"iz:Wi3s
　　int i, j, k1, k2, c;
|9KD$h"Xck%t]sW 　　rect_t rc;
E4n,|#k#C*j 　　vertex_t w; eYAJ$Z y
　　if (np < 3) "Ai&y%e4{J
　　return 0;
4b.yTWr;q%c 　　vertices_get_extent(vl, np, &rc);
9ls5ceLT 　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) 9E Gcv A9[3U
　　return 0;
k(xh~:ap 　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ 5J'@!['e2s'`C
　　w.x = rc.max_x + DBL_EPSILON;
]ci;K8_7~n 　　w.y = v->y; b{)F"o^u b,[a3X
　　c = 0; /* Intersection points counter */
i{]4fc8r| 　　for(i=0; i  
,Ai0E8pSFA"@&] 　　{ \ Y7|.k|i
　　j = (i+1) % np;
k1g0o_6Y"V9F*t#x+J 　　if(is_intersect(vl+i, vl+j, v, &w))
O6M2l C3{F 　　{ )gU4F8S;jX ?+W9s
　　C++; X)JSY~]i,w
　　} !F)Kj!O!R}d5D
　　else if(vl[i].y==w.y) /p8iC+BVfXpW
　　{

[.WC/@P4{N 　　k1 = (np+i-1)%np; _2P8o3f`U7|3Je B
C
　　while(k1!=i && vl[k1].y==w.y) Mq a"]q/E#B
　　k1 = (np+k1-1)%np;
F'{&Y1l4}yu 　　k2 = (i+1)%np; T@B9Axr3IH;J^!|A$|
　　while(k2!=i && vl[k2].y==w.y)
(XH1D
i} W4kj)t+\ 　　k2 = (k2+1)%np; W'O$L{3U*~g/^{
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) 2~dFp/l$m*\.z0O `;Z
　　C++; QN4H SX#@"q
　　if(k2 <= i)
5L#Zbc'dEu 　　break;
(H|eKR 　　i = k2; P2q-y&m6BGbtm6r}
　　}
iHlx_?zLAO 　　}
z"]X'jklo:f;]J 　　return c%2; 'T o0I;i*j_
ap
　　} ;p$l$o3u"P,pT
8[ k&l+~z

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

查看完整版本: C语言中显示 点在多边形内 算法