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

本文是采用射线法判断点是否在多边形内的C语言程序。多年前，我自己实现了这样一个算法。但是随着时间的推移，我决定重写这个代码。参考周培德的《计算几何》一书，结合我的实践和经验，我相信，在这个算法的实现上，这是你迄今为止遇到的最优的代码。
0 t- x! |3 g& c2 }
　　这是个C语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实现这样一个算法的时候，想在网上找个现成的，考察下来竟然一个符合需要的也没有。我对自己大学读书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下BLOG的点击量。

　　首先定义点结构如下：

以下是引用片段：
　　/* Vertex structure */   [: a3 M# [3 h) N
　　typedef struct
　　{   x) G% C" [8 L4 e
　　double x, y;
　　} vertex_t;
9 F8 v5 N: p: Q7 b: @, V0 Y. f

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

以下是引用片段：
　　/* Vertex list structure – polygon */
　　typedef struct 9 F7 q; T& L# ]* n# y0 p# f& ^
　　{
　　int num_vertices; /* Number of vertices in list */ , B* Z( M/ o  K8 h% T6 x
　　vertex_t *vertex; /* Vertex array pointer */
　　} vertexlist_t; 7 J2 X( T/ A8 }8 t& _0 s

+ J- W$ M4 k- O& W6 s& Q( o- @
　　为加快判别速度，首先计算多边形的外包矩形(rect_t)，判断点是否落在外包矩形内，只有满足落在外包矩形内的条件的点，才进入下一步的计算。为此，引入外包矩形结构rect_t和求点集合的外包矩形内的方法vertices_get_extent，代码如下：7 H6 [6 U4 T( E+ o* ?' o' Y
: o7 P1 h! }# z9 y0 v" p
以下是引用片段：
　　/* bounding rectangle type */ $ G' H- f+ J9 @* C6 f
　　typedef struct ) [4 \" P2 d2 u: J( i. g
　　{ + l- k& M& ~* V, p3 \- i$ m$ }
　　double min_x, min_y, max_x, max_y;
　　} rect_t;
　　/* gets extent of vertices */ 9 O( h4 I2 G% r0 S
　　void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
　　rect_t* rc /* out extent*/ ) 2 ]. @& Z' T% B5 ?- f
　　{
　　int i;
　　if (np > 0){ % E) k/ {* k1 I- E
　　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  6 P' I, M2 R3 D* j
　　{
　　if(vl.x < rc->min_x) rc->min_x = vl.x;
; `1 F9 ?& H6 x* ?　　if(vl.y < rc->min_y) rc->min_y = vl.y; ( A) V9 |1 e$ Q; [7 H; p
　　if(vl.x > rc->max_x) rc->max_x = vl.x; # s( W9 e2 C4 r' d  A) ?, d" B
　　if(vl.y > rc->max_y) rc->max_y = vl.y;
0 Z, G& c0 b: c9 M  c　　} ' y" G7 _. b9 U
　　} / Q& C' d  k1 }2 l- D7 b' z! h$ U) ^

6 {0 v% B# X9 P5 m* T6 ~9 j" k# r- }5 v( G1 d
　　当点满足落在多边形外包矩形内的条件，要进一步判断点(v)是否在多边形(vl：np)内。本程序采用射线法，由待测试点(v)水平引出一条射线B(v，w)，计算B与vl边线的交点数目，记为c，根据奇内偶外原则(c为奇数说明v在vl内，否则v不在vl内)判断点是否在多边形内。' Z# d3 I' F9 Y9 s" q+ z
8 Z3 ^) p2 A' b0 F; Z4 N
　　具体原理就不多说。为计算线段间是否存在交点，引入下面的函数：9 U/ Y$ x: J" n9 j

8 G$ W- e( B2 L) }- b　　(1)is_same判断2(p、q)个点是(1)否(0)在直线l(l_start，l_end)的同侧;" F) R9 g' Q. C7 Z9 C( T

/ j4 v1 Y  f! I! p3 y: q　　(2)is_intersect用来判断2条线段(不是直线)s1、s2是(1)否(0)相交;1 k. x7 T4 B" q0 Y( g

, O+ R8 v7 u2 J+ n. g4 p, i# V$ m: ?以下是引用片段：
9 f' v4 f( a5 ~) p　　/* p, q is on the same of line l */
: c: ~7 D, k5 h　　static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
. n7 R: w8 d! z* Y　　const vertex_t* p, # E6 v: `2 j& v8 U3 b9 z0 R
　　const vertex_t* q)
0 i; H' ^  e6 d& W8 ?9 A( V8 g　　{ 2 C- z' L. m' S" {( L. Z) A
　　double dx = l_end->x - l_start->x; / R1 V* E  {; V. O# m. ~' q: {
　　double dy = l_end->y - l_start->y;
8 Z/ P- u1 a5 ^/ b, R% Z　　double dx1= p->x - l_start->x;
0 n. F/ Q2 B5 D6 `　　double dy1= p->y - l_start->y;
/ _9 H* P% N- T2 S% K, A　　double dx2= q->x - l_end->x;
  k# R# ~) `  m- Z/ j　　double dy2= q->y - l_end->y; # [5 n/ ~! n: t6 L: \& f" {
　　return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
4 \* V$ L7 v# q/ Z$ U! m- `3 @7 d　　}
  }: [. T5 s8 u! q& o　　/* 2 line segments (s1, s2) are intersect? */
1 ~8 K( W! X& z2 C/ G　　static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end,
5 S& }7 n) y' ^% e9 b  _9 l　　const vertex_t* s2_start, const vertex_t* s2_end)
* O) v& U' |% k, m3 I　　{
. o( L' h0 ~% p$ }/ X% ]　　return (is_same(s1_start, s1_end, s2_start, s2_end)==0 &&
, x3 w( o' Z, T' i# i7 X　　is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
& `" @1 B& c* u! R* n　　} 9 y" }* r9 c% s. W( t' d1 Q

) [2 U2 I% s; X) D& A% B8 ?7 {0 w' ?, {$ S
　　下面的函数pt_in_poly就是判断点(v)是(1)否(0)在多边形(vl：np)内的程序：
4 \- q$ c! p% B: D9 i2 I6 Q+ \+ o" J8 K/ V/ S3 V' O
以下是引用片段：
  o4 }! ^/ S  d: J( A, V5 @　　int pt_in_poly ( const vertex_t* vl, int np, /* polygon vl with np vertices */
% @" Y5 G) ~2 f　　const vertex_t* v)
" f; ~, P; V+ p　　{
" c. {1 S: m1 c: z　　int i, j, k1, k2, c; + `: e& e0 U- @% W
　　rect_t rc;
3 b/ J5 _6 n2 A; d　　vertex_t w;
8 |, I# }1 C- e. k% N　　if (np < 3) 5 J& L& Y8 S. ^( |) @' o) t
　　return 0;
7 M+ W" N3 j& O5 i- q" O2 z+ X　　vertices_get_extent(vl, np, &rc);
$ o5 ~# N! }! w6 m% a　　if (v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y)   U2 g2 {6 j" F
　　return 0;
8 x- O: q$ _  f9 ?: s3 R& H　　/* Set a horizontal beam l(*v, w) from v to the ultra right */
5 y+ k8 Q: r& i$ v4 {* A4 z　　w.x = rc.max_x + DBL_EPSILON;
7 o7 @% S2 j! [　　w.y = v->y; : @, ^' w" ]* R  U  C( o
　　c = 0; /* Intersection points counter */ " |% V1 t" ?3 _: a8 r" e* O+ C/ o
　　for(i=0; i
7 {0 P, @% W& |2 x2 E" d# _　　{
& e% f' C$ }/ P2 F　　j = (i+1) % np; % t+ v$ F+ {( ]* P9 G% Y
　　if(is_intersect(vl+i, vl+j, v, &w))
' O/ n# h  y5 z4 c) K4 D% w1 l　　{
" n& q) I1 S; q! O' l6 J　　C++;
& Z" a$ g! l- l9 D4 R( T" s$ N　　} 4 d* P& D. |" T' B
　　else if(vl.y==w.y) ) ~8 u4 r8 z% h. ^/ k; _# N( @' m
　　{
, H. q$ Z; ~2 \8 p# E　　k1 = (np+i-1)%np; / v, n) e# z# A5 Q2 \! e# B: h
　　while(k1!=i && vl[k1].y==w.y) % W: @( O' B6 c) |  [
　　k1 = (np+k1-1)%np; : M! T* n7 |  B3 }: n& T4 A- c
　　k2 = (i+1)%np;
8 i6 }0 }5 F' f7 \　　while(k2!=i && vl[k2].y==w.y) ; R2 C# ?& V) A+ N0 k$ M
　　k2 = (k2+1)%np;
6 Z1 D3 d# [0 U3 P( \" P+ C　　if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
" h& o# i5 N! `( |7 c6 F　　C++;
  v: s6 L! j, n: L0 n　　if(k2 <= i) $ |: u* n7 \8 d8 r# ]
　　break; 7 B5 Y4 {0 S. ]) L' w2 W
　　i = k2;
8 i+ v  @. ?3 D' a3 J, h0 F　　} . r- O* T; ~4 s* ]
　　} 3 I! l- E# v3 R* S/ z$ z0 X
　　return c%2; ) B" R% V3 H# {- }7 k0 I5 C
　　} 9 D; B% J6 e' T, S9 u8 F' e
8 E1 k# R, n' m6 v
; F9 e3 v1 K+ c7 g7 f
　　本想配些插图说明问题，但是，CSDN的文章里放图片我还没用过。以后再试吧!实践证明，本程序算法的适应性极强。但是，对于点正好落在多边形边上的极端情形，有可能得出2种不同的结果。

返回列表

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

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

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

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

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

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

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