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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。
! ~/ N  c5 A  K( X4 ], u
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。' V, d* u* W/ ~. j

　　首先定义点结构如下：/ d. T) y1 Q, t! G4 z  Y
/ o" e2 r7 w0 X8 `. n3 o4 z
以下是引用片段：
　　/* Vertex structure */ % ^$ K# m( X2 S  a& \$ l# @9 G; T
　　typedef struct
　　{
　　double x, y; + ?5 F) n$ S  p& o6 o, v
　　} vertex_t;   G+ i/ h* d; ^; t! \) R; Y

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

以下是引用片段：
　　/* Vertex list structure – polygon */
　　typedef struct
　　{ & e! Q7 \9 K6 k$ U4 l
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t; ! a6 F  B( i% E. g' ?3 s7 J

7 K; c& @. Z0 n# `( N, O2 s
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：8 n5 Y$ p3 ~1 B; V4 y. m6 K

以下是引用片段：$ v: }- b4 _% G% d7 A
　　/* bounding rectangle type */
　　typedef struct 5 l" [: I( n3 }* Q3 V1 ]  P  _- A3 B
　　{
　　double min_x, min_y, max_x, max_y;
　　} rect_t;
　　/* gets extent of vertices */ + _7 v/ s8 u, l- B0 d5 t% _. G
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ ! a  r; H( a' ^4 ~" O
　　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;
　　}else{
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ 6 B, \5 t; _/ x) @/ f
　　} 9 A* z, M! R, |9 @( c& P# u% v
　　for(i=1; i
　　{   F4 C4 a5 N/ ]- m0 q0 e, q
　　if(vl.x < rc->min_x) rc->min_x = vl.x; / L. E5 e! N/ @6 d
　　if(vl.y < rc->min_y) rc->min_y = vl.y; ) C# x- @: b1 u( r" [/ E+ u% n
　　if(vl.x > rc->max_x) rc->max_x = vl.x; 1 X; `# {, R$ E* r% o; W# {
　　if(vl.y > rc->max_y) rc->max_y = vl.y;
/ v0 |- C) `9 s8 Z0 i' I( c3 u1 b" o　　} $ \4 c6 G$ [6 o2 D. K6 S
　　} 5 d; R) r, o- e: X( }8 X

. n9 O, g6 t+ n* E' U. I0 S1 U1 q# H( G+ P; {9 E/ T
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
2 `9 f+ o* k2 Y. A5 U% S7 o* O
$ }) X7 f$ p- ]4 _8 [　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：. H# Z- E# Y+ d9 A6 P3 }9 l, _) }
: |/ x, \& Q  _# }4 m
　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
: y) Q# T$ P2 o. ?0 @. R
& a8 B: P- ?  Y5 i. A　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
/ ?( }3 ~0 K  m! \, t# c0 W
5 W# L$ j( K/ E6 E! u以下是引用片段：
! a- W' \7 Q! x; ~7 A& Y　　/* p, q is on the same of line l */ ! }, @* R# s0 S. {- }
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
, q! l2 t8 [" u# @2 q　　const vertex_t* p,
8 i7 X  R) B6 M　　const vertex_t* q)
+ v* U) V; S/ e8 R6 a　　{ : i6 `- T/ r4 r
　　double dx = l_end->x - l_start->x;
  J2 M$ Q# `: c* J, _, K( G) h　　double dy = l_end->y - l_start->y;
