三维Hilbert曲线层级演进模型与编码计算

格网单元的编码计算是全球离散网格系统的核心,支撑着网格快速索引及应用分析的高效计算。Hilbert曲线具有聚簇性高、连续性强的特点,是研究设计全球离散网格编码的重要工具。利用Hilbert曲线进行格元编码实现了坐标等效降维表达,但是对Hilbert曲线不同层级之间的变换关系、一维Hilbert码如何刻画格元多维空间结构与关系等网格编码基础理论问题的研究尚不完备。本文以八叉树立体网格中三维Hilbert曲线层级演进关系为突破口,使用状态矩阵与演进矩阵构建层级演进模型,进而分别设计笛卡儿坐标至Hilbert码计算以及邻近格元Hilbert码计算方法。与现有算法对比,本文算法以层级演进模型为理论基础,避免了烦琐迭代步骤以及转换步骤,算法流程简明直接。试验结果表明,本文笛卡儿坐标至Hilbert码计算效率较迭代算法提高为7%~23%,邻近格元Hilbert码计算效率较转换算法提高4.0~4.5倍。     

虚拟战场环境时空数据的Hilbert码索引方法

在虚拟战场环境中,时空数据的高效组织是动态描述战场关键要素、实时分析军事行动计划的前提。首先对经度、纬度、时间进行同步层次嵌套细分来构建规则的多分辨率时空网格,然后基于Hilbert曲线设计时空格元编码,进而根据虚拟战场环境时空数据与时空格元Hilbert码的对应关系,提出一种基于Hilbert码的时空数据索引方法。在此基础上设计实验,比较格元编码的时空邻近性、索引构建效率以及查询效率。结果表明,Hilbert码方法在邻近性上优于Morton码,索引构建速度满足大规模时空数据处理需要,且查询效率优于直接基于经度、纬度、时间查询和基于Morton码查询的方法,可作为虚拟战场中作战计划推演、战场环境要素可视化与分析等时空操作的基础。     

Hilbert曲线层级演进关系

网格编码代数是当前全球空间网格研究中的难点,也是推动全球空间网格从数据组织管理框架发展成为新一代空间分析模型的理论基础。Hilbert曲线是设计全球空间网格单元编码的重要工具。本文以Hilbert曲线序列码作为八叉树立体网格单元的唯一编码,由Hilbert曲线数学性质推导得到网格单元Hilbert码的层级演进关系表,进而设计了用于网格编码代数运算的若干操作算子,为构建全球空间网格分析理论与方法提供参考。     

球体坐标与SDOG-ESSG格网码的相互转换算法

基于球体退化八叉树格网的地球系统空间格网(SDOG-ESSG)是地球系统科学与空间信息领域的重要的研究工具和手段。SDOG-ESSG格网码与现有空间参考相互转换的关键问题即球体坐标系与SDOG-ES-SG格网码的正向转换与逆向转换的算法。通过引进6种列-行-层坐标系并导出有关计算公式,借鉴Morton码行列二进制位交错的特性,分别设计了正向转换与逆向转换算法过程,在此基础上,理论分析并实验验证了两算法的时间效率。结果表明,两转换算法非常高效,其时间消耗基本与SDOG-ESSG的主剖次和副剖次呈线性关系,时间复杂度为O(n);在PC环境下,每秒能实现106～107次的转换运算,1次转换相当于101～102次的除法运算。     

紧致的Hilbert曲线Gray码索引算法

Hilbert曲线具有良好的聚簇性,使其成为设计全球立体网格多维数据索引的重要工具。但当数据集在不同维度上的分布密度存在较大差异时,常规Hilbert曲线索引会出现大量的冗余。对此,本文基于Gray码推导分析了Hilbert曲线索引的构造特点,进而设计实现了紧致Hilbert曲线索引算法,在保持Hilbert曲线良好聚簇性的同时,避免了数据维度分布差异带来的索引冗余问题。试验结果表明,相比常规Hilbert索引,紧致Hilbert曲线索引计算复杂度相当,在实例数据测试中编码耗时减少约40%,索引存储空间减少约46%,排序速度约为Hilbert排序的4.3倍。     

