基于tin模型的空间索引方法研究

《基于tin模型的空间索引方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于TIN模型的空间索引方法研究刘妍（黑龙江工程学院测绘工程系，黑龙江哈尔滨150050）摘要：结合常见的三表数据结构，构建二表数据结构，在二表数据结构的基础上，探讨适应TIN模型的空间索引方法，提出重心空间索引和顶点空间索引两种算法，同时比较各空间索引算法的优劣，为提高空间数据查询的效率提供了依据。关键字：TIN；数据结构；空间索引；空间查询ResearchonMethodsofSpatialIndexBasedonTINLIUYan（Dept.ofSurveyingandMappingEngineering,Heilongj

2、iangInstituteofTechnology,Harbin150050,China）Abstract:Basedon3-tablesdatastructure,2-tablesdatastructureissetup.ThispaperresearchestwokindsofspaceindexmethodsforTINmodel.TheyareCentrobaricSpatialIndexandApicalSpatialIndextoimproveefficiencyofspatialsearch.Keywords:TI

3、N;Datastructure;Spatialindex;Spatialsearch0引言不规则三角网（TriangulatedIrregularNetwork）模型是数字地面模型的重要表示模型之一。随着数字信息时代的到来，TIN模型的应用在GIS的发展过程中也变得越来越重要，其[1]中TIN模型的空间索引和查询是最为普遍的应用。为了能够从根本上解决空间索引和空间查询的速度问题，建立高效的空间索引机制和快速的空间查询方法则是解决问题的关键，这也是多年来研究的热点。本文针对不规则三角网模型，对模型中的三角形进行重新排序索引，达到快

4、速判断标识点所在三角形的目的，提出了重心索引和顶点索引两种方法。并在此基础上进一步提出了空间信息折半查询的方法，克服了顺序查找法在查找时遍历所有数据的缺点，大量减少比较的次数，为实现TIN模型的快速双向空间查询提供依据，从而提高对海量空间数据的利用效率。1TIN模型的空间数据结构1.1三表数据结构三表数据结构是常见的数据结构，以三个拓扑空间信息数据结构表来定义该TIN模型[2]中的所有数据关系。具体数据结构设计是分别对特征点、三角形边和三角形本身按拓扑关系组织成对应的点、线、面拓扑关系表。各表的数据结构分别如表1、表2、表3所示

5、：表1点的拓扑结构IDXYZRE其中，ID为点的流水号；X、Y、Z分别为点的横坐标、纵坐标和高程值；RE为与点相关联的边。表2边的拓扑结构IDFNTNLNRN442其中，ID为边的流水号；FN、TN分别为边的起点和终点；LT、RT分别为边的左、右三角形，规定沿着边的走向，在左侧的为左三角形，右侧的为右三角形。如果边的左侧或右侧不存在三角形时，则该边为边界，一般的情况下，规定不存在三角形的区域为0面域。表3三角形的拓扑结构IDFESETE其中，ID为三角形的流水号；FE、SE、TE分别为三角形的第一、二、三条边。1.2二表数据结构

6、虽然三表数据结构已经被广泛的引用，但根据不同的数据库需要，也可构建二表数据结构。n1k3这种数据结构更为简单，只需建立点表（表4）和cn3三角形表（表5）。以图1为例，在点表中存储点a号ID、点的横坐标X、纵坐标Y及高程Z；在三k1bk2角形表中，则存储三角形号ID、第一个顶点n1、n2第二个顶点n2、第三个顶点n3、第一邻接三角形图1二模型数据结构k1、第二邻接三角形k2、第三邻接三角形k3。表4点表IDXYZ表5三角形表IDnnnk1231k2k32TIN模型的空间索引机制设计空间索引的关键是将无序的空间点、线、面实体数据进

7、行排序，进而建立高效的索引机制。国内外常见的空间索引一般是自顶向下、逐级划分空间的各种数据结构空间索引，有代表性的是网格索引、四叉树索引、BSP树索引、KDB树索引、R树索引、R+树索引和[3][4]CELL树索引等。针对TIN模型，常见的索引方式并不适宜，为此本文提出两种空间索引方法，即重心空间索引和顶点空间索引算法。实质就是通过合理的排序建立一张索引表。2.1重心空间索引算法在TIN模型中，由于每个三角形对应唯一的重心点，三角形序号与重心即可建立一一对应的关系。那么就可以通过给重心排序建立三角形的空间索引。只要找到三角形对应

8、的重心信息，便可以轻松找到该三角形所对应的相关信1息。参照1.2二表数据结构分析具体算法如下，大致可分为三个步骤：1）计算重心坐标io三角形的重心坐标的计算主要是求得横坐标和纵坐标，即三角形的三个顶点的横坐标之和的平均23数得重心的横坐标，三个顶点的纵坐标之和的