论文部分内容阅读
目前已有多种基于平面上离散点集构造Delaunay三角网的算法，其中三角网扩张法、逐点插入法的平均时间复杂度为0（n^2），分治算法和其他分块合并算法能使平均时间复杂度接近线性，但增加了算法的复杂性，从而使浮点计算误差错误发生的机率增大。本文作者提出了一种新算法：将用于构网的离散点集先按横坐标从小到大排序，在空间上表现为从左到右排列；然后先以点序列中的前三个点作为初始三角网，每次将剩余点集中最左边的点联入三角网，最终得到一个三角剖分，再用LOP法优化三角剖分。该算法的优势是具有快速的三角剖分过程，使整体的