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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。/ H# y6 u- N+ a& \3 e
1 s. p6 N: S  S1 i+ P  Q. i. @! X8 l
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。
7 p3 ?2 I$ f  o, H8 n3 J
　　首先定义点结构如下：

以下是引用片段：, h. ~; N% {+ \/ ?% m  V/ _
　　/* Vertex structure */ ) e5 C* f/ O0 W! Y& }8 V3 \- M
　　typedef struct
　　{
　　double x, y; ) B- d. J0 p4 z* l4 b2 E
　　} vertex_t; 6 g/ h2 C! F0 _9 Q% p

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

以下是引用片段：
　　/* Vertex list structure – polygon */
　　typedef struct & L6 d- k" B  e: d( E$ `
　　{ 4 r! U2 S7 ~. E" {
　　int num_vertices; /* Number of vertices in list */
　　vertex_t *vertex; /* Vertex array pointer */ 4 v9 o) D- K4 J3 P
　　} vertexlist_t;
& U3 B) L2 G" V8 u- ]+ f6 B( Y8 N

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

以下是引用片段：8 y* K- O+ h+ W7 m/ y% v5 S
　　/* bounding rectangle type */ ! ]9 N5 E2 ^3 }4 Z: Q4 L
　　typedef struct 4 {3 w" `6 y* e; ~; n+ X
　　{
　　double min_x, min_y, max_x, max_y;
　　} rect_t; # X$ {* D4 v( k# ]8 n" G& z/ L
　　/* gets extent of vertices */
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ )
　　{
　　int i;
　　if (np > 0){
　　rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y; 4 M% u& B  X: b- X# \
　　}else{
　　rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */ + S" z' |0 Y; A
　　}
　　for(i=1; i  # i0 X& a; X8 t
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x; " Z0 o: ]) K" T
　　if(vl.y < rc->min_y) rc->min_y = vl.y; 1 o' Z, D; B2 I! h
　　if(vl.x > rc->max_x) rc->max_x = vl.x; 0 U% H0 r) c8 t  S" Z0 Z
　　if(vl.y > rc->max_y) rc->max_y = vl.y;
4 t, F$ z+ }# n1 L: T: ?  D　　}
$ @& t5 u2 g3 n2 M+ z* i- K4 @/ B　　} % `6 K+ ?4 s/ |3 O/ ?

  I( d$ w& `! o9 g' [, `
