论文部分内容阅读
讨论了实现Ｄｅｌａｕｎａｙ三角形剖分的新算法。该算法使用一个均匀的格子结构，并采用循环生成三角形的策略实现Ｄｅｌａｕｎａｙ三角形剖分。与其他算法相比，具有许多新特征。尤为重要的是，算法的时间复杂度随点数的增加呈线性增长，而不是固有的Ｏ（ｎ＾２）。文中给出了该算法及其实现的细节。讨论如何处理数据；描述如何基于均匀格子结构建立内部数据结构；通过一个例子描述如何实现三角形剖分进程的细节；给出算法思想的证