生成Delaunay三角网的改进算法

算法以原“改进的自连接Delaunay三角网生成算法”为基础。其主要方法仍是三角网生长法,但同时采用了逐点插入法中的凸壳。在原封闭点的基础上提出了封闭的边界点的概念,并增加了对边界点和边界边的识别和处理,从而进一步提高了构网效率。另外,采用的用边的法向量对边的某侧的点进行判断的方法也简单实用。

An Improved Algorithm for Building Delaunay Triangulation

This algorithm is based on the original paper of "An Improved Algorithm for Auto Connected Delaunay Trianglation~([1])".In this paper,the main method we take is triangulation growth still,but also adopt Convex-Frame in incremental insertion method.We propose the notion of closed-border-point on the base of closed-point,and also improve the way of recognizing and handling to border-point and border-edge(because border-edge can build triangulation only once).For this,it enhances efficiency of building triangulation.Additional,the way in this paper to determine which side of an edge points in using edge's normal~([4]) is very simple and practicality.