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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。
* X/ j' S& D, O
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。
" `: T9 Z2 e7 [  N7 n
　　首先定义点结构如下：

以下是引用片段：
　　/* Vertex structure */ ! h6 u$ G& v. @9 I
　　typedef struct
　　{
　　double x, y;
　　} vertex_t;

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

以下是引用片段：
　　/* Vertex list structure – polygon */
　　typedef struct ) l1 D9 @( |9 o; s
　　{ 3 b$ f1 N& T& y! k
　　int num_vertices; /* Number of vertices in list */ 9 C+ `" _2 K2 I3 {. O. w
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t;   ~- O% c  q' P; ^8 K* \
$ P' F, x% h7 C0 S  ~" \

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

以下是引用片段：- {' M% |0 T# P3 g0 p& x" V
　　/* bounding rectangle type */ . S8 @. |5 N( q
　　typedef struct 8 q' Q. ?$ M/ C/ V, D" G. `
　　{
　　double min_x, min_y, max_x, max_y;
　　} rect_t; ' G7 y# a, A, w4 u
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ )
　　{ 0 v! K9 e0 p- G" `
　　int i;   y$ k$ O+ I6 c) h# o: O# L, {
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; & }' ^! M1 B/ l
　　}else{ 9 @8 t( ?  S$ P
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ , n; b2 ^) _+ s: l2 ?! k: A* s
　　} 3 l% s9 r1 H4 a$ {, v, L0 t
　　for(i=1; i
　　{ % C  i( t+ u8 i& m9 R
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
" D; h  v9 U( q　　if(vl.y < rc->min_y) rc->min_y = vl.y; 2 D' t$ D- }2 r# N
　　if(vl.x > rc->max_x) rc->max_x = vl.x;
9 `- x" X: g8 _2 e6 d; V2 N# w6 P　　if(vl.y > rc->max_y) rc->max_y = vl.y; . H/ I0 y1 R4 S0 L+ b7 r
　　} . J6 n; V& v# x+ F  w5 T* M, s* k
　　} ! r$ Z; `$ i+ x* e1 O
- N" A0 _/ D) [8 ?" H, `0 r
! _4 P7 f, M8 G. Y- {0 d$ d; ]
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。( k( x" S+ k: L3 m- D1 p
! a9 v5 c2 b4 g- {3 n
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：/ z- f  D0 l* C4 Z2 u! U

% }; n. w" h; }% E& b, @　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
2 D. t% ~5 u9 h8 s2 s6 Y
: W0 C: L7 N# L# V8 @7 F3 P2 Z( {　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;9 w6 W! b, z, y) n" Q# K* F

8 R, q. W) V' }, j* Q以下是引用片段：5 @" h/ `; g7 o, ?7 a" U2 b+ C
　　/* p, q is on the same of line l */   m) M* G) C8 j$ [/ m6 G
　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
7 l2 H, Q  ?, C. z　　const vertex_t* p,
; O1 _; w4 I; D　　const vertex_t* q)
. G7 S8 w+ j2 `　　{
6 K8 |5 ]( I' m　　double dx = l_end->x - l_start->x; : F2 u2 e2 {2 b, Z3 O
　　double dy = l_end->y - l_start->y; 0 U/ ^. `% I' e
　　double dx1= p->x - l_start->x;
7 p, u) W/ f+ p- Y1 H9 M3 E9 z$ e　　double dy1= p->y - l_start->y;
7 @9 `2 L4 x6 B4 }! f$ n　　double dx2= q->x - l_end->x;   }7 K+ _" r. C; R. k! i3 w
　　double dy2= q->y - l_end->y; - J: B3 f/ z& V: @! H" Y4 `9 z
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); + K6 A2 E& C8 n! C0 M7 v0 Z
　　} - N6 p# z, b# d8 B+ O3 B
　　/* 2 line segments (s1, s2) are intersect? */
7 H" k0 F% Z9 A/ |+ p　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, 2 ~/ g( ^) S4 h$ A
　　const vertex_t* s2_start, const vertex_t* s2_end)
4 w, N# S/ u3 L" g0 r, }  w6 ~# `　　{
, F: Y& w1 @. i1 Y　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && 2 y' z5 |9 d$ _4 [2 D. P4 m
　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; . k$ U1 O8 h8 n# m+ e
　　}
# x0 X( G' A$ T5 `, X8 h, c# e1 Y: v% B- S" {% s' a

