大规模地形散乱点的快速构网算法

A Fast TIN Generation Algorithm Based on Large-scale Unorganized Terrain Points

针对大规模视景仿真地形显示的需要,提出了一个利用大规模地面散乱点构建地形三角网格的算法。先将空间的散乱点投影到XOY坐标平面,在坐标平面上对散乱点进行均匀网格划分,然后按照一定顺序将大规模散乱点组织成若干不相交的单调链,由相邻单调链连接成单调多边形,利用单调多边形的特点快速构建初始三角网格模型,并在空间上对模型进行三角网格优化。通过加入辅助点的方法,有效解决了网格边沿的奇异情况。算法在保证网格质量的同时,大幅减少了构网的时间开销,证明了提高网络的速度。

Aiming at the characteristics of terrain data, a TIN generation algorithm is proposed. First, the unorganized points are projected onto the XOY coordinate plane, and are divided into many parts by a regular net. Then, the paper organizes those points in several monotonous chains according to a certain axis order, and makes use of the characteristic that monotonous chains are easy to set up triangular mesh quickly. In the end, the triangular mesh is optimized by normal methods. The boundary shape is not very good by this algorithm, then by adding some accessorial points, the abnormity in the mesh boundary is solved effectively. This algorithm promised the mesh quality, and the time cost is greatly reduced.