| 基于线性四叉树的快速邻域查询算法 |
| |
| 引用本文： | 赵慧,宋星. 基于线性四叉树的快速邻域查询算法[J]. 计算机工程与设计, 2007, 28(18): 4333-4335 |
| |
| 作者姓名： | 赵慧 宋星 |
| |
| 作者单位： | 中国航天科工集团第二研究院706所,北京,100854;中国航天科工集团第二研究院706所,北京,100854 |
| |
| 摘 要： | 邻域查询是位置服务系统的核心技术,它的实现取决于空间对象数据模型.根据空间对象分布构建的四叉树模型,以及线性四叉树中位置码的使用,提出了一种新的基于线性四叉树的快速邻域查询算法.该算法根据满四叉树结点编码思想对线性四叉树的Morton码进行了改进,并增加了表示四叉树所有结点状态的序列,通过网格模型的邻域查询算法实现了线性四叉树的快速邻域查询.
|
| 关 键 词： | 位置服务系统 线性四叉树 邻域查询 Morton编码 结点状态序列 |
| 文章编号： | 1000-7024（2007）18-4333-03 |
| 修稿时间： | 2006-12-11 |
Fast neighbor-finding algorithm based on linear quadtree |
| |
| ZHAO Hui,SONG Xing. Fast neighbor-finding algorithm based on linear quadtree[J]. Computer Engineering and Design, 2007, 28(18): 4333-4335 |
| |
| Authors: | ZHAO Hui SONG Xing |
| |
| Affiliation: | Institute 706, Second Academy of China Aerospace Science and Industry Corporation, Beijing 100854, China |
| |
| Abstract: | Neighbor-finding is a core technique of location-based service whose realization is decided by the data model of spatial objects. As geographic region is partitioned by the quadtree and location-code of linear quadtree is used to represent the location of spatial object in the sub-region, a new fast neighbor-finding algorithm based on linear quadtree is introduced. It refers to an optimized morton-code which is modified according to node-code of full quadtree, a status sequence recording the status of all quadtree nodes, and a neighbor- finding algorithm based on grid. All of these make the efficiency of neighbor-finding high in linear quadtree. |
| |
| Keywords: | location-based service linear quadtree neighbor-finding Morton code node status sequence |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
