一种基于空间层次分解的Hilbert码生成算法_陆锋

一种基于空间层次分解的Hilbert码生成算法_陆锋

第6卷(A版)　第5期2001年5月

中国图象图形学报

JournalofImageandGraphics

Vol.6(A),No.5

May2001

一种基于空间层次分解的Hilbert码生成算法

陆　锋

周成虎

(中国科学院资源与环境信息系统国家重点实验室,北京　100101)

摘　要　基于Hilbert空间填充曲线的Hilbert空间排列码是一种优秀的线性映射方法,故在空间查询与索引中得到广泛应用.传统的Hilbert排列码算法是基于Morton码上的二进制位操作,复杂度为O(n2),在Hilbert空间填充曲线的空间层次分解特征的基础上,提出了一种新的Hilbert排列码生成算法,即通过栅格空间层次分解与构造区域状态转移向量,以递归的方式来生成Hilbert码,其复杂度为O(n),较之传统算法显著地提高了效率.在此基础上,结合点特征空间区域查询方法,又进一步阐述了以Hilbert空间排列码作为地址码的二叉平衡排序树空间索引方法的应用特点,并结合实例进行了讨论.

关键词　线性映射　Hilbert排列　层次分解　算法

中图法分类号:TP301.6　　文献标识码:A　　文章编号:1006-8961(2001)05-0465-05

AnAlgorithmforHilbertOrderingCodeBased

onSpatialHierarchicalDecomposition

LUFeng,ZHOUCheng-hu

(StateKeyLaboratoryofResourcesandEnvironmentalInformationSystem,ChineseAcademyofSciences,Beijing100101)

Abstract　HilbertspatialorderingbasedonHilbert-Peanocurvesisanexcellentlinearmappingmethod,andgetswideapplicationsinspatialqueryingandspatialindexing.ThetraditionalalgorithmforHilbertorderingcodeisbasedonbinarybitmanipulationonMortoncode.IthasacomplexityofO(n2).Inthispaper,theauthorsetforwardanewgeneratingalgorithmforHilbertorderingcode,whichisimplementedbyrasterspacerecursivedecompositionandregionalphaseshiftingvector,andhasacomplexityasO(n).Experimentshavevalidetedtheefficiencyofthenewalgorithm.Thealgorithmhasbeenappliedinafeaturebasednon-planardatamodelforurban

trafficnetworkstogeneratetheaddresscodesoastofacilitatethepointfeaturedynamicindexingbasedonbalancedbinaryorderingtreeandthelinearfeatureindexingbasedonvertexretrospection.Theaddresscodesforqueryingareaboundarycellscanbeusedtoseparatetheareaintoseveralsub-areastodecreaseexcessivesearching.SpatialorderingbasedonHilbertcodefacilitatesspatialclusteringofthespatialobjectsandspeedsupdataextraction.SpatialindexingwithHilbertcodeismoreefficientthansequentialindexingwhenagreatnumberofspatialobjectsareprocesed.Itisdistinctforspatialextentandproximityquerying.Keywords　Linearmapping,Hilbertordering,Hierarchicaldecomposition,Algorithm

凑技术,即将数据库中的记录映射到磁盘上的桶内,

0　前　言

线性映射一直是空间数据操作的重要组成部分,其在影象压缩、行程编码形式的栅格数据表达、空间索引、计算几何中的启发式搜索等领域应用十分广泛.

最早的多维到一维线性映射主要采用多属性杂

基金项目:国家“九五”科技攻关项目(96-B02-03-05)::09-26

以加快一维遍历和指定范围查询[1],但这种方法需要设计良好的杂凑函数,并且还要处理重复码问题,

因此在应用中,已经逐渐被基于空间填充曲线的空间排列码方法所代替.

虽然任何一种空间排列方法都不能完全保证能对二维数据的空间关系进行维护,但不同的空间排

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科一种基于空间层次分解的Hilbert码生成算法_陆锋全文阅读和word下载服务。