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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。+ J* z/ \' ?; u- [4 k* H
% w. i  Q: g3 q
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。& e: z  x0 _* t8 K2 B$ x& {- a/ y

　　首先定义点结构如下：! h. ~% ^5 n$ f! n, q
7 {% _. q9 z, f9 H
以下是引用片段：' d" {) |; _  m1 F! {' I: ?
　　/* Vertex structure */
　　typedef struct
　　{
　　double x, y; : q) u+ c  h3 Z2 o$ Q
　　} vertex_t; 8 U8 g& C( g( Y& o) a
( Q! r1 a& x& I2 p' T9 Z! M$ B

　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：
6 T9 T+ n5 b' l$ ~6 g
以下是引用片段：6 u8 O& U5 h; i( _$ D- V& ]5 N
　　/* Vertex list structure – polygon */
　　typedef struct
　　{   ?7 y- G7 R+ ^0 h0 `: g
　　int num_vertices; /* Number of vertices in list */ 5 i" H3 R9 M  N; e2 f) m  n  x
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t;

* ]' g* ]$ V: q+ d3 `
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：
( c% Q; D7 a6 B" [* r8 O
以下是引用片段：# H4 q- Y. {  X( ~# j4 [) y
　　/* bounding rectangle type */ 0 E( ^" ]3 i  p' W- a4 b
　　typedef struct
　　{ 9 P6 s1 p+ q+ [: d4 }2 ?
　　double min_x, min_y, max_x, max_y;
　　} rect_t; , g+ q! s2 p1 X, w2 T
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ ) ( P. |2 l# B# ?7 K( F4 \$ D
　　{
　　int i;
　　if (np > 0){ ; F, y* \& ~6 v6 e
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; 5 ~! N  A- X! l
　　}else{
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
　　}
　　for(i=1; i
　　{ 6 N8 ~1 w4 p2 T8 s
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
/ }) u8 `6 M. F% n5 g) }1 l4 P. ^　　if(vl.y < rc->min_y) rc->min_y = vl.y; & B, _$ E$ U% }
　　if(vl.x > rc->max_x) rc->max_x = vl.x;   _9 \0 B5 [+ J. h1 a8 M/ o1 s
　　if(vl.y > rc->max_y) rc->max_y = vl.y;
) O% S6 V9 \4 l; X8 n; t& Y　　} / b9 ^6 o- K$ I, t0 B' j/ U
　　}
1 Y+ a1 O' I/ Z" `4 b+ c: }" M6 x4 L, f

& U7 Z' P! |+ c　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
* _9 l2 \: S) J7 `
' Z6 d  q; d: B. ~; s　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：+ L% [( v* X' \( y9 |6 V
2 N! o- ^6 F! }% b+ i# Z2 {  a, ]
　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;1 d2 ~7 s, X0 |' m: b

4 ]5 g' A$ E' N/ Q; w5 b1 v　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;6 Q( A8 B7 }* U: ^
, h1 r( i4 Q* D, m( u8 x
以下是引用片段：
& _' \" N: N! k　　/* p, q is on the same of line l */
$ H$ M8 E7 W2 f9 ?) |! X- D5 ]* {　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */ ) Y% t' G1 r9 X8 L, s9 [
　　const vertex_t* p, $ G7 ~. k3 x* P* K% V/ y* M9 W
　　const vertex_t* q)
* m# v# y4 M* V2 U. N9 H　　{
  W* S" {9 y4 k/ v0 }! r+ ~% X8 K4 y　　double dx = l_end->x - l_start->x;
. y6 q5 v0 c$ Z# W　　double dy = l_end->y - l_start->y;
- b7 H+ x( R5 x( g$ R: ]　　double dx1= p->x - l_start->x; ( [/ |. i5 m- i( o2 Y
　　double dy1= p->y - l_start->y; , s9 E/ ^7 |  c, Y& C; \
　　double dx2= q->x - l_end->x;
) \, I. y8 F* h　　double dy2= q->y - l_end->y; : [2 A$ K' e0 c
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); * R& {2 l8 y+ k. p6 P* @
　　} 9 a3 p4 H- G! w% v4 c
　　/* 2 line segments (s1, s2) are intersect? */ 1 s2 g2 I) \/ y& C
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, ( F. p( e! {  \
　　const vertex_t* s2_start, const vertex_t* s2_end)
. `" `" d; }* y5 g　　{ 1 z0 d, P! s6 P/ w$ K: T* [0 J& ^
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && 0 n# S" e1 ?/ {# m
　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; ) j! C. H; }* G$ q4 u$ g
　　}
5 D: T+ ?+ x, ^7 j3 M- e0 e" h
* g6 V5 o2 V: o( ~' z- Y8 v" [2 @) {+ B. d2 o; }
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：1 y& W5 M$ z4 B$ U
$ [9 J2 y( e3 [5 K7 \+ B9 z* V
以下是引用片段：
" i: D& n! E: G; E& B　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
* ^# u& |* W% N7 h1 N( F7 _　　const vertex_t* v) : j* B5 Z- p! t: P& R1 t
　　{ * V8 ~9 u  G! Y7 z) A& [) r  W+ p: V
　　int i, j, k1, k2, c;
4 L! A8 x! F% C* @$ V  ]　　rect_t rc;
! S& J6 N6 q2 a, j* X　　vertex_t w; " l0 x6 `/ k' E, o
　　if (np < 3)
6 e# P8 n) l( n: q+ ?0 m7 @/ r　　return 0;
: @- n- J3 N" v2 Z* E/ }0 {　　vertices_get_extent(vl, np, &rc); # N1 P7 r2 Q/ _/ i/ r) U$ f1 j
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) / ^. l$ e0 w1 X
　　return 0; 6 P7 l% \, O# w! Q2 u2 X: J% `
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
9 A. s% h+ I+ ?! _　　w.x = rc.max_x + DBL_EPSILON; 5 w0 d1 J) _& W, {+ v  Y7 t4 P
　　w.y = v->y; : W: N2 \( B6 M' D8 Y
　　c = 0; /* Intersection points counter */
6 C5 w' v" @, M0 }2 C　　for(i=0; i
8 z" K$ N* Q" o, Y+ S" Z　　{ , O/ N! |  t- }, _5 J1 H8 L0 p
　　j = (i+1) % np;
0 K( O- l# O& {' H+ n- T　　if(is_intersect(vl+i, vl+j, v, &w)) , j, p2 F6 j4 i7 I
　　{
3 [$ `) S7 g0 o2 Y2 n; H. g　　C++;
- |* ~+ c9 d  B  A, H　　}
& F- v2 L3 A8 Y! d* m1 Z. P4 f　　else if(vl.y==w.y) - R6 H, k8 f5 l4 P  a. d& q
　　{
# x0 e) i$ w6 S4 M% C6 B0 b　　k1 = (np+i-1)%np;   }( R9 |6 H# \. O
　　while(k1!=i && vl[k1].y==w.y) 0 ]- |, n0 ?6 T* s$ g
　　k1 = (np+k1-1)%np;
　　k2 = (i+1)%np; ! t) E: {- S2 u- A; i( _: }
　　while(k2!=i && vl[k2].y==w.y) ! L# n! o; h5 `9 @0 V2 ^/ N5 a
　　k2 = (k2+1)%np; / e  S' I) r; K. f6 O" u! C6 e
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) / b+ p" R9 q* G6 b
　　C++;
6 y8 i/ h2 C& [5 |" p　　if(k2 <= i)
7 V- F' n5 S1 g+ `$ f　　break; * U" w" m( y' n" W* C% f* w7 G
　　i = k2;
' W  k. ^, L* [; B4 I　　}
1 j4 D) M3 O& B. M2 J  T8 E　　} + a% D. ?( \4 k9 @0 g
　　return c%2;
5 X% i" M- y3 J% E  {, E　　}
: }( k5 B$ C' p! O/ y
( k/ H- c  d" H% m* o
! ]0 d! \6 y& o4 p% [　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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