针对海量地形大数据点云的总分式三角网多线程并行生成方法

摘要

本发明公开了一种针对海量地形大数据点云的总分式三角网多线程并行生成方法，该方法首先提出自适应网格空间分割，实现海量点云数据的规模均衡网格分布；通过建立网格内点数据空间的距中排序规则，合理部署网格内点的参与构TIN的先后顺序；按总分方式优先运用传统构TIN的查找插入法、拓扑插入算法首先实现网格间的点数据建模，避免分治建模算法复杂低效的网格间合并过程；建立网格的拓扑闭包检测机制，分别针对各个空间网格，适时启动独立并行的多线程对余下的构模点按传统的拓扑插入算法进行建模，从而并行高效地、由总到分地完成整个空间下的三角网建模工作。本发明显著提高了针对海量点云大数据的空间建模支持能力。

主权项

一种针对海量地形大数据点云的总分式三角网生成方法，其特征在于，它包括如下步骤：步骤1：对海量点云数据进行给定规模的自适应网格划分，使得每一网格内的点数限定在预设的数量LN内，LN表示网格的限制点数，即网格之间无缝无叠地覆盖整个点云数据空间；步骤2：对每一个网格内的点按点距离网格中央的距离，由远及近地进行排序，这样网格内点队列的最后一个点就一定是距离网格中央最近的点，称为中央点；将中央点移动至网格点队列的最前面；步骤3：按网格里包含点的数量从小到大对所有网格进行排序，同时标注各个网格中待构模点数RN为点列队中点的数量；步骤4：从网格队列中第一个待构模点数RN>0的网格开始，依次从每一个网格的点队列中取出第i个点，其中0≤i<LN，用查找插入法构建初级的均衡的三角网，当网格中的一个点参加构模后，该网格的待构模点数RN减1；如此对所有网格重复操作K次，完成各个网格前K个点的插入法构模，其中，1≤K<LN；步骤5：在每一个网格中完成第K个点的查找插入法构模时，同时在插入法新增加的三角形中找到一个以该网格中央点为顶点的三角形，作为该网格进行拓扑检索的起始三角形予以记录；步骤6：对网格队列中余下第i个点的插入，其中K<i≤LN构模，根据标记的起始三角形，利用既有三角网的拓扑关系采用重心趋近方向搜索方法定位点所对应的三角形，按插入法构模，单个点插入后同样在新生成的三角形中找到一个以网格中央点为顶点的三角形作为新的起始三角形，这样能够保证后续点的插入构模效率不会因为三角网的增加而变低；依次对每一个网格完成第i点的插入构模后再次循环完成i＝i+1个点的构模，直至所有网格的所有点均参与构模，主线程算法完成。