L curve for spherical triangle region quadtrees  

作　　者：YUAN Wen1,CHENG Chengqi1,MA Ainai1 & GUAN Xiaojing2 1.Institute of Remote Sensing and Geography Information System,Peking University,Beijing 100871,China 2.Centre of State Information,Beijing 100045,China 

出　　处：《Science China(Technological Sciences)》2004年第3期265-280,共16页中国科学（技术科学英文版）

摘　　要：The sequence of facets and nodes has a direct influence on the efficiency of access to spherical triangle region quadtree. Based on the labeling schema by Lee, spatial curves both for facets and nodes are proposed and the main algorithms for coordinate translation, node Lsequence generation and visiting nodes are presented. In particular,constant time algorithms for generating node Lsequence are advanced by using bit manipulation operations,which can be easily implemented with hardware. In L curve the distance between three nodes of a facet is mostly limited in a range of small value, thus making fast access possible. Though codes of sibling facets are continuous, the difference between codes of some cousins may occasionally be very large and makes the distance of a few facets also very large, thus greatly increasing the mean node distance and the total traversing distance. Therefore an m cluster of nodes is proposed as a basic storage unit fo n cluster, which should store eery shared node in each,and the distance between three nodes of a facet is limited to a controllagle scope.The sequence of facets and nodes has a direct influence on the efficiency of access to spherical triangle region quadtree. Based on the labeling schema by Lee, spatial curves both for facets and nodes are proposed and the main algorithms for coordinate translation, node Lsequence generation and visiting nodes are presented. In particular,constant time algorithms for generating node Lsequence are advanced by using bit manipulation operations,which can be easily implemented with hardware. In L curve the distance between three nodes of a facet is mostly limited in a range of small value, thus making fast access possible. Though codes of sibling facets are continuous, the difference between codes of some cousins may occasionally be very large and makes the distance of a few facets also very large, thus greatly increasing the mean node distance and the total traversing distance. Therefore an m cluster of nodes is proposed as a basic storage unit fo n cluster, which should store eery shared node in each,and the distance between three nodes of a facet is limited to a controllagle scope.

关 键 词：global grid  spherical TRIANGLE REGION quadtree  SQT  QTM  space-filling curve. 

分 类 号：O29[理学—应用数学]