基于网格与R-树空间索引的矢量线图任意简单多边形窗口裁剪算法

J4 ›› 2012, Vol. 34 ›› Issue (11): 96-103.

基于网格与R-树空间索引的矢量线图任意简单多边形窗口裁剪算法

李楠1，吴信才2，马金金3，王中

(1.中国地质科学院矿产资源研究所,北京 100037;2.中国地质大学(北京) 地球科学与资源学院,北京 1000833.中南大学信息科学与工程学院,湖南长沙 410083;4.合肥工业大学资源与环境工程学院，安徽合肥 230009)

收稿日期:2011-09-21 修回日期:2011-11-22 出版日期:2012-11-25 发布日期:2012-11-25
基金资助:
国家自然科学基金资助项目(41002119);国家863计划资助项目(2006AA06Z114 );国家科技支撑计划(2006BAB01A01);中央国家机关基本业务费基金项目

A Line Clip Algorithm of Based on Cell and R-Tree Spatial Indexes against Arbitrary Polygon Window

LI Nan1,WU Xincai2,MA Jinjin3,WANG Zhong4

(1.Institute of Mineral Resources Chinese Academy of Geological Sciences,Beijing 100037;2.School of the Earth Sciences and Resources,China University of Geosciences,Beijing 100083;3.School of Information Science and Engineering,Central South University,Changsha 410083;4.School of Resources and Environments,Hefei University of Technology,Hefei 230009,China)

Received:2011-09-21 Revised:2011-11-22 Online:2012-11-25 Published:2012-11-25

摘要/Abstract

摘要：

针对大规模矢量线与大量裁剪窗口同时出现的线裁剪算法存在的三个主要问题，减少线段求交次数、简化交点出入属性计算以及无交点矢量线的取舍，本文提出了一种基于双空间索引的大规模线图任意多边形裁剪算法。算法根据裁剪多边形的边分别建立R树索引和均匀Cell索引,应用两种索引各自的优点大幅减少被裁剪线段与裁剪多边形上线段的求交次数。在此基础上，基于均匀网格索引，提出局部射线法，简化交点出入属性计算和无交点矢量线的取舍。本文在传统算法基础上提出三点改进：首先提出基于两种空间索引模型进行线段求交计算，保证算法在理论上具有较低的时间复杂度；其次，在射线法和网格索引基础上提出局部射线法，使得判断每个交点出入属性的时间复杂度为O(1)~O(〖KF(〗n〖KF)〗),与参考文献中的算法相比，此方法的优点是避免判断多边形上顶点的方向；最后，算法中裁剪多边形可以是包含任意多个洞的任意简单多边形，克服传统算法中对裁剪多边形的特定约束条件。

关键词: R-树, 网格索引, 线裁剪, 局部射线法

Abstract:

There are three main problems in line clip:reducing the number of segments intersection,reducing the time complexity for computation property of intersections and determining whether nonintersection lines is in clip polygons.This paper presents an improved line clip algorithm against general polygon window.The algorithm uses RTree and Cell structures to calculate segment intersections between segments in lines and segments in polygon edges.Then,based on uniform subdivision,a method named local radial is introduced in order to reduce the time complexity for pointinpolygon.The algorithm has three improvements.Firstly,segmentintersections of two spatial index structures can be calculated simultaneously.Secondly,a ‘local radial method’ is presented to reduce the time complexity for computation property of intersections,whose time complexity is,and the method avoids judging the orientation of clip polygons.Finally,the algorithm can be used in the clipping window that is general polygon.

Key words: R-Tree；cell index；clipping line；local radial

李楠1，吴信才2，马金金3，王中. 基于网格与R-树空间索引的矢量线图任意简单多边形窗口裁剪算法[J]. J4, 2012, 34(11): 96-103.

LI Nan1,WU Xincai2,MA Jinjin3,WANG Zhong4. A Line Clip Algorithm of Based on Cell and R-Tree Spatial Indexes against Arbitrary Polygon Window[J]. J4, 2012, 34(11): 96-103.

[1]	许凯,杨萌. 移动对象的反向k近邻查询算法的研究[J]. J4, 2013, 35(1): 149-154.
[2]	甘亮1,2,于莉莉3,李润恒1,贾焰1,金鑫4. 一种基于逆支配点集的数据流Top-k计算方法[J]. J4, 2012, 34(6): 59-64.
[3]	张丽，邹鹏，贾焰. 基于网格的数据流连续约束Skyline处理技术研究[J]. J4, 2011, 33(8): 173-180.
[4]	田李李爱平邹鹏贾焰. 更新数据流上的连续Skyline计算[J]. J4, 2008, 30(5): 59-64.
[5]	韩明峰李传林. 韩明峰李传林[J]. J4, 1999, 21(3): 45-48.