点与三角形位置关系对三角网格拓扑的影响

Relationship of point and triangle’s influence on topology of Delaunay triangulation

逐点添加、局部优化的Watson算法和局部变换法是生成大规模离散点集Delaunay三角网格的常用方法。点与三角形位置关系判别和三角形外接圆包含点的测试分别是局部变换法和Watson算法正确生成Delaunay三角网格的重要环节。计算误差会导致点与三角形位置关系以及三角形外接圆包含点的错误判别,从而生成几何拓扑关系不正确的三角网格。采用相对位置坐标可以提高面积坐标和外接圆圆心、半径的计算精度。以等高线地图采集的地形数据为例,用改进的算法生成了包含393252个离散点的Delaunay三角网格。

Watson and local transformation methods which add point by point and local optimization are the popular algo- rithms of large-scale scattered data Delaunay triangulation.The situation of the new point in a triangle and whether the point is contained in triangle’s circumcircle are important factors of creating correct Delaunay triangulation.Calculation error can lead to the wrong discrimination of the location relationship between point and triangle,the containing relationship of point and triangle’s circumcircles,and then wrong geometric topology triangular mesh is created.A new method is presented that improves the calculation precision of area coordinates and the centre and radius of circumcircle with relative coordinates.De- launay triangulation of 393,252 points of terrain data which are extracted from contour map is created.