一种确定高阶Delaunay三角网中可用k—OD边的算法

目的构建高阶Delaunay三角剖分方法的数字地形模型，有效地减少局部极值问题，使得地形模型能更好地反映原始地形的真实面貌．方法提出了一种确定高阶Delaunay三角网中可用k-OD边的方法，该方法首先在任意边uv的两侧分别确定两点，使每个点与uv边形成的三角形的外接圆不包含同侧的点，若这两三角形都为k—OD三角形，则uv边是可用k—OD边．结果用Visual C＋＋实现算法，通过实验验证了算法的有效性，对于具有n个点的点集P，在时间O（nk^2＋nklogn）内可以计算出所有的可用k—OD边．结论选择合适的可用k—OD边生成相应的高阶Delaunay三角网来模拟实际地形，可以有效地减少局部极小的数量，使地形模型更接近于实际地形．

An Algorithm on Finding All Useful k-OD Edges of HOD Triangulation

In order to construct DTM based on higher order Delaunay triangulation, to minimize the local extremum problems, and to make the terrain model reflecting the real landforms better of the original terrain, a new algorithm is proposed. The algorithm is used to find the useful k-OD edges of the higher order Delaunay triangulation, by which two points are first fixed at the two sides of the random edges uv, and the points at the same side aren＇t in the circumcircle of the triangle constructed by edge uv. If the two triangle are k-OD triangles, then edge uv is an useful k-OD edge. The experiment validated the validity of the algorithm, for the point set P containing n points ,the time complexity is O（ nk^2 ＋ nklogn）. Choosing the right useful k-OD edges to construct the higher order Delaunay triangulation for simulating the real terrain, it can reduce the quantity of the local minimum, and the terrain model approximates the real terrain better.