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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。
5 P+ _! f, \/ v2 Q6 Q$ E
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。
2 C( q! X5 O3 L0 A
　　首先定义点结构如下：

以下是引用片段：
　　/* Vertex structure */ 8 ]; `2 G0 S- b
　　typedef struct
　　{
　　double x, y;
　　} vertex_t; 3 p* ]8 T8 F2 q0 w2 }$ f

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

以下是引用片段：
　　/* Vertex list structure – polygon */
　　typedef struct
　　{
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t; : D: @& N" F  i$ X, i# |- {# F& w, x

　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：: Z' }/ M' T6 Z0 q7 `+ V, J  F9 K2 }
3 H2 M2 h( X$ H" d& X& E: V
以下是引用片段：
　　/* bounding rectangle type */
　　typedef struct 6 t9 R: ?: E2 u* q" p' q
　　{ , b' [- t5 ~! m5 C4 Z) ^
　　double min_x, min_y, max_x, max_y;
　　} rect_t;
　　/* gets extent of vertices */ + x5 J6 [  R; C3 d! z; s2 g- P
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ 7 I/ j! b1 l0 }% q
　　rect_t* rc /* out extent*/ ) / c" ], x2 J, r9 W
　　{ 8 k3 B7 y& o5 G  y6 P2 s
　　int i; , q1 E) n; [/ _  }" y$ m2 T
　　if (np > 0){ ) q* Z' v0 x4 p8 p/ C
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
　　}else{ ! [) m2 Z4 n0 C* o0 M2 I+ M
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ $ q: l. o! O$ `# b- g
　　} ' d; h$ g+ z. h+ @3 ~$ B4 _9 U
　　for(i=1; i  # _4 U6 I7 f0 j3 e/ M, B
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
; S2 D# T6 G6 Z( o/ I　　if(vl.y < rc->min_y) rc->min_y = vl.y;
/ z0 H( g( e$ W+ e　　if(vl.x > rc->max_x) rc->max_x = vl.x; ; C. C2 Q# ~# K4 L0 K. |& K  M4 k
　　if(vl.y > rc->max_y) rc->max_y = vl.y; 2 E! b1 o$ S) k" I& p4 n6 ?3 ]' L
　　}
$ p2 b! T; y& @　　} / S8 G( U' d8 z( A  W. t
5 e: t- Y9 D0 d

$ ^! N% }( @3 D  X' z　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。3 T" n% @1 S1 r3 _: k
) d' n6 L' N: G, W7 _0 W' G. \
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
7 O! `& h3 O, w9 J5 D$ m
6 Z# E% U% r. l) O0 w　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;( z" Y$ d, A: R( U& w/ s* b

) s  S, K- Y, e+ x- j　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
9 I& n% o/ J; h5 m
  U' Q$ n9 y6 D) m# s2 W& R2 s" r2 R以下是引用片段：: Y; g4 ?+ x% S& o( X' K! C2 T& D
