基于增量算法的三角剖分算法

增量算法是平面投影法中一种常用的点云剖分算法,该算法编程简单,占用内存少,计算速度较慢.针对增量算法的特点,改进算法通过将不同位置的点剖分对应存储到不同的边链表和三角形链表中,降低了边和三角形的搜索时间,提高了三角化的速度.同时,采用了加点剖分中同步优化和初步剖分后全体再次优化的优化方案,大大提高了剖分三角形的质量.实际点云剖分的结果显示,该算法不仅速度快、占用内存小,而且形成的三角表面质量高.

Triangulation algorithm based on incremental algorithm

The incremental algorithm of plane-projection method is a mainly point-cloud subdivision algorithm. And the incremental algorithm works out procedure simply, take up memory little, whereas the computational speed is relatively slow. Based on the incremental algorithm, an improved algorithm is presented in the paper. The improved algorithm reduces the time of searching the sides and the triangles and improves the speed of the triangularization through subdividing and storing the points in different seats to the different side linked lists and triangular linked lists. And after adopting the synchronous optimization when the points are added, the whole optimization is used again. So the quality of the subdivided triangles has been improved greatly. The experimental result of point-cloud subdivision reveals not only does the algorithm run fast and need the memory little, but also the quality of triangles surface is high.