《边方向角长度和点包含算法的改进》由会员分享，可在线阅读，更多相关《边方向角长度和点包含算法的改进（10页珍藏版）》请在金锄头文库上搜索。
1、1 8 6中国科协第二届优秀博士生学术年会论文集边方向角长度和点包含算法的改进丁 健1 ,2 ,3 江 南 ， 苗 材( I .中国科学院南京地理与湖泊研究所2 .中国科学院研究生院北京 3 . 解放军理工大学工程兵工程学院南京2 1 0 0 0 81 0 0 0 3 9南京 2 1 0 0 0 7 )摘 要 对丁健 1 ,2 的 边方向角长度和点包含判断算法提出改进方法。定义了多边形半平面连 续链概念， 建立了半平面连续链整体计算定理， 通过计算连续链两个端点之间的边方向角长度差 值， 直接得到链上各边的边方向角长度差值之和， 从而跨过了中间边的计算， 减少了计算量。给 出改进算法， 算法先
2、对多边形进行半平面连续链划分， 然后以 链为单位， 逐条链整体计算， 最后对 边方向角长度差值进行累加， 用累加值判断点的内外性。分析表明， 改进算法在顶点数大于4 时， 可以 减少计算量， 提高算法效率。 关键词多边形点包含判断边方向角长度边方向角长度和半平面连续链T h e I mp r o v e m e n t o f P o i n t 一 i n一 P o l y g o n A l g o r i t h m B a s e d o n E d g e 一 a z i mu t h一 l e n g t hD in g J i a n t Z 3 , J ia n g N a n
3、 ， R u i T i n g 3 ( 1 . N a n j i n g I n s t i t u t e O f G e o g r a p h y A n d L i m n o l o g y , T h e C h i n e s eA c a d e m y o f S c i e n c e s , N a n j i n g 2 1 0 0 0 8 , C h i n a ; 2 . G r a d u a t e S c h o o l o f t h e C h i n e s e A c a d e m y o f S c i e n c e , T h e C h
4、i n e s e A c a d e m y o fS c i e n ces , B e 巧 i n g 1 0 0 0 3 9 , C h i n a ; 3 . E n g i n e e r i n g I n s t i t u t e O f E n g i n e e r i n g C o r p s , P L A U S T , N a n j i n g 2 1 0 0 0 7 ， C h i n a )A b s t r a c t T h e i m p r o v e m e n t f o r D i n g j i a n t p o i n t 一 i n
5、一 p o l y g o n a l g o r i t h m w h i c h q u e ry a b o u t w h e t h e r a p o i n t l i e s w i t h i n a p o l y g o n o r n o t i s g i v e n . A n e w c o n c e p t , t h e c o n t i n u o u s c h a i n i n h a l f p l a n e i s d e fi n e d , t h e w h o l e c a l c u l a t i o n m e t h o
6、d f o r c o n t i n u o u s c h a i n i s f o u n d e d , w h i c h g e t t h e s u m o f E d g e 一 a z i m u t h 一 l e n g t h o f t h e c o n t a i n e d e d g e s , 场d i r e c t l y c a l c u l a t i n g t h e d i ff e re n c e b e t w e e n t h e t w o e n d p o i n t s . A ll i n - t e r m e d
7、i a t e e d g e s c a l c u l a t i o n i n a c o n t i n u o u s c h a i n a r e o m i tt e d a n d a v i o d e d , t h u s t h e c o m p u t a t i o n t i m e i s c u t d o w n . T h e i m p r o v e d a l g o r i t h m p a rt i t i o n t h e p o l y g o n e d g e s t o c o n t i n u o u s c h a i
8、n s f i r s t , t h e n c a l c u l a t e e a c h c h a i n s E d g e 一 a z i m u t h 一 l e n g t h d i ff e re n c e , a n d a c c u m u l a t e t h e m t o a s u m . B y c o m p a r i n g t h e s u m w i t h 1 6 , 8 ， a n d 0 , w h e t h e r t h e p o i n t l i e s w i t h i n t h e p o l y g o n
9、o r n o t w i ll b e i d e n t i f i e d . A n a l y s i s s h o w s t h e i m p r o v e d a l g o r i t h m i s f a s te r th a n t h e o r i g in a l , s p e c i a ll y f o r c o n v e x p o l y g o n . K e y w o r d s p o l y g o n , p o i n t 一 i n 一 p o l y g o n q u e ry , E d g e 一 a z i m u
10、t h 一 l e n g th , th e s u m o f E d g e 一 a z i m u t h - l e n g t h , c o n t i n u o u s c h a i n i n h a l f p l a n e 本研究得到中国科学院知识创新工程领域前沿项目 ( C X N I G L A S - A 0 2 - 0 1 2 ) 资助。 本研究还应用于“ 东南沿海野营供水地理信息系统” 课题中， 该课题获2 0 0 4 年度军队科技进步二等奖。信 息 科 技1 8 71 引言点在多边形内外的判断， 也即点包含判断， 是计算机图形学、 地理信息系统、 科学计
11、算可视化等领域中 的基本问题， 几十年来， 国内外学者针对点包含算法的设计、 改进、 优化等工作从来没有中断过。笔者给出了点包含判断的新颖、 高效算法边方向角长度和算法， 该算法基于相邻的检测点与顶点 连线之间， 边方向角长度差值累加之和为固定值( 0 ， 土 8 n ， 土 1 6 n ， 其中n 为自 然数) 的原理， 适用于简单、 自 交、 含岛和 合并等一般意 义上的 多边形， 在时间复杂 度与执行效率方面 都有先进之处f .z l 。 文献 1 , 2 1 算 法主要耗时部分是每条连线的边方向角长度计算， 每对相邻连线间的边方向角长度差值计算， 以及累加 计算。本文的研究找出了无需计
12、算的中间连线， 提出了基于多边形半平面连续链整体计算的边方向角长度 和点包含算法。本文算法可有效地跨越半平面连续链中间连线的重复计算， 专注于对影响点内外性质的 链端点( 顶点) 及其连线进行相关计算。分析表明， 本文的改进正确、 合理， 可以提高算法效率， 在多数情况 下， 改进效果十分理想。2 定义为叙述统一和方便， 给出几个相关的定义。定义1 . 多边形， 简单多边形， 多边形方向。 多边形是一个首尾相连的多边线， 可以用P或顶点序列 p , p 2 . . . p 。 表示， P I p 2 1 . . . I P n _ 1 P . Ap ， 称为多边形的 边。 对给定多边形的n 个
13、顶点， 若对任意i li ( i O J ) I i l - 1 , 2 , 3 , - “ - , n ， 线 段只 P i . ， 与凡 弓 . I 或 是 相 邻 且 相 交于 一 端 点或 不相 交， 则 称该 多 边形为 简 单多 边 形。 对 给定多边形P I 凡. . .P . ， 若沿P , - . P Z . . . P- . P ; 方向 走， 该简单多边形所围的有界区 域总在左边， 则称该多边 形的走向是逆时针的; 反之， 称其走向是顺时针的。定义2 .自 交多边形， 含岛多边形， 合并多边形， 一般多边形。给定多边形非相邻边之间存在一个或一 个以上交点则称为自 交多边形
14、。给定多边形内部存在一个以上空洞则称为含岛多边形。给定多边形由两 个以上互相不包含的简单多边形组成则称为合并多边形。本文将简单多边形， 自交多边形， 含岛多边形， 合并多边形统称为一般多边形。定义3 . 链。多边形顶点序列中连续的一部分连接起来的边集称为链， 链是多边形边集的一个子集， 用符号L m 表示之， 也可以 用顶点序列表示， 如P k p k . I r . . . I 几， . ， 或用符号L k - k . 。 表示， 其中k 为 链的 起始顶 点标号， m为链的边数目。3 边方向角长度和点包含算法介绍3 . 1 边方向角长度定义从检测点出发， 与多边形顶点连线， 此连线可以当作
15、矢量， 有 方向 角属性。 约定以 地图 学中的正北方向 为零方向， 约定从零方 向按顺时针旋转到连线所在射线， 所经过的角度， 为连线的方向 角( E d g e 一 im u t h ) 。定义边方向角长度( E d g e 一二 i m u t h - l e n g t h ) 为: 以 连线起点为中心， 建立边长为2 且边分别平行于水 平和垂直方向的正方形， 该正方形与连线或连线射线存在交点， 从零方向交点沿正方形边顺时针走到该交点的长度， 称为边方向 角长度。如图1 , L N P 是连线O P 的边方向角长度声 ，二 编 + 几 。 + L c e + L E P 。图1 边方向
16、角长度对连线O P ， 其边方向 角长度大小与终、 起点坐标差值A x , 勿 的 符 号 和 取 值 相 关， 本 文中 以E _ a _ l ( O P ) 函 数 表 示 之， 借 鉴Q i ( 二 , Y i ) 函 数 3 ， 用 下 面 的E al ( O P ) 函 数 来 度量该长度:1 8 8中国科协第二届优秀博士生学术年会论文集妙妙吵城晒砂砂 +一十+- 02244矛b尹0E - a 一( 口 尸 )8 + A x l d y( 勿 0 ) n( 公 0 ) n ( A y 山)( 勿 0 ) n ( A x 0 ) n ( A y S d x ) ( 勿 0 ) 八( O x 一 a y ) ( 勿 0 ) A ( A x 一 勿) ( 勿 4 x ) ( 匀 0 ) 八( 山 0 ) n ( A x :s 0 ) n ( A y 一 二 )rfl.lleeeel吸.esL-工其中A x 二 P . 二 一 0 . x ; A y 二 P . y 一