　　/* p, q is on the same of line l */ / ~+ l! u1 G( P: f; F) r5 H5 [
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
7 T. F* I6 D7 {　　const vertex_t* p, + ~$ m5 ^+ o* g$ N0 U, b
　　const vertex_t* q) 3 x3 _) d- I: D
　　{ 2 ]  d3 V6 S+ m; O$ Q% S
　　double dx = l_end->x - l_start->x; : M8 w9 J0 h5 _. Z% A5 G9 ?
　　double dy = l_end->y - l_start->y; 0 b  H5 N2 u  V
　　double dx1= p->x - l_start->x;
9 N2 t0 a& c0 P1 {  a( H　　double dy1= p->y - l_start->y; ! U+ \+ D" h6 Z) |9 X
　　double dx2= q->x - l_end->x; 1 G! r5 e' A( G
　　double dy2= q->y - l_end->y;
3 m8 n0 i6 a( x6 k) J. W　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
6 C& @. u6 a2 g　　}
5 W! u& l" g6 T1 a: Q" e- x　　/* 2 line segments (s1, s2) are intersect? */
( P' q2 h% z$ Q　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, 1 l; G' w& \4 ]& [' w
　　const vertex_t* s2_start, const vertex_t* s2_end)
& R3 C2 B) ~% {8 M+ ^4 c( ^　　{
- \- n/ g7 g8 c) X7 Z7 M# v0 B　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
1 I2 u  s2 w' q) q9 f　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; 7 m9 r# |+ E0 T4 p+ F4 f, P* k
　　} 0 l, g( M0 [2 J3 c/ V
1 [, u' M; \; M: M  X3 \

% G9 ^: x2 E3 g% Y! }7 I　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：' T- j5 d6 J* l6 W. ]7 X" _8 Z. |: [
  M$ p; w4 G( X+ `' a
以下是引用片段：
, U  A7 I/ K, {$ B　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ / b" x1 p% K5 D' G3 j2 B
　　const vertex_t* v)
, F9 G6 M" q( o2 a　　{ + ^4 M' `" @) T9 A" ]; ?
　　int i, j, k1, k2, c; : K* c; D' Z' \9 I5 B
　　rect_t rc;   J. x' X8 s0 z3 A  u8 i2 y
　　vertex_t w; + O( J9 d. k7 b) H: Y* j
　　if (np < 3) + n: X& C0 Q, |6 q! `8 {6 H
　　return 0; . v# e0 A7 _, y! X+ C
　　vertices_get_extent(vl, np, &rc);
& L5 D' x3 ?3 i1 b. B! X$ @1 w; `/ M　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) 6 K( n2 j* i+ h3 p% T& T+ F
　　return 0;
8 w5 @4 _: @6 W) \/ v9 R6 t$ p1 f　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ ) K" D+ G: Z8 r
　　w.x = rc.max_x + DBL_EPSILON;
6 p" o1 ~( {/ v5 Z0 y　　w.y = v->y; 1 b( q& i' e8 `
　　c = 0; /* Intersection points counter */
' @+ C0 D/ c/ D; W' z2 d1 H1 f　　for(i=0; i
, ^1 t# y) Y+ m7 z2 `( ~3 O+ P2 e　　{ 1 q% M' a& B8 B$ |- r; Y% {
　　j = (i+1) % np;
5 m9 k5 D. }# Q" m　　if(is_intersect(vl+i, vl+j, v, &w))
& N6 s0 `' c5 P6 F5 ~　　{ ' k, C( n$ n% [- L3 n
　　C++; - w5 w4 K4 \# s  w# k( i: I) H
　　} 7 z( _' T3 {% E* h- |9 F" G
　　else if(vl.y==w.y)
: t4 G( `9 Q; h( }; y$ j　　{ ; J& [. q# _9 H9 B
　　k1 = (np+i-1)%np; - {# L0 \: N: C) a5 n/ a
　　while(k1!=i && vl[k1].y==w.y) ( Z* f. ~, H; Y
　　k1 = (np+k1-1)%np; 2 O0 T* C) w4 i5 A7 T' k
　　k2 = (i+1)%np; - h+ E/ x4 R" N  D6 P! F. Z
　　while(k2!=i && vl[k2].y==w.y)
/ Y" P9 _+ B9 a9 j7 g( i　　k2 = (k2+1)%np; % a' g# v( Z* U
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) * P6 b3 f3 I( v6 W- m  a
　　C++; 3 @. K( d# x! O( H: u* ^
　　if(k2 <= i) 7 K0 T, w% L: q- B" o
　　break;
' o5 ]4 A5 r- ^: ~　　i = k2; 1 ]+ N- Y( a6 V' C5 G4 P- d
　　} ( m" a. Y) C; C4 d4 h7 X4 y
　　} 3 p2 O6 {+ ]; D3 t$ {/ B, k# W
　　return c%2; 0 o  t/ o+ p$ u% ]
　　} 1 t- t6 _: }+ h) G0 a0 e  Q
3 W# J, o! D7 N# T% P+ ^/ k% S
- e! r) |2 t6 @. V6 S1 T
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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