不规则三角网的几种数据结构及其存储机制研究

在比较分析了TIN的几种常见数据结构的基础上,针对TIN拓扑查询与搜索问题,提出了另外几种强调边拓扑信息的TIN数据结构,根据拓扑关系的表达方式可以将它们分为内存索引式结构、数组索引式结构及二者的混合结构,并给出了这些数据结构的多种序列化存储方式:数组索引直接存储、对象ID存储法、PythoncPickle存储、对象内存地址的存储法。研究比较发现数组索引直接存储的数据占用空间最少,对象ID存储法和对象内存地址存储法的二进制方式占用空间相同,Python cPickle只适合于极小规模的TIN数据的存储。对基于不同数据结构的TIN模型构网效率测试表明,不包含边信息的结构的构网效率最高,含有边信息的结构中采用数组索引表示拓扑关系的构网效率最高。研究结果将对TIN模型的软件实现具有理论及应用价值。

A study of several data structures of triangulated irregular networks and their storage mechanism

On the basis of comparison and analyses on several currently frequently used data structures of Triangulated irregular networks, some new data structures that emphasize on edges' topologic information were proposed aiming at the existed problems in TIN topologic query and searching. According to the topologic expressions the new structures can be classified as memory address structure , array indexed structures and a hybrid structure based on former two structures. Accordingly several serialization methods for these structures were suggested, i. e. array index' s direct saving method (AIDS) , objects ID saving method (OIS), cPickle-saving method in python language (PPS) and object pointers saving method (OPS). Comparisons among these methods indicate that the AIDS method takes the least memory, while OIS and OPS take same amount of memories. PPS is only suitable for saving very small sized TIN. Comparisons on TIN generating efficiency among these proposed data structures suggested that the structures without edge information is most efficient, and for those structures comprising edge information, the array indexed structure was performed the best.