* o; ^+ j5 ~+ G2 Y　　double dx1= p->x - l_start->x;
) i% M, @6 x% t0 ]2 n. a　　double dy1= p->y - l_start->y;
% u; S9 |2 V3 D( [8 V7 l. G　　double dx2= q->x - l_end->x;
8 f0 G$ v, S8 @/ G　　double dy2= q->y - l_end->y;
; o* g$ Z4 C# _- b) C　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);   ]/ R! z! _3 b$ T2 |
　　} 7 d5 U5 `% g, p! b6 J  U
　　/* 2 line segments (s1, s2) are intersect? */
7 s! t6 C, G' \' L: H3 ~/ B  l　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, - ?4 \. V9 k; B+ w' D
　　const vertex_t* s2_start, const vertex_t* s2_end)
$ ]/ v  y3 g, d: {. d　　{ , L2 i$ g6 y9 \0 y+ O, c5 O7 p) ~8 y
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && 0 z1 p6 D& S! u( f
　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; 0 o9 P! K5 {( n8 ^- H( d
　　} ) y" z( n3 ]! U! a7 X& l/ y
# V2 q1 v& p" r) i' R

+ G1 d$ {# u, E4 v) \* j　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
7 O$ R7 w& w- m- z
  M( k7 N2 u6 P以下是引用片段：& B) h, i3 m$ i" Z- q' [5 B1 W* ?
　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ - T  @2 f& U9 s8 S# ]
　　const vertex_t* v)
/ \, b1 s" O, X" K- G5 F　　{ ! J+ X4 \  W" H0 q" U) c  h& @
　　int i, j, k1, k2, c; 1 N4 o: i; u; R) _* c1 T
　　rect_t rc; ) f8 _- j* r- r. Y: d
　　vertex_t w; # @8 v" x) T' M# ~5 l) S* m
　　if (np < 3)
4 j/ c9 ]2 s( k" i　　return 0;
2 K/ F( T. \- g' L  r6 [$ X: q　　vertices_get_extent(vl, np, &rc);
: f( l& A2 `# X, h$ h( o! A1 W0 S/ A2 V　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
$ `% ]8 {+ d/ I+ A! k7 r　　return 0;
4 X3 X# }# j- e+ n: i　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
) D! f. b$ S, H　　w.x = rc.max_x + DBL_EPSILON;
- m. W( j1 |: G' q) s: B- H　　w.y = v->y; ! G) ~7 D4 m8 h! ]( k
　　c = 0; /* Intersection points counter */ ! T, i( n& ]* T, p7 ^
　　for(i=0; i  1 p- T8 B  s6 K6 l
　　{ ( a8 _: K  J4 A- ~8 O4 m4 m
　　j = (i+1) % np; + W- K1 F- ?8 {
　　if(is_intersect(vl+i, vl+j, v, &w))
' Q( ~! R" n5 `/ V$ I　　{ 9 J* C, V) K: q' `3 B  \5 S8 N
　　C++; $ n" m7 l7 h. \& U  ^( [
　　} # c( q( z% |" a7 W; T/ r2 t% o& v
　　else if(vl.y==w.y) ; s+ d, M5 a6 o  U8 Y
　　{
- p: `; _6 E0 h5 h　　k1 = (np+i-1)%np;
. C) E4 j9 F" F# H: Z* Z# L　　while(k1!=i && vl[k1].y==w.y) . _( ~0 k' u/ }% A3 c, C
　　k1 = (np+k1-1)%np;
3 x3 h& U# z( a0 l　　k2 = (i+1)%np;
6 x) i" Y) _6 n3 D　　while(k2!=i && vl[k2].y==w.y)
: ~8 c0 K8 W5 ]1 n: H; A　　k2 = (k2+1)%np; 3 k( [$ J: k- p# |1 Y# w
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) 4 K0 v# W9 y  |7 x" X
　　C++;
8 X1 f% E% R! a* f* D4 r　　if(k2 <= i) 0 |9 e) i+ v* ~" ^1 {
　　break;
( ]- O/ h* S8 p1 V  [) R　　i = k2;
  w  a6 i1 Q% P! b　　}
. S) T  a/ |/ e. ~5 B( y) e& e# e　　} + z$ W% B& q' Q/ H( v6 d8 `
　　return c%2;
( X# O: o3 K" g* G　　} , o6 d4 w& L0 C) {) ?/ X

1 o4 t9 s4 @, _) K
7 o" P1 u$ I$ v　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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