3 N% U8 _, h7 o$ U. v- F　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：: U- ?. S2 }& n+ w+ C$ P7 s+ a

7 W* U- N1 L) y2 N/ H以下是引用片段：
: H- ?( Z8 P( _　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ 4 V+ [% Z9 r  M% u% g8 T1 g
　　const vertex_t* v) 8 }. x! {- e& |6 H
　　{ - O; p9 T, y4 R7 N8 i+ I
　　int i, j, k1, k2, c;
& D/ r4 o% S$ E6 a0 W5 l" K/ O　　rect_t rc; " D$ ^! V6 {; e1 Q6 ~2 M' \$ f
　　vertex_t w; : t" U7 B, _6 u  B' p# y
　　if (np < 3)
5 {( s* S; X7 b$ n% z4 k# A# P8 f　　return 0; 6 f& D4 o) C3 c- t9 o
　　vertices_get_extent(vl, np, &rc);
2 x0 P9 \2 _* h* s4 @　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) * A6 Q+ N$ Z- c
　　return 0; 1 ~5 n1 i- N5 u' T3 ^% u! F2 @, r1 S
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ 0 w/ c* s) b0 S( v3 F
　　w.x = rc.max_x + DBL_EPSILON;
% u6 e# P' w+ F3 J　　w.y = v->y; % h+ ^( }  [4 a% b3 |' K+ o9 B, Y
　　c = 0; /* Intersection points counter */ ' }' p& T5 [, N  t9 l- V- E
　　for(i=0; i  2 L' J2 ^3 [% h! d* f
　　{
; ^  g/ D' C$ c. ]: `　　j = (i+1) % np;
6 J2 A! `% h2 k' H+ E! b3 X/ r8 }2 v; r　　if(is_intersect(vl+i, vl+j, v, &w)) ! N- L/ ^# \: {
　　{
6 U) P1 B0 _* d1 y# c6 ~' _  M' T　　C++;
7 W/ c8 f2 b5 J* k+ v* |　　} $ M6 |. X- c4 \3 x
　　else if(vl.y==w.y) ( v" i0 K/ H% b
　　{ . a" W* t6 q+ H
　　k1 = (np+i-1)%np;
: k8 V( X6 C& x3 T　　while(k1!=i && vl[k1].y==w.y)
　　k1 = (np+k1-1)%np; ; ^. V2 E9 j& ~5 i" V
　　k2 = (i+1)%np;
0 s, ~& n! ]9 d4 d　　while(k2!=i && vl[k2].y==w.y) ) Q- r( u4 S. }2 a
　　k2 = (k2+1)%np; + B- Y+ X2 Z9 q! S
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) 9 c9 g: ]  t" L3 m  ?/ G  v
　　C++;
( N" `2 [- ]% Q; K　　if(k2 <= i) 9 O+ r7 O) L% t4 w; [' U! b; i
　　break;
% j$ F$ d: t8 J5 G" {　　i = k2;
, P6 w" S% t9 R. G$ N8 w　　} 1 F8 x3 }2 L- s* P8 d, E1 y! n
　　}
4 J3 l2 Z9 c- i7 m　　return c%2; & I0 r# b0 E1 O4 P6 G$ ^
　　}
& R' g  e3 z) R5 J. E3 H7 O8 r* C0 N( j3 d; g1 z

8 n) Q. U' I  p3 z　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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