! k9 T& H2 P1 x$ m0 F/ R　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。
9 `" q6 P8 k' r+ V
- ?7 m' w3 w. n1 ~1 a/ a9 v" B$ W　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：- J# I& r7 H0 Y$ ~! T

6 D# o2 V4 A0 {, t　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;
7 k  B% u& Z: e4 o3 U: _0 g  U
* {( n% a* x7 |% [' e; z　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;1 C, W# D- b6 y6 P9 Z1 @# K
# Q- \, v8 o( u# S9 T; ~
以下是引用片段：
9 R1 H- y) P$ D5 ^8 b6 u　　/* p, q is on the same of line l */
2 v( g& B* N: E- N　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
* h0 H; |2 D& w- a+ k　　const vertex_t* p,
- m4 V% B5 [7 \8 \- y% s　　const vertex_t* q) * `' C8 s+ P0 z( ]1 [4 s4 X2 A
　　{ ) [2 Q6 ~) K$ L
　　double dx = l_end->x - l_start->x;
" `+ N4 k% s6 D, @( r　　double dy = l_end->y - l_start->y; / n& }+ Z% `, k: p
　　double dx1= p->x - l_start->x;
, x, u$ T0 [! B$ S% c, ?　　double dy1= p->y - l_start->y;
# `: L: v$ P" @　　double dx2= q->x - l_end->x;
7 B- E2 j. v4 d3 C' E8 J　　double dy2= q->y - l_end->y;
8 B: ]3 W; S$ X4 o( F. r　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
5 j' ?2 z" w) @6 }　　}
7 U# N  ~/ X9 A. l' i　　/* 2 line segments (s1, s2) are intersect? */ ; v  n: ?/ |: F% u" W9 ]. b3 C
　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
" I; C1 ^# B6 E; ]. P: @1 q# f& ^　　const vertex_t* s2_start, const vertex_t* s2_end)
$ I5 Q+ W& M4 [; `. ?: U% [6 l9 I! w　　{ " O; j% R) K( X% q, s0 G$ b
　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
& M# E1 W) q9 h( `: M  a4 ~4 A　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0; ( W2 E& W8 g2 I- b) ]+ _
　　}
4 e: Y# E; D8 N( N8 n( b
) ~1 X5 l0 `! _! K! T1 M# `6 K6 S, {
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
  |7 K! G# W' I
. L3 Z8 v: S/ Y# ]/ p0 F以下是引用片段：
4 U! O5 i7 ^. E7 D　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */ ; j* K& T; k% C! b  J( b4 Q
　　const vertex_t* v)
# y) u+ }4 j6 E0 x) `4 {　　{ : f1 G6 M9 z7 F. H  F6 }& Y! Y
　　int i, j, k1, k2, c; % Z) K2 v4 M  k
　　rect_t rc; # {4 e1 m1 y( X, q
　　vertex_t w;
; c+ t7 d8 Y4 W2 }7 N( k　　if (np < 3)
  ?# v* D3 F9 G" r8 a+ {# U2 T　　return 0;
) W) }1 W/ W* l/ ~　　vertices_get_extent(vl, np, &rc); 7 ^8 e# T' g( P" ^8 z3 u
　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)
& L6 o+ ]# e1 t- T　　return 0;
! g" N* T- v& o5 P8 n9 A　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
# x, y0 [( R# \) w　　w.x = rc.max_x + DBL_EPSILON; 4 P/ a' y& m* z$ {, j; p
　　w.y = v->y; 0 n# t5 G7 F8 K3 K" N( S
　　c = 0; /* Intersection points counter */
- X" }& ~; Y9 V* j2 C& o3 D* r　　for(i=0; i  : [; v6 t* ]0 K' D* ~( r
　　{
+ D9 n. v, `; W$ i6 s% ~% d' q　　j = (i+1) % np;
  z* c4 r* i& c; ~9 R2 \　　if(is_intersect(vl+i, vl+j, v, &w))
4 Q1 w3 W- t3 E, C8 z# U4 K: v　　{ - t: T! u% `* [* \. ~1 Z. y
　　C++; 7 V8 Y: E: q8 |1 Y8 e3 s
　　} 6 {5 `% y3 p$ D
　　else if(vl.y==w.y) 6 l2 s$ Y5 W0 ^
　　{ * f# f& T7 v3 m& Z* q! _: C1 K5 G
　　k1 = (np+i-1)%np; # f; a7 E  Y( f
　　while(k1!=i && vl[k1].y==w.y)
% |6 ]9 x; A% |9 M: t　　k1 = (np+k1-1)%np;
! J+ L$ r* Y9 S6 U* S3 Y$ v$ ?　　k2 = (i+1)%np; 9 t9 ?0 `5 q/ G. H* A) W# P
　　while(k2!=i && vl[k2].y==w.y)
) p4 N2 J8 p2 x4 o　　k2 = (k2+1)%np; ) q" J( k! |3 X1 F1 R  P% u. Y+ r
　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0) ' h- y+ I6 s. h, I5 J
　　C++;
: c( `# Q- `( v　　if(k2 <= i)
. m$ G0 W+ V& s" f2 ~　　break;
: V7 {) S6 m- f+ V' ]0 [　　i = k2;
1 ]  s1 w* E9 U! B; S　　}
, p3 V) k1 B4 k( S0 j5 i$ {) ^　　} & \$ j4 q8 q: J/ X8 O5 d1 W
　　return c%2;
% m: R% A. |) `6 j　　} 5 F% @4 N" k5 O

8 x8 {. B9 [' G
, M# }, t( c* h$ _* k　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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