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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。% c- R, q7 F, ?" ?% s7 O7 a  d0 o
9 ?5 R  W" v# Y/ z5 O5 L9 K
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。' ]9 j$ K$ t  H8 O; A
& f: m* ^8 W; m
　　首先定义点结构如下：

以下是引用片段：, ^6 a' y5 Q8 q7 E# l7 l
　　/* Vertex structure */ 2 B( G9 @) }) R% D& t% V- X
　　typedef struct
　　{
　　double x, y; 8 U2 h  D3 |( i6 L9 H8 ?
　　} vertex_t;
" z' w' U, X7 R4 h7 E

　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：& j3 J% V4 K* O
& y, U2 {3 r3 \& C- M- |
以下是引用片段：
　　/* Vertex list structure – polygon */ : v# e/ G) B$ M. ?
　　typedef struct
　　{
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t;
# X  l- Z& f" J

　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：) [$ T; R( x6 v' S% z3 s9 Y
# H, G7 x- O  T  {
以下是引用片段：. L, }0 t, o' U2 q/ F( n, E$ z
　　/* bounding rectangle type */ 8 k4 ?% U1 K* {1 S5 s7 Q6 v# u
　　typedef struct % x+ n" K8 B' {% O
　　{ / F  R' a& `0 M1 I) H
　　double min_x, min_y, max_x, max_y;
　　} rect_t;
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ ) ) c5 ~! D$ W$ b
　　{
　　int i;
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
　　}else{ 2 e: o; ]" n5 L: N  V  D9 m
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
　　}
　　for(i=1; i  ; ]5 s$ p- `( I
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
0 ]7 O! C1 T% z5 h: m1 W　　if(vl.y < rc->min_y) rc->min_y = vl.y;
+ d+ X4 {1 ?( ^5 G  c　　if(vl.x > rc->max_x) rc->max_x = vl.x;
$ P6 O( D5 }+ p* }& E) T. F' t　　if(vl.y > rc->max_y) rc->max_y = vl.y; ! ^; V* ~& b1 c+ s, z4 G7 u
　　}
6 W9 Z- Y# ~1 S5 ?, h4 {　　} ; m) [" T0 w9 O8 x/ _. j) A, p

: }, V4 i2 ?7 t) X; I  s4 e, H$ q, B8 ~& l1 J
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。9 J! p, j. M8 A
" Y" e/ s. R( h$ j8 W: w1 A
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
& w- ?3 D- M1 c$ [* V" n
0 o8 k5 x& q: a( v" v　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;. L$ O: u% S3 ], H8 C- S2 Q
* u9 J- Z$ K' v4 x# Z5 l1 b
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
# d: X0 x# N) a/ [; N7 v% _. Z2 `7 M+ ]8 b. u: J- r8 b
以下是引用片段：
: g  s- h! z& _& I* X　　/* p, q is on the same of line l */
) t( F" U: _1 e) J& S+ R　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ ! ^3 l( @( r1 c; [: m8 p
　　const vertex_t* p, * O% R/ o% c$ W& O5 G1 a, A
　　const vertex_t* q) + V2 H( H  |: J
　　{
; Y+ C5 J; Z# d. q3 q6 B1 o　　double dx = l_end->x - l_start->x;
3 N% [7 j) V$ z1 B/ s: [) [　　double dy = l_end->y - l_start->y;
5 ^5 y( |1 b' W  h& `3 t& F　　double dx1= p->x - l_start->x;
. m! B( J3 M  t& t　　double dy1= p->y - l_start->y; $ M/ A9 t5 h( x+ \0 p1 _. O
　　double dx2= q->x - l_end->x;
% C/ Y/ g8 p0 S, h6 p　　double dy2= q->y - l_end->y; 8 |* |" e. F, P* l% Y- f
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
4 Y" e: ]% J1 M  a, N8 n　　} * b% p. t* r6 w. n$ J3 f
　　/* 2 line segments (s1, s2) are intersect? */ 7 `: j- a4 t/ M
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, ; N1 g; h9 L9 _9 Z% j
　　const vertex_t* s2_start, const vertex_t* s2_end)
; E0 s; c/ ^! m# M' j　　{
) f, O8 `5 K% y( n　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && 9 v0 a, ^7 x) X6 O' A$ r
　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
9 ?& S7 c, v+ \5 h6 H8 V( n　　}
/ N2 ?2 O2 h, g' v3 L$ }
+ Y) o" p0 `9 [. O; g$ X- \& {: _7 ^$ c( ?  d
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：+ f  r( n: h; d2 \6 d4 M& t; L* O
) K( h# a& S! ^  L& `( F
以下是引用片段：
, I2 t' h: W/ o　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
% V9 c! R0 c" s, X9 Y4 v( X　　const vertex_t* v) / x( g0 L' C- E6 i: _9 P% e
　　{
& A4 ]/ {; N) F5 k2 t# z6 I6 _　　int i, j, k1, k2, c; 8 ]+ d$ A' S( ], \1 V& d
　　rect_t rc;
% l; p/ r+ b  n" P* m　　vertex_t w; % z. c2 k2 {  B: E
　　if (np < 3)
4 U+ n8 C5 `5 N　　return 0;
. h8 k  m; x1 r3 W& z. t" T% J　　vertices_get_extent(vl, np, &rc);
) q% K5 I) L3 Z　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) , S3 O) m8 C" H% H
　　return 0;
* f8 [5 ~  P  e% {& ~) E' m& D　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ ) h9 a7 o( y: I+ [- Y9 [
　　w.x = rc.max_x + DBL_EPSILON; / P$ Q0 \5 K+ v+ P6 L2 `1 k. y) @
　　w.y = v->y; , N6 p4 c  i8 I2 A* A
　　c = 0; /* Intersection points counter */ : Q  \9 S0 V  a& Q2 ?6 W! e
　　for(i=0; i  6 F# \% t5 v+ m. D* Y
　　{
3 A5 n2 P5 x) V　　j = (i+1) % np; - j3 P6 M# k4 U% N% E* ^
　　if(is_intersect(vl+i, vl+j, v, &w)) 7 j" ?9 k/ g* @/ S. y
　　{ 6 o: D7 K1 F, k$ H& Y
　　C++; , S' Y( p) o8 G* v6 m( h, U
　　} # \% t9 y1 ?6 }/ _3 _' J5 d0 F1 h
　　else if(vl.y==w.y) ( u2 G9 D  `, v
　　{ - }0 s0 `7 L4 m/ C) N
　　k1 = (np+i-1)%np; % \+ D0 O8 A0 s$ |, Q) h3 J# e% U' k
　　while(k1!=i && vl[k1].y==w.y)
; r$ C2 {; H, s" E　　k1 = (np+k1-1)%np;
) G( T1 c/ @  T, a　　k2 = (i+1)%np; 7 ?0 {' V  H  _# v% i
　　while(k2!=i && vl[k2].y==w.y)
  Y6 K3 I3 Z9 A! Z. v$ x　　k2 = (k2+1)%np; 6 j, w" y3 U4 T5 H9 W. k
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
. q5 Y9 Y! }* U　　C++;
9 V( I0 e# Y7 N2 m8 q　　if(k2 <= i)
( g$ r# C" o3 x/ t8 K　　break;   U- K# N+ C+ o0 J
　　i = k2;
! t" P, e9 l) R: [　　} " |" N: Z7 y/ F/ Y3 Y
　　}
1 E& E3 X1 T% ~0 B　　return c%2;
# }7 w$ ?- s9 W　　}
1 q) {. D5 W' {% J4 h
4 s' f3 k0 X6 _% g$ w2 y$ ?8 J2 G3 q* [' D
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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