基于Voronoi图的线段最近对查询

最近对查询是空间数据库中的重要查询之一。已有的关于最近对查询的研究基本集中在点对象上,对空间对象无法抽象为点的对象则研究较少。提出基于平面线段的最近对查询,即找出两个平面线段集中距离最近的线段对。提出基于Voronoi图的线段最近对查询算法,该方法构造两个线段集的Voronoi图,利用Voronoi图的最近邻近特性和局域动态特性找到互为最近邻的线段对,从中找到结果,以缩减大量的计算代价。对线段集中增加线段和删除线段的情况做了相应的处理。实验证明,该算法具有较高的查询效率。

Line Segment Closest Pair Queries Based on Voronoi Diagram

Closest pair(CP) query is one of the important spatial queries in spatial database. But the existed researches on CP query are mainly focused on point objects,which can rarely solve some instance that spatial object can not be abstracted as a point. The question of closest pair query between line segment and line segment was first put forward.That is finding the line segment pair which has the shortest distance among all the line segment pairs of two line segment sets. The line segment closest pair ctuery algorithm based on Voronoi diagram was proposed, and the relevant theorern and proof were given. `hhe Voronoi diagram of two line segment sets was constructed respectively in the method. By making use of nearest adjacent property and local dynamic property, the line segment pairs that arc the nearest neighbor mutually were finded from which the result was got, in order to reduce a lot of computational cost. The two circumstances of insert line segment and delete line segment were dealed with. Experiments demonstrate the proposed algorithms have high query efficiency.