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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。

　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。

　　首先定义点结构如下：9 ^# e# H% r8 E% y$ g4 g+ R

以下是引用片段：& V# ^7 A  W2 g) G0 W
　　/* Vertex structure */
　　typedef struct 9 j- {! x3 e( i% W! }
　　{
　　double x, y; 9 R' l' H( m7 t& k/ x
　　} vertex_t;

　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：* V) H- l6 x9 q
7 ?* C$ R: K9 F. j
以下是引用片段：" g: M" ~! M8 ?& D5 ?
　　/* Vertex list structure – polygon */ % r/ Y- y: G7 Q1 `0 m2 E' |1 R( X
　　typedef struct 7 l# f# w6 f9 J2 o+ ]
　　{ % `' y3 L  f# M8 i) }; `' I) u3 J) T
　　int num_vertices; /* Number of vertices in list */ ) r1 v2 q8 Q' [& [, C6 b
　　vertex_t *vertex; /* Vertex array pointer */ $ O: X1 K6 l- L/ i4 b1 a8 n8 `
　　} vertexlist_t; % C5 _- J9 \$ F: {

0 J1 p, a( x0 O7 L3 m4 W& s6 K
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：5 ]0 D7 ]. k  w) S$ N

以下是引用片段：
　　/* bounding rectangle type */ - C% k, T2 {) C# T+ u3 d
　　typedef struct + p5 h0 n) {; {1 F+ i! v4 M: v
　　{
　　double min_x, min_y, max_x, max_y; ( a  T0 D; ^$ `4 _& c, k  z/ |
　　} rect_t;
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ ) / }6 b/ \: r# `/ C( ]$ }
　　{ 5 p3 W) ^/ M8 K( P1 \
　　int i;
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
　　}else{ / h& J! z3 `" W. R
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
　　}
　　for(i=1; i
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
% J( ~/ F) k) G4 w2 E6 f5 p: D　　if(vl.y < rc->min_y) rc->min_y = vl.y; % N3 C& E* T" J6 P
　　if(vl.x > rc->max_x) rc->max_x = vl.x; + W4 s0 R4 G$ R" B& Q- Q
　　if(vl.y > rc->max_y) rc->max_y = vl.y; 7 p2 S8 R: B: U
　　}
9 w3 \- b/ N" |* N; a& k　　}
  e( c4 w# _/ R) M+ m
) m  S: a2 l3 J" j3 I' R* c+ A( c" P+ k& _7 m
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
5 f% A! N' y8 O+ ?' S1 t" @( j/ s" H/ f! V! ^& k# m& J" u! n+ R* ^
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：+ @3 P! Z' P8 [1 n
# r; J3 k8 S) n7 D
　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
0 [. Y- A2 b5 _% J
8 F; J3 G+ o5 a6 a0 u　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;* \% n% ]6 f* \& `
- V  Z8 X, N9 T3 S$ ?% J
以下是引用片段：
* j2 B! [  N5 G1 V4 e　　/* p, q is on the same of line l */
4 u7 v" g" m0 S9 B: d　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ 0 l. I  S0 h9 M- b
　　const vertex_t* p,
4 B& J$ _# Q( i5 k9 b* Z: f+ K' t: O　　const vertex_t* q) $ i% g% z" a; P
　　{
6 \  q% Z3 |/ D4 h& U8 s: H# w　　double dx = l_end->x - l_start->x;
$ e+ k; X& M  U% r' F- G7 G　　double dy = l_end->y - l_start->y;
, V7 @* \" o6 d. c3 s9 y　　double dx1= p->x - l_start->x; ( ]+ Y: e' e" s+ U5 O* R" K& v
　　double dy1= p->y - l_start->y;
$ f" Q, j) Y; ?4 |5 \& y1 I4 t　　double dx2= q->x - l_end->x;
5 _2 [* `( m  C2 E9 }% |　　double dy2= q->y - l_end->y;
# g: p. r* a& @+ @2 J　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); 0 ~6 t( k% R7 f  x0 F
　　} ' n1 y4 M& x# X7 M
　　/* 2 line segments (s1, s2) are intersect? */ 3 z7 m: m, ]( M( K' W- k0 O
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, ( _2 D# C  _) y/ u5 g: h
　　const vertex_t* s2_start, const vertex_t* s2_end)
; g- V) q0 e$ \2 o2 W+ J　　{
6 B; O/ p% @" o, v. [% B　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
4 B' h* L  y- _　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; 5 k, V& N" F3 }" `8 Y" L
　　} ' D6 W% I: `! R! B) O2 f7 i
  N- ^* r3 t1 a: L" |
: m! X0 V5 Q* ^' }1 x
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：8 a$ G! M4 i* [# y- `

" s8 n- e" T( W) ?以下是引用片段：
0 y$ T0 Z* x& Y$ l　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ # N) X/ ?! m3 x. X, w2 v4 R
　　const vertex_t* v) 6 n3 G* u# f! h9 d* O$ \
　　{ $ ~$ \5 ?" O, Y/ c
　　int i, j, k1, k2, c; 5 q: }" P0 x# w2 _2 E8 X4 G
　　rect_t rc;
: T: ]& S# m# ?　　vertex_t w;
% h: x0 G$ N0 h0 z　　if (np < 3) : Z- M6 E: U0 {8 t
　　return 0;
- `" H$ L/ W. _/ J6 A　　vertices_get_extent(vl, np, &rc); 0 A0 j4 @. f4 M0 T& p2 e
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) ( a; y* m) v* B0 ]
　　return 0; 9 |: @0 @9 ~  ]3 o4 C3 t3 O
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
2 U/ n8 z& v% v/ N) w4 |　　w.x = rc.max_x + DBL_EPSILON;
) O% q' }3 h0 O4 P& K　　w.y = v->y; 1 @: F- L) N4 o; t9 K- I
　　c = 0; /* Intersection points counter */ # F4 A+ \1 u( T) S% ]0 `( E
　　for(i=0; i
& d/ y6 d2 q. o& i9 n/ I　　{ . t2 h. ~+ W5 p9 `) B) ^6 p* C, j9 u
　　j = (i+1) % np; ) @  A8 d" A" _# n
　　if(is_intersect(vl+i, vl+j, v, &w))
0 Q8 Q9 K( a" K2 d　　{
" H! @! }4 D+ I( @3 R% o$ P$ w　　C++; 8 r( a4 N  T$ ?9 J1 r
　　}
. y" R( c+ V; c4 G4 @5 y　　else if(vl.y==w.y) 6 }% d6 R( h& \  l$ T, a& n" {+ }
　　{
( S8 V# z# s5 h* A　　k1 = (np+i-1)%np; - G7 R/ f' e0 c2 p6 k# z% E
　　while(k1!=i && vl[k1].y==w.y) 9 p( O. g5 ?4 q5 @+ D
　　k1 = (np+k1-1)%np; ; @7 l' z  |0 i4 w- }
　　k2 = (i+1)%np;
' E, |2 P. V& I. J/ z　　while(k2!=i && vl[k2].y==w.y) 3 ~. g0 Y8 J$ E3 D% a* |# c, ^  y
　　k2 = (k2+1)%np; 1 ~  k" V: O/ H
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
/ b- w0 X* ]! X/ |) P8 Q　　C++; # J8 l: q/ `- l0 Y8 |
　　if(k2 <= i) . c, [/ Q+ M. j. u! U$ W
　　break;
6 x, O3 ?: t8 @$ f  N' S　　i = k2;
* ]! H6 _+ H0 g/ s2 ?# k7 t) `) D3 L　　}
$ |# S0 i# L  v1 m8 N- |　　}
+ `4 W- P6 k  \7 M) w2 L　　return c%2; " i& i" A9 z0 c# O- Y' l
　　} 8 h0 Y) f' f/ F5 p5 H3 E
" _" g/ ^4 N# c/ n* I- \
7 L/ A) I7 y$ }/ l1 t3 b$ _
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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