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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。
, ?7 L, n% y9 J" V* G3 q; g: G
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。, \+ f3 L( z7 D- ~1 o
' K  T( M5 K# d( P
　　首先定义点结构如下：. ~" k  j0 z+ L& j

以下是引用片段：2 o: }& ?  i5 ]3 v
　　/* Vertex structure */ 4 q: G4 V, l1 k, \0 q1 j
　　typedef struct
　　{
　　double x, y; , q! d, x+ d* l9 n. G
　　} vertex_t;

　　本算法里所指的多边形，是指由一系列点序列组成的封闭简单多边形。它的首尾点可以是或不是同一个点(不强制要求首尾点是同一个点)。这样的多边形可以是任意形状的，包括多条边在一条绝对直线上。因此，定义多边形结构如下：- a% A5 n' j( M- }$ M
$ r( H" J5 [( h) Q+ G( F7 ?0 S* L
以下是引用片段：2 q( F7 ?7 S3 J7 k
　　/* Vertex list structure – polygon */ / ]0 W) n( ^  K
　　typedef struct
　　{ ; n" y5 O- T# I
　　int num_vertices; /* Number of vertices in list */ , r( q7 p9 g. x% r# h+ A! [
　　vertex_t *vertex; /* Vertex array pointer */ & {: _& B" U7 H- ]/ [* f  A0 `. J
　　} vertexlist_t; 0 h# _8 w  j# a, I$ w/ X9 t  j$ S
$ c  C6 _8 ]! H# u/ u; c. |* D

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

以下是引用片段：' A7 s2 k4 `; g- m+ l
　　/* bounding rectangle type */
　　typedef struct
　　{
　　double min_x, min_y, max_x, max_y;
　　} rect_t; / E: ^+ n7 D, A) P9 H/ i* [( m3 P
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ ) 8 G# b* V9 E( P! t3 W$ ]0 D
　　{ . K+ b  o1 L0 k: z& V, ?6 }5 |
　　int i; 7 A# h$ J! b. A/ K6 d# u
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
　　}else{
　　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; 7 L- D8 H$ x/ p6 T4 I7 [0 ~" b
　　if(vl.y < rc->min_y) rc->min_y = vl.y; : g4 z6 ^- }% {' ^; U5 Y* x+ z
　　if(vl.x > rc->max_x) rc->max_x = vl.x; 8 S- t# T. E9 n4 g4 f
　　if(vl.y > rc->max_y) rc->max_y = vl.y; % b5 W2 D; c( `
　　}
# z( O! `/ a7 e- u# r' A　　}
/ _. p( {2 r7 @# _" ^* U' d. D% G2 l( k. V9 ]2 U

1 E  t$ |- K% F　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。" `3 P( V  z/ l9 j4 x% K
6 n0 t6 R2 @4 ?# `- d
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：
8 {/ y* [, U4 z# O5 K- I0 q* k1 h
; [7 G- Z1 }8 _, X　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;; @( N# ]+ j9 \2 w9 g
% b; N. n1 f" Q) F( o; W0 v
　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;, a. J0 J4  ?4 N
2 N4 W* h% O; S& X$ L
以下是引用片段：
/ l3 ?, u% F( ^4 W. a* W# B) D　　/* p, q is on the same of line l */
" c& ]/ k# X7 Q4 }" k2 U　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
/ S% d4 ~$ V/ S5 i( O+ R　　const vertex_t* p, 4 G0 H4 t) \; Y! k: H# e1 c
　　const vertex_t* q)
; A/ b" E6 X+ o1 m* I　　{ " t" s$ I4 E( n0 T
　　double dx = l_end->x - l_start->x; 6 X7 B. @2 ?  O. V0 K
　　double dy = l_end->y - l_start->y;
$ A6 W# j: d' N% O6 u　　double dx1= p->x - l_start->x; 1 X4 r, `3 {* }. v3 B* w9 T  o4 E$ d
　　double dy1= p->y - l_start->y; 9 M7 U' c. g' x# h
　　double dx2= q->x - l_end->x; ( f: Q) r7 ?$ r( l7 E& z
　　double dy2= q->y - l_end->y;   Z' T, z3 h; l( ~
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0); 2 X5 k+ l/ M) Q
　　} ( D- Y$ v9 Q! x4 P* U, w* p8 \
　　/* 2 line segments (s1, s2) are intersect? */
3 }# `# p. a# A! y　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, ' J! c" h6 q1 d: A) [$ i; q
　　const vertex_t* s2_start, const vertex_t* s2_end)
$ \7 W1 B5 r9 a; F) Z　　{ 5 P6 D! c7 X+ G3 ?( [" B  e% s
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && 9 ^! s/ {; h$ y7 V
　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
6 u$ k5 m6 R' s$ O  N　　}
# R3 ~% q3 ?  T% U& O+ F8 F
5 {3 o. x* l7 M% W. h: w$ Q
; D! `+ k3 |" ]. f9 P& [. B　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
2 h, v) F8 z" ?5 J  K( E' t( z) D" O) `9 T) ~$ j
以下是引用片段：
3 K/ O8 ]- h$ ~7 W! D3 K' c# i　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
2 p1 u8 |0 c7 ]4 n　　const vertex_t* v)
0 O* _+ f3 U2 y+ m　　{
) x- W/ J; c8 |6 T; |0 Z0 o　　int i, j, k1, k2, c; 4 i1 i7 M0 Q2 p- Y% A4 O
　　rect_t rc; " E& \% U7 ~4 ?- ]& E
　　vertex_t w;
( w% j  [1 ~. H8 r1 y　　if (np < 3)
9 J- v+ G2 @1 ]　　return 0; $ r4 Z2 \) `1 X5 r+ W# S8 R& e
　　vertices_get_extent(vl, np, &rc);
0 t" j/ y1 i0 w+ g( U( k/ f　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
/ z0 f; }4 `8 P$ e- D　　return 0; 4 ^. ]. }+ A8 r: t
　　/* Set a horizontal beam l(*v, w) from v to the ultra right */ 5 l, G* {9 Q/ g' D
　　w.x = rc.max_x + DBL_EPSILON;   e" Z# d6 A! \/ ^' j
　　w.y = v->y;   F  {( O) T( k8 R
　　c = 0; /* Intersection points counter */ 5 E. R6 H9 I8 e9 ?( O! K7 u
　　for(i=0; i
( Y- {* U, U% b7 ]8 m　　{ 0 p3 d% c9 j: A' E  f
　　j = (i+1) % np; + c4 \# n) z4 P3 n  {
　　if(is_intersect(vl+i, vl+j, v, &w)) : R# C6 B' A4 t# m
　　{
6 t" C. a4 W  e8 B! d' ~　　C++; 3 o/ Y/ Z7 V9 z* Y8 E
　　}
2 S4 B% S2 j1 e' E  t( d; i　　else if(vl.y==w.y)
$ e  ^( d( n0 R% v& {　　{
6 e' B8 p+ `: E0 ]5 b7 |　　k1 = (np+i-1)%np;
* s. S4 q3 k8 d: ]; ?1 Y　　while(k1!=i && vl[k1].y==w.y) ; X9 `" \$ k5 G4 N
　　k1 = (np+k1-1)%np; ) h$ F1 r$ O( V# E, ~/ G
　　k2 = (i+1)%np;
7 ^) V# W- `& ?5 z' h: k　　while(k2!=i && vl[k2].y==w.y) ; c% g) l  v" R& f3 u
　　k2 = (k2+1)%np; & r$ \0 M% \  {8 \" J
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) / U% w% a$ I+ }# ^
　　C++; $ r! Y. ^2 Q4 S0 }( g# T
　　if(k2 <= i)
6 q) t& z8 W: o( N2 S　　break; 8 @5 \! m/ d' o, ]
　　i = k2; ; s: ~6 Z* g, \) [5 c
　　} / w6 J4 D/ y# F( X
　　}
, X/ Z8 R# a# G. X8 y　　return c%2;
2 F4 m* E8 R! a, J  F6 X　　} & c( D! G, c( V+ L) `! [* r4 Q& F

# z0 c/ ^2 I' v) ^0 N4 F' ?' J2 ?$ A. c# ?+ S8 d
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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