基于Morton码的一种动态二维游程压缩编码方法

本文在分析常规二维游程压缩编码方法缺陷的基础上,提出了一种基于Morton码的二维游程压缩编码方法.该方法按Monon码由小到大顺序扫描栅格数据,对于由2×2个像元组成的格网由Morton码生成格网左上角像元的行列号,并且用动态线性表通过比较像元的属性值,存储压缩结果,建立二维游程编码.实验表明,该编码方法在运行时间和...     

基于线要素综合的形状相似性评价模型

从面状要素形状描述模型中导出线状要素的相似性评价模型:将线状要素以首尾点的连线为对称轴作镜像处理构建其对偶面,以其对偶面的傅立叶形状描述子为其形状向量,以向量的欧氏距离来度量曲线的相似程度。为保证一定的评价精度,通过计算傅立叶第K项X、Y的增量值,来决定K值大小。最后对给定曲线运用不同的化简算法进行多层级的化简,通过本模型对形状的保真度进行分析。该模型具有数学严密性和实用性,能为选择曲线化简算法提供一种参考依据。     

最大空圆约束下的最邻近计算方法

移动目标的最邻近查询是位置服务的重要内容之一。本文针对地理目标分布不均的情况,将离散点集的最大空圆参数引入到最邻近查询中,提出了最大空圆约束下的k-D树最邻近查询算法。通过实验证明该算法可以有效地减少节点访问次数,减少距离计算次数,从而提高最邻近的查询效率。进而将该算法应用于移动目标的k阶邻近查询中,可以有效地减少移动点在三角网中的定位次数,改善k阶邻近的查询效率。     

Milne-Hamming线性多步法在求解姿态四元数微分方程中的应用

姿态微分方程的求解是SINS(Strap-down Inertial Navigation System)导航解算中一项重要的内容,对算法的稳定性、精度和计算量有较高的要求。引入了一种求解姿态四元数微分方程的新方法——Milne-Hamming线性多步预测校正方法,详细推导了应用此方法求解姿态四元数微分方程的过程。应用仿真数据和实测数据对此算法和四阶龙格-库塔算法进行了对比验证,结果表明Milne-Hamming线性多步预测校正方法是一种求解姿态四元数微分方程的有效方法,其稳定度明显优于四阶龙格-库塔算法并且计算量小。     

基于单位四元数矩阵实表示的坐标转换算法研究

四元数法可用于大角度的空间三维坐标转换,但其理论较复杂,计算及证明不便。借助四元数的矩阵实表示,可以将四元数域上的运算转化为实数域上向量和矩阵的运算。针对大角度空间三维坐标转换问题,构造了四元数优化函数,然后基于单位四元数矩阵实表示的方式将四元数问题的求解转换成矩阵问题的求解,并给出了利用单位四元数进行空间三维坐标转换两种算法的详细证明。经过算例分析表明,两种算法解算结果和奇异值分解算法一致,验证了算法的正确性和有效性,且两种算法只需进行矩阵的特征值分解,无须线性化,计算简便,便于编程,适用于大角度坐标转换问题的求解。     

时空轨迹多层级相似子段匹配方法

轨迹子段匹配是轨迹数据挖掘的重要手段,针对其计算复杂度较高、受噪声影响大的问题,提出了一种融合自适应希尔伯特地理网格编码的多层级轨迹编码树结构,在可接受的建树代价下,形成了从轨迹整段到最小片段的层次化组织形式和子段从属关系表达结构,并在轨迹片段编码树的基础上,设计了相似子段匹配算法,将复杂的空间计算转化为空间编码的字符串前缀匹配操作,极大地降低轨迹子段匹配的计算复杂度。实际轨迹数据的实验表明,在不影响匹配准确率的前提下,提出的子段匹配方法的效率与基于经典距离的相似性度量方法相比,有超过一个数量级的性能提升。     

路网环境下的混合数据最近邻查询算法

