基于Voronoi图的方向区域查询方法

doi:10.3778/j.issn.1002-8331.2105-0481

摘要/Abstract

摘要： 针对空间中方向区域查询效率不高的问题，通过引入Voronoi图，利用其特性对数据空间进行划分，提出了基于Voronoi图的方向区域查询方法。该方法在基于Delaunay三角网生成的Voronoi图索引结构基础上，将首结点与查询对象连线形成有向线段，利用Voronoi图可以通过邻接生成点延展的特点确定查询对象的位置，通过判断空间对象与查询区域的位置关系，将相应关联数据点加入候选集，并判定该数据点是否为正确结果，从而得到查询结果集。理论研究和实验结果表明，该方法在确定查询点位置的过程中有效减少了非必要数据的访问，在过滤阶段大大减少了候选集中点的数量，从而提高了空间数据的方向区域查询效率。

关键词: 方向区域查询, Voronoi图, Delaunay三角网, 索引结构, 开放区域

Abstract: In order to solve the problem of low efficiency of direction region query in space, Voronoi diagram in computational geometry is introduced to divide the data space, and a direction region query method based on Voronoi diagram is proposed. This method is based on the index structure of Voronoi diagram generated by Delaunay triangulation. Firstly, the first node is connected with the query object to form a directed line segment, by using Voronoi diagram, the location of query object can be determined by the feature of point extension generated by adjacency. Then, by judging the location relationship between the spatial object and the query region, adding the corresponding related data points to the candidate set, and determining whether the data point is the correct result, it gets the query result set. The theoretical research and experimental results show that this method can effectively reduce the access of unnecessary data in the process of determining the location of query points. In the filtering stage, the number of candidate points is greatly reduced, thus the efficiency of direction region query of spatial data is improved.

Key words: direction region query, Voronoi diagram, Delaunay triangulation, index structure, open region

刘润涛, 董庆宇, 吴昊天. 基于Voronoi图的方向区域查询方法[J]. 计算机工程与应用, 2022, 58(8): 83-89.

LIU Runtao, DONG Qingyu, WU Haotian. Direction Region Query Method Based on Voronoi Diagram[J]. Computer Engineering and Applications, 2022, 58(8): 83-89.

参考文献

[1] PAPADIAS D，THEODORIDIS Y，SELLIS T.The retrieval of direction relations using R-trees[C]//Proc Fifth Conf Database and Expert Systems Applications（DEXA），1994.
[2] HEODORIDIS Y，PAPADIAS D，STEFANAKIS S.Supporting direction relations in spatial database systems[C]//Proc Seventh Int’l Symp Spatial Data Handing（SDH’96），1996.
[3] SHEKHAR S，LIU X，CHAWLA S.An object model of direction and its implications[J].Geoinformatica，1999，3：357-379.
[4] LIU X，SHEKHAR S，CHAWLA S.Object-based directional query processing in spatial databases[J].IEEE Transactions on Knowledge and Data Engineering，2003，15（2）：295-304.
[5] 肖予钦，张巨，景宁，等.基于R树的方向关系查询处理[J].软件学报，2004，15（1）：103-111.
XIAO Y Q，ZHANG J，JING N，et al.Direction relation query processing using R-trees[J].Journal of Software，2004，15（1）：103-111.
[6] 张泽宝，张健沛，李若愚.R树的方向查询精过滤方法[J].哈尔滨工程大学学报，2010，31（11）：1490-1495.
ZHANG Z B，ZHANG P J，LI R Y.A fine directional query filtering method with an R-tree[J].Journal of Harbin Engineering University，2010，31（11）：1490-1495.
[7] LIU R T，WANG Y M，ZHAO Z G，et al.The new strategy of object-based directional query[J].International Journal of Database Theory and Application，2014，7（6）：55-62.
[8] WEI H L，TAN X J，LIU F J，et al.A new directional query method for polygon dataset in spatial database[J].Earth Science Informatics，2015，8（4）：775-786.
[9] 刘润涛，赵振国，田广悦.连续多方向区域查询的空间向量模型算法[J].计算机应用，2015，35（2）：452-455.
LIU R T，ZHAO Z G，TIAN G Y.Space vector model algorithm for query of continuous and multidirectional regions[J].Journal of Computer Applications，2015，35（2）：452-455.
[10] 王中辉，杨艳春.一种基于方向关系的空间查询算法[J].兰州交通大学学报，2015，34（1）：175-179.
WANG Z H，YANG Y C.An algorithm for spatial query based on direction relation[J].Journal of Lanzhou Jiaotong University，2015，34（1）：175-179.
[11] 王中辉，孙立，禄小敏，等.方向关系在空间查询中的应用研究[J].地理信息世界，2018，25（1）：23-27.
WANG Z H，SUN L，LU X M，et al.Application of direction relations in spatial query[J].Geomatics World，2018，25（1）：23-27.
[12] 郝忠孝.时空数据库查询与推理[M].北京：科学出版社，2010：32-36.
HAO Z X.Spatio-temporal database query and reasoning[M].Beijing：Science Press，2010：32-36.
[13] SHAHABI C，SHARIFZADEH M.Voronoi diagrams[M]//Encyclopedia of database systems.New York：Springer，2018.
[14] 孙继忠，胡艳，马永强.基于Delaunay三角剖分生成Voronoi图算法[J].计算机应用，2010，30（1）：75-77.
SUN J Z，HU Y，MA Y Q.Voronoi diagram generation algorithm based on Delaunay triangulation[J].Journal of Computer Applications，2010，30（1）：75-77.
[15] 赵纪桥，张丽平，李鹏，等.Voronoi图的构建与查询方法[J].计算机与数学工程，2014，42（9）：1701-1704.
HAO J Q，ZHANG L P，LI P，et al.Construction and query methods of voronoi diagram[J].Computer & Digital Engineering，2014，42（9）：1701-1704.
[16] 周培德.计算几何-算法设计与分析[M].北京：清华大学出版社，2008：147-172.
ZHOU P D.Computational geomety-algorithm design and analysis[M].Beijing：Tsinghua University Press，2008：147-172.