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

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

　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。7 a2 ~) o3 @: V; U3 k$ N" @- M3 l0 s
! S' K# K' H9 H" |  ]% \7 ^- p' W! ?
　　首先定义点结构如下：. `+ |3 ^, B( [( e  u" v2 l

以下是引用片段：
　　/* Vertex structure */ " X& n3 z% s3 w! O" A) z+ Y
　　typedef struct + X5 i0 X1 l3 X0 \4 e  w
　　{
　　double x, y; : m, v1 e! s/ A+ s/ G
　　} vertex_t; 4 ^7 w6 N0 m4 B: e4 o
; _* i% a" }* D6 a

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

以下是引用片段：& B' d! l1 O0 v" T' B% j! [
　　/* Vertex list structure – polygon */
　　typedef struct 6 H* }% e" k; g6 u# [- w) G
　　{   u  P8 p. E5 y3 l; d0 V* O( ^
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t;   e. \* X1 R+ w- o) Z( ]

　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：; L! k9 m# J5 j1 d; |: ?

以下是引用片段：/ [$ Z% M5 W+ m, t8 u+ M
　　/* bounding rectangle type */
　　typedef struct
　　{ 3 f' J! C2 A5 b5 K/ U+ e
　　double min_x, min_y, max_x, max_y;
　　} rect_t;
　　/* gets extent of vertices */ * `% i* I: ?) w5 t! Q2 G
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ ) ) A! O9 B8 t: @6 d: w/ |' V
　　{
　　int i; ( G1 Y) {/ q8 k8 h- S( k  w3 U
　　if (np > 0){ & A5 R0 [0 h: R
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; 4 A: q) F4 y' y; F  h' ~
　　}else{ " c0 p0 J: X% `4 ^- j
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ 5 d9 D8 O6 a5 c7 e. m# |$ E4 t+ i) `
　　}
　　for(i=1; i  ; d( R3 K& N6 i; \3 ?% n0 q
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
, d; R; r6 l6 ?' u/ t' H4 W　　if(vl.y < rc->min_y) rc->min_y = vl.y; * m4 |, W; l* K: g
　　if(vl.x > rc->max_x) rc->max_x = vl.x;
7 t2 e1 U- M" v$ y/ q7 x　　if(vl.y > rc->max_y) rc->max_y = vl.y;
' L6 k& S7 ~6 H" S　　} 5 H1 O9 D, s8 P  J5 M; d( d
　　}
! J0 B, Y; v5 f$ ]: g7 a+ o% S$ A* S7 v2 C4 q" M$ w: W% T
* W7 `" e+ u& R- B  w
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
% }4 {3 F) l6 \0 \+ ?0 e
7 l8 L, n4 t2 |: F　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
$ _1 t+ ?: \) X2 W% U8 Z. x6 }0 n& Z0 O) L
　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;; X1 G6 ?; H) z9 `; s

$ R( U3 g2 a" K# t% d2 w& G　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;
5 h1 h9 q: m, x; G3 X2 L, X- k# X8 I! ^
以下是引用片段：+ @# M- u& c  M) a
　　/* p, q is on the same of line l */ 6 _0 L% J  B3 W- C5 K
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
; b2 s& M0 _- V' f1 u& F　　const vertex_t* p, # _0 j1 o( H, G: g8 \
　　const vertex_t* q) ' e7 [; i  A# \8 k! t" h% }6 v
　　{ 8 P" O. z, r% V8 R( [
　　double dx = l_end->x - l_start->x; # I' a- @9 x8 z. \" X5 v* ~
　　double dy = l_end->y - l_start->y;
, O" D, S1 ~0 v* ~6 u　　double dx1= p->x - l_start->x;
* K% ^# o) L  l　　double dy1= p->y - l_start->y; ' _, e* P5 D, u8 V
　　double dx2= q->x - l_end->x;
0 Y1 H- c! i6 l0 W5 r: X　　double dy2= q->y - l_end->y; ' H7 j6 n2 y1 p; ^/ M9 q+ M! l
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); 1 {; t2 p; L; y9 k
　　} + S4 u2 y# w& ^7 p
　　/* 2 line segments (s1, s2) are intersect? */ , A4 F9 c1 p9 m& A4 G, q# m- ?
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
; m( c' U% P9 z　　const vertex_t* s2_start, const vertex_t* s2_end) - N' A# a9 ]! x3 p# L9 D% i
　　{ 7 e- w4 O/ q) {4 r  F
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
  _! ?. q8 g( E　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; 0 h6 I1 o7 z, d
　　} ; Y) Y$ y8 t7 r! S* \+ u
% j" T! P; b8 l! F
9 G) l& k& W; M6 y# U3 d
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
& Q- n, I! Q5 Y  d$ g+ Z% e8 r; Q. J: ]: @$ S4 D) Z5 Y
以下是引用片段：
" k6 t: @( }8 P+ b$ q7 G　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ , a/ x3 f/ p! q* i8 O+ M7 c% t
　　const vertex_t* v) 2 D, F6 g+ d4 {! B7 {
　　{ $ I- h2 h* Q; Z8 s# z% O
　　int i, j, k1, k2, c; ! Z/ V/ x  d8 s2 `' a  [% Y
　　rect_t rc; 0 \% g2 D" e) p; r, a: U* O4 v
　　vertex_t w; + g6 W, C6 h' V4 E8 u  t& W+ [) ^6 d
　　if (np < 3)
9 p% K, Z- [; d* Y6 }& n　　return 0;
$ b# ]1 t8 t: R1 U　　vertices_get_extent(vl, np, &rc);
# p% F. z! z' x9 D- M% g+ X　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) * P# e2 ]  D; y$ p9 j
　　return 0;
3 G4 J# |5 W1 g  p$ |　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
0 n# a; Q# S4 N6 I5 n$ l/ p' C　　w.x = rc.max_x + DBL_EPSILON; % i/ B0 ~+ _- G7 v, _6 a
　　w.y = v->y; % x& _0 Z$ l, a
　　c = 0; /* Intersection points counter */ 6 P7 S0 O! a) k2 M% P
　　for(i=0; i
  W! H* G0 o9 k8 X8 Z1 j　　{
' X' Q% }8 d0 I' e  K　　j = (i+1) % np;
; a4 O: |' O7 ]　　if(is_intersect(vl+i, vl+j, v, &w))
! s8 m5 `7 ~7 i& {$ x5 K0 a, u　　{
* A0 |" H+ \6 Y% R3 x; m　　C++;
( v3 F' W/ B" r; y) k8 ^) ]% D　　}
* f5 g* X/ N$ U' y( x2 x) E　　else if(vl.y==w.y) & d- U7 a0 _% t4 P3 w8 X& F0 ^: L
　　{
5 J, M  Y7 |' G- _' Y. k　　k1 = (np+i-1)%np; 0 G* [7 E2 j  W  s5 o$ O
　　while(k1!=i && vl[k1].y==w.y) 0 Q: V) R0 h* ~8 b+ i
　　k1 = (np+k1-1)%np; $ b/ y5 M/ X4 {8 P/ j9 o
　　k2 = (i+1)%np; - z' G% E0 c8 C; H- m/ Y
　　while(k2!=i && vl[k2].y==w.y)
# J; v4 W  A' V) z　　k2 = (k2+1)%np;
7 K# }+ `3 u( ~7 k　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) / k! ^/ F0 \8 R5 {. ^( I' y
　　C++; - n6 t' U3 t9 t* K. a9 t
　　if(k2 <= i)
: ^8 K( n$ Q+ B" W/ I. o　　break; & W0 D& Y# `0 e+ |/ X
　　i = k2;
' }1 W$ |3 P1 _9 N: A4 R; I* E　　}
6 K! E0 v& ?5 X　　}
' H5 y/ Y) T4 w& h% j　　return c%2;
* }- B' ^9 @$ j% d. d3 Q　　}
- `5 I- X% i& e5 |6 i9 B: l3 a0 U
+ a$ x. h4 l$ X4 c% ~+ g: ^% ?' N- g1 z! N( Z4 R  f
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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