路网环境下的k最近邻查询方法在地理信息系统、智慧城市、数据挖掘、医疗营救和物流配送等领域都有着较为重要的作用,已有路网环境下的最近邻查询方法无法直接解决查询对象为点而数据对象为点和线段混合的复杂数据的近邻查询问题,为了弥补已有方法的不足,提出了路网环境下混合复杂数据的最近邻查询算法。将查询过程分为预处理、数据集约减和数据集精炼3个部分,并与3种对比算法进行对比实验,研究了测试数据对象的数量、路网规模的大小对中央处理器运行时间以及输入/输出代价的影响。结果表明,所提算法能有效地处理路网环境下混合数据的最近邻查询问题。     

一种面向多尺度面状居民地匹配的Voronoi图自适应构建算法

针对现有基于发生元离散化思想的Voronoi算法在计算效率与边界位置精度之间难以平衡控制的问题,提出了一种基于邻居对分类插值策略的面向多尺度面状居民地匹配的Voronoi图自适应构建算法(adap-tive Voronoi diagrams algorithm for matching multi-scale area...     

四孔六边形全球离散格网一致瓦片层次结构编码运算

全球离散格网系统是支持多源地球空间信息融合处理的有效解决方案,格网系统单元层次关系及全球统一编码运算是研究难点。首先,根据四孔六边形剖分特点,提出封闭二十面体表面的一致瓦片层次结构;然后,利用复进制数建立一致瓦片层次结构的编码数学模型,并等价设计全球统一编码运算、编码邻近查询、编码与地理坐标转换等算法;最后,设计了格网层次结构验证和编码运算效率测试实验。实验结果表明,一致瓦片层次结构的编码与地理坐标转换平均效率分别约是同类成果的2.74、1.73倍,编码邻近查询平均效率约是其7.46倍,且随着格网层次升高,效率优势更显著;与同类成果相比,所提方案瓦片具有一致性,且数量更少,算法复杂度低;层次结构的原理简明易懂,计算机执行效率高,可为多源对地观测数据统一组织管理、处理分析提供理论和技术支撑。     

一种顾及符号完整性的矢量瓦片地图改进方案

在矢量瓦片地图中,跨网格的要素被分割成多个部分,常常造成点、线、面要素中非均匀符号在网格边界处的不连续,这样不仅影响视觉效果,还容易引发空间认知错误.在保持矢量瓦片数据和样式独立的基础上,提出使用预处理和实时绘制相结合的方法解决这类问题.通过分析不同要素符号在网格边界不连续的类型和原因,提取了不同类型的绘图辅助信息;将...     

兰勃脱等角圆锥投影反解不同算法的解析

在测量与地图制图中,等量纬度求解大地纬度是一种常见的投影反解计算,就该反解问题的几种不同算法进行研究,包括迭代法、等量纬差求解大地纬度的级数展开式及等量纬度求解大地纬度的直接算法。利用Mathematica对后两种算法的计算公式进行了详细推导,给出了其高阶系数展开式,同时对现有算法中存在的问题进行了解析。兰勃脱等角投影算例表明,所推导的公式其计算精度可达(1×10-7)″~(1×10-8)″,完全满足测量与地图投影高精度的要求。     

利用哈尔变换和高斯随机数进行矢量空间数据坐标加密

基于安全保密的考虑,需要对矢量空间数据进行加密,现有做法是对数据文件整体进行加密,会破坏矢量空间数据结构并影响属性数据的查看。提出了一种不改变矢量空间数据结构,仅对坐标数据加密的方法,能够保护数据的安全且矢量数据结构依然保持不变。运用SHA-512加密用户密钥得到哈希密钥,用高斯随机数置乱哈希密钥生成用来加密坐标数据的密钥。首先读取矢量空间数据的顶点序列,并对矢量数据的顶点坐标序列进行哈尔变换,使用上述密钥对哈尔变换后的均值系数和差值系数进行加密,再实施逆哈尔变换得到加密后坐标,使用高斯随机数置乱顶点序列得到加密后的矢量空间数据。实验结果表明,矢量空间数据的坐标被加密,但文件结构及属性数据完全保持不变,且运行效率高;拥有密钥的用户还可以解密坐标,还原出原始矢量空间数据,安全性高。