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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。
/ z3 U" }. R5 W; _
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。1 f) W1 t2 v' f! \6 A
1 f/ w! l* a1 [
　　首先定义点结构如下：

以下是引用片段：- P/ {) n& [) f2 ]& S( G
　　/* Vertex structure */ 6 s1 H( @; x! b3 ^
　　typedef struct / H! x, Z; Y1 U& `
　　{ 3 j* {& [( Y6 h* z) j) E* z# N3 L% ~
　　double x, y;
　　} vertex_t;
8 b& b: n4 D1 e( o
' v; H+ `' r1 X- o/ v
　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：# u# ?" \2 W, a' Q7 V# E

以下是引用片段：
　　/* Vertex list structure – polygon */
　　typedef struct % L9 K1 H8 p& d; S( ]
　　{
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */ . A7 ]$ {# q2 E4 Z6 H+ a; f2 [
　　} vertexlist_t;
4 {% H4 K8 Q. P7 ?: s! Q3 X' _
+ x& N6 y2 l4 L" v" s6 r
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：9 a% x1 u! m: y( P# w) T& |+ h

以下是引用片段：" d; y, U+ t9 C  K# E# E
　　/* bounding rectangle type */ * U+ |3 S0 f/ k5 {% d* L
　　typedef struct
　　{ 2 r, w: w- b7 a; S
　　double min_x, min_y, max_x, max_y; - F1 @6 E" h0 y& C  y
　　} rect_t;
　　/* gets extent of vertices */ ' j5 V) h6 `$ C7 ~
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */ ) f, b  I& e! s' V% W
　　rect_t* rc /* out extent*/ )
　　{ % r% W  g6 C( `. ~/ U
　　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 */
　　} $ T2 e- P5 A/ \8 F4 l. F3 N7 R3 p' w
　　for(i=1; i
　　{ 2 V7 g  b9 F4 k* x0 v% \
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
3 ?7 g0 X0 |4 N- D  c& E& @; C  U　　if(vl.y < rc->min_y) rc->min_y = vl.y; , Q7 d. U, w! \) a- d0 C2 d
　　if(vl.x > rc->max_x) rc->max_x = vl.x; 6 S  G! ~6 u" b. _1 O4 J' K
　　if(vl.y > rc->max_y) rc->max_y = vl.y; ( `+ ~: u  b% R
　　} ) e( }+ q2 e8 _; v, s( C' ?& R
　　} 4 Y5 K- W( m* v$ {9 O

; Z' p9 u1 b5 F0 c3 ], i! o" {
5 o  f( _, f5 S, ~3 `9 \1 K( y　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。5 R) C$ h4 k& m# \
0 `: v) ?& S- Z5 @7 q
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
- Z; B9 X- [$ z$ d' O+ x
; L1 ?4 m& {3 |. i4 @　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
5 D: U! s0 f1 S. u( I# W+ T# w! I4 E5 y7 W$ d3 u
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;+ R& g, h5 i7 ~) T
2 c0 r8 d0 J% |7 h/ a" o! j5 U
以下是引用片段：
% T8 E4 H/ P2 \( G( w' k# n! B4 S　　/* p, q is on the same of line l */
$ n( b6 h& G# G5 e* ]0 I. H　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
+ }8 G! ]' `& i% S　　const vertex_t* p, & E* T) `9 Z: z8 L. X! C
　　const vertex_t* q)
3 m0 W. I9 \8 S- f' |* d　　{ . Z, k) q$ t3 Y9 p! i! b
　　double dx = l_end->x - l_start->x; 1 H, |4 [. W: p/ D! O5 ~
　　double dy = l_end->y - l_start->y;
9 W. M7 h9 q( w7 c* K　　double dx1= p->x - l_start->x;
) x5 j( G6 ~" N0 B0 F$ W! d　　double dy1= p->y - l_start->y; 5 o8 I) j: w) f: |1 l. t
　　double dx2= q->x - l_end->x;
; L( `5 p  |3 c5 O; Q  X6 u　　double dy2= q->y - l_end->y; ( Y+ m0 x# l; W& K& x$ N" F8 m: A4 G
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
9 Z2 A' h+ P: Q$ v　　} ) d$ V4 F9 f& j5 ^, |
　　/* 2 line segments (s1, s2) are intersect? */
' p! h$ t' X% Y　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, % ]7 l- i' j" K& P$ O: g/ |
　　const vertex_t* s2_start, const vertex_t* s2_end) % V  N8 e2 p* e3 v
　　{ 0 B; _2 {7 Z! d
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
: v$ m$ V2 t) T. X5 ?) {　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
$ N4 }- h6 R7 D# s4 w　　}
8 S# j% k: ^3 T5 r1 g6 Y( `" x' z6 R+ C* L" Y, X# s1 ^

5 I$ y# E" x1 }% V# q& _' V　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
" h4 w- w- {; o3 i2 R  _  Q3 y7 F& F5 `1 ^
以下是引用片段：
# V# m/ j0 g/ p8 h" K% i. e　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
# x% p+ X* Y7 p1 R; B. u* `: E　　const vertex_t* v) 0 Z) e8 \6 s  Z" r5 u' U
　　{
6 o" z0 X. N, j+ V- W2 |" V9 B& C　　int i, j, k1, k2, c; ' \6 {7 Z8 R, r6 A' K; d  m
　　rect_t rc; # q$ e3 ^9 X2 p% @% d! p
　　vertex_t w;
, n3 D" P+ j+ d3 A　　if (np < 3)
- x3 x1 K( P1 |7 B' ^　　return 0;
7 J0 |$ ^& S  H7 S/ e, S　　vertices_get_extent(vl, np, &rc);
% ^7 e# Q1 [# W, l; M% N　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
/ H6 x) n/ p. |1 p, @　　return 0; & H) V; z( c( i4 D3 F
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ # e, K& c7 d0 C& l% Z
　　w.x = rc.max_x + DBL_EPSILON;
0 W, a  B) {  [$ O6 f0 s; U　　w.y = v->y;
: G2 L$ ]! @  q- _7 C& Q　　c = 0; /* Intersection points counter */
; ~8 d: N1 N0 A0 d　　for(i=0; i  $ q) m( R' h! t
　　{ & T# |$ ]; {$ d2 N  ]
　　j = (i+1) % np;
* X5 l, q( P1 B; a　　if(is_intersect(vl+i, vl+j, v, &w)) 9 O! d' l  h& U+ z( c
　　{ & P& d1 I' c, F3 ]( Z! k
　　C++;   r# s: A$ i# V% Y2 k+ d
　　} * R$ U. `9 V( [. |2 ?+ Y+ ?
　　else if(vl.y==w.y)
1 n2 Y' g) ~8 T1 N6 K7 }; P( c$ {　　{ - E# y% J1 s: Y# J
　　k1 = (np+i-1)%np; % s1 d9 i7 X4 g6 p8 |- A  c
　　while(k1!=i && vl[k1].y==w.y) 0 Q+ |/ e' H6 l# R
　　k1 = (np+k1-1)%np;
. T1 Y8 T0 v1 U* e0 N$ ^' K　　k2 = (i+1)%np; 6 M+ {1 X- Y, {* c
　　while(k2!=i && vl[k2].y==w.y)
" D7 ?  v& V3 B9 ]. W$ t& \( R　　k2 = (k2+1)%np; 0 N7 a. y, {* g$ j
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) ) H# W- X' ]# q) L7 ^7 ~* @4 S
　　C++;
! M$ ^% l+ W8 y. J　　if(k2 <= i)
5 m; j; z3 k; ^) @9 m7 T1 f　　break;
0 T3 m$ R0 X& C* W　　i = k2;
& x+ n: g% p  C* s% M1 L/ v4 B　　}   W% y9 B$ `! T: m$ o6 p1 E
　　} ! V! i" i! e& Q7 J1 Z7 {# f; G/ {
　　return c%2;
/ {2 Z: L- j$ a　　}
9 D4 a2 S# v+ d* N" [6 o" j0 c& w- H7 y+ T3 n
' a3 B( X- y  y  a" g5 p6 ^, i& @5 v
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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