一种含边拓扑信息的不规则三角网弧扫式构建方案

摘要

一种含边拓扑信息的不规则三角网弧扫式构建方案，涉及地理信息系统(GIS)以及激光雷达(LiDAR)数据处理所需的不规则三角网(TIN)的构建技术，尤其是含有边信息的不规则三角网的快速构建技术。本发明使用一种含有向边及其拓扑关系的数据结构。先对点集相对某一选定的参考中心计算各点的距离及方位角，对点集按照与参考中心的距离排序，并按此顺序由内向外以圆弧扫描的方式逐个把离散点联入三角网中，同时以递归方式局部优化新生成的三角形。方法中用双向循环链表结合一个按照方位角划分的存储桶用于管理和检索已有三角网外侧凸包边界上的所有边。每联入一个点时，借助存储桶的导向功能快速找出符合联网条件的边以构建新三角形。本方法具有构网速度快、思路简单、易于实现和生成的三角网拓扑关系明确的特点，对基于LiDAR海量数据的不规则三角网构建及其数据处理提供了有效方法。

主权项

一种用于地理信息系统的含边拓扑信息的不规则三角网弧扫式构建方法，其特征在于，包括以下步骤：(1)使用含顶点、有向边、三角形的3种结构体类型定义，并创建这三种结构体类型的数组容器对象，用于存放这三种结构体类型的变量；(2)确定一个参考中心位置，计算所有离散点相对参考中心的距离和方位角，将待构网的离散点集按照该距离从小到大升序排序；(3)建立一个存放三角网外边界边序列的双向循环链表；并建立根据该双向循环链表中边的始点的方位角存放结点的方位角存储桶；方位角存储桶中只存放属于双向循环链表结点的记录，当双向循环链表中加入一条边时，由该边生成的结点对象的记录要按照该边起始方位角存入相应的方位角存储桶；当双向循环链表中要删去一条边时，相应的方位角存储桶中的记录也要删去；(4)在排序过的点集中取最初三个点按逆时针顺序连成首三角形，并将三条边的记录以同样的逆时针顺序存入该双向循环链表中，形成初始三角网外边界；(5)从点集中按序取下一个点，按照该点的所属方位角，从对应的方位角存储桶开始快速找出以右侧面向当前点的边，都作为与当前点连成新三角形的基边；查找基边时需要借助两种条件判断，条件1为待判断边是否以右侧面向当前点，条件2为当前点的方位角是否介于待判断边起始方位角和终止方位角之间；首先根据当前点的方位角在相应的方位角存储桶找到一个边结点，以确定待查找的多条边在双向循环链表中的大体位置；查找的方法是从当前方位角存储桶中找出使条件2为真的一个结点；若对应的方位角存储桶为空，则向方位角更大的后续方位角存储桶中查找，直至找到一个符合条件的结点时结束循环；对新找到的不为空的桶中查找，若找到一个能使条件2为真的结点则将其返回，否则直接返回当前桶中最后一个结点；接着从上面返回的结点开始，在双向循环链表中以循环的方式向当前结点的左右两侧查找能使条件1为真的其它边结点，直至遇上不符合条件1的任意边结点后结束循环；(6)将步骤(5)中找出的每条基边与当前点构建成为三角形，将其注册到三角形数组中，同时生成和注册新三角形的三条邻边，即当前基边的反向边、当前基边始点与当前点构成的边即右侧边以及当前基边终点与当前点构成的边即左侧边；其中没有反向边的右侧边和左侧边需要加入该双向循环链表来实现链表更新，检查双向循环链表中是否有其反向边时，只需要直接将右侧边与当前基边的前驱比较，左侧边与当前基边的后继比较即可完成检查；当未找到右侧边或左侧边的反向边时，在双向循环链表中，将右侧边作为当前基边的前驱插入，将左侧边作为当前基边的后继插入，最后在双向循环链表中删除当前基边的记录；当新生成的左侧边或右侧边在双向循环链表中已有反向边时，在互设各自的反向边下标后，需要将原双向循环链表中反向边的记录删去；(7)对每个新生成的三角形都要与其所有邻接三角形进行检验是否符合Delaunay三角网最优准则，否则交换三角形的对角边，并以递归的方式对交换后得到的三角形进行扩散式LOP优化；(8)重复第(5)~(7)步，直至点集中所有的点都被处理过。