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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。# O5 d' V9 x; {& O/ Z9 x/ d. s
  O) Q- ]1 D6 m
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。' ?8 n6 R7 X6 P+ `, ?) y  C; g2 X8 y

　　首先定义点结构如下：* V8 x/ v+ Z1 Y/ P/ U
; e5 G" W1 R% y; o8 A
以下是引用片段：
　　/* Vertex structure */
　　typedef struct 8 L' |# N, v; f; |$ r* H) G# v+ c9 \. I
　　{ 8 @0 g- D+ L! t
　　double x, y; 4 j! z, B4 M% X, {$ ]
　　} vertex_t; 5 G4 |/ e7 K6 W! \# ~( U6 q2 H: K5 \
, O0 f5 i6 q" i% ]- ~

　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：: _7 p4 u1 P3 O( l
# {, o2 h2 V) R
以下是引用片段：
　　/* Vertex list structure – polygon */
　　typedef struct ; k! I! n# R- r/ ~) a) I9 Q8 M- d
　　{
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */ " B' q4 V: ^* K# Z' P
　　} vertexlist_t;
8 @. p# m/ s- p& N  h

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

以下是引用片段：
　　/* bounding rectangle type */   F. c1 F6 I8 f; C/ C
　　typedef struct
　　{
　　double min_x, min_y, max_x, max_y;
　　} rect_t; 9 R; _  ?* v& W' }" Y
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */   w2 }- E! c8 {4 x7 D2 r! o$ g
　　rect_t* rc /* out extent*/ ) ; Y7 V/ ~* m3 [/ N) \" F
　　{
　　int i;
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
　　}else{ - p; {, _: r; t& x
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
　　}
　　for(i=1; i
　　{ & i& s  c: x- }! i/ k, S
　　if(vl.x < rc->min_x) rc->min_x = vl.x; ; _5 p) U; o* A
　　if(vl.y < rc->min_y) rc->min_y = vl.y;
. j* [) x3 i9 _: f9 }! v　　if(vl.x > rc->max_x) rc->max_x = vl.x;
) O; a8 |7 y6 O# ^　　if(vl.y > rc->max_y) rc->max_y = vl.y;
( Q- Y" P9 S  _% `; b　　}
" |2 ^; Z% n" y　　}
1 c* G' q& v! J& ~+ h$ j% d2 ?! S$ @
4 j0 F: u8 {* W, U) F+ j
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
* t+ Y6 V+ \' S6 X0 s
% F0 g  g) Y) f! y  i% n　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
" B: d6 H9 Z1 k$ E, ]6 A6 O: ]- h- g, W) W+ V1 U
　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
5 [* p& V( `1 y% v' q
5 d3 s( K, R: e6 J5 ?( D　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;- D5 ^, i  i  S9 [) a+ k& Z. n" u

1 X% G5 z5 d" b* v# E- D* V2 s; G以下是引用片段：9 `% z% }! Z; e% r  g/ m: j
　　/* p, q is on the same of line l */
3 z  W9 g0 a& q# k　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
) D% {% D6 ~" |/ D% ^; s, t　　const vertex_t* p,
' X) w9 f: ~; [8 q  k　　const vertex_t* q)
- |, M8 y3 b$ N6 x5 z% X　　{ & y1 }; ^* i, }, r  {0 L6 s1 \8 p5 j
　　double dx = l_end->x - l_start->x; 7 @$ }4 g4 O2 [  C; m/ _
　　double dy = l_end->y - l_start->y; 4 R( K+ ?- F9 w& a5 o- Y7 i
　　double dx1= p->x - l_start->x;
. v& h% W; I7 N( O- b4 R　　double dy1= p->y - l_start->y; $ o1 Z( \% h) {# f7 Z' m
　　double dx2= q->x - l_end->x; 9 A6 n- R# G& E, d
　　double dy2= q->y - l_end->y; 9 f* L& m% d$ ~& u3 b! E2 G0 ]$ Z
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); 5 f9 G2 w( U9 [6 Q7 S
　　}
) A. f+ `3 t0 p/ u6 A5 x7 Z5 _+ Y! L　　/* 2 line segments (s1, s2) are intersect? */ 5 I; L, {, J1 V3 s! O
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
% L& P0 e: H+ d　　const vertex_t* s2_start, const vertex_t* s2_end)
: z0 R) K. y" a+ B$ s, t& U　　{ - f, y: k* e9 k, q  j& O" v
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
  d/ }+ p( {# K1 f1 m' c$ w+ e　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
. r6 }5 n) k1 ~; q/ h　　} ! x; T$ ~% V. c/ e2 R0 \0 F9 K
5 r" f/ \9 [" N' q6 L
. l: u! I9 u/ V
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：; i! L0 Z$ I7 [* E0 c

$ K0 Z9 r# Z6 h; M. g  }5 K" o, Z以下是引用片段：
% m7 c7 |; F! q# v　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
3 C) b' u/ j6 w$ A% W5 I8 b: v$ O　　const vertex_t* v)
6 {6 p3 Y5 [9 K- k　　{ ! W, E* ?3 T0 u0 n, _
　　int i, j, k1, k2, c; # D( _2 @8 a1 p- \0 H
　　rect_t rc;
- e7 R  K! d6 p9 y　　vertex_t w; ; E0 j; f$ B5 K  p
　　if (np < 3)
7 a( G& y* f' T. [3 h6 I( g1 q　　return 0;
9 L+ T. w; O+ V- @0 B　　vertices_get_extent(vl, np, &rc); : Z/ C" B8 y3 {$ k  H! b, H
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) ) Y! q8 d9 e1 w  F
　　return 0;
* r! n# c3 u2 f# ]9 J　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
# V& R1 k5 j" b) ?6 _( y　　w.x = rc.max_x + DBL_EPSILON;
; v) k: s9 w& e4 p　　w.y = v->y;
1 [" I8 ]9 m) T1 ^1 K" ?　　c = 0; /* Intersection points counter */ ! h4 V7 M% Q% E: m& F' ^8 \1 X
　　for(i=0; i
/ t! e! p6 v- c/ T  T0 g- i　　{
1 V# T1 K) q9 t　　j = (i+1) % np; 0 V2 Y. g: [% x- u4 s
　　if(is_intersect(vl+i, vl+j, v, &w)) 8 N7 l% x% B5 k& |# R! E
　　{ - [9 J; j; S3 z  c- n
　　C++;
8 w5 P4 N- Y# K  B) w& r; \$ G0 r7 l　　} ( w* \$ w( W: W! Y. l
　　else if(vl.y==w.y) 9 ^$ q: X& _0 r9 z- I
　　{
/ V; |+ N* f! U: _$ D　　k1 = (np+i-1)%np; 4 d" b2 p- V# u, V
　　while(k1!=i && vl[k1].y==w.y) 3 n3 Q4 ~$ P# I4 ], l7 z, w
　　k1 = (np+k1-1)%np;
' l6 ]+ X8 Y  A- N1 U& s　　k2 = (i+1)%np;
7 j0 X) x1 t4 x& M　　while(k2!=i && vl[k2].y==w.y)
1 Q& g* ?' [$ }$ k3 ~　　k2 = (k2+1)%np; 9 u$ e7 e# z, Z  F. ]
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) - I0 `& P  a( T# F; `
　　C++;
4 o. Q, _( h& t  ^7 G5 C+ ~9 y　　if(k2 <= i)
/ G6 V8 s* R* C# ?　　break;
! b; k7 U# u) \5 ^6 Z　　i = k2;
  P: D8 F  n1 ^8 H3 H* S& I/ U　　} 9 E. O0 t5 g7 S4 y
　　} ; b4 s' L, ?, @3 D% j. S$ |
　　return c%2;
& T0 }4 ~; t. ]" _" f' }　　}
4 o  C, b/ `- ~& ~# ~
, q/ n* @/ S5 @6 @" e+ h* f, G
- s) v" C) ?: p2 ?　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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