Abstract: In order to satisfy the actual demand of surface and underground mining area construction of curved surface, especially in the pit, according to the classical problem is widely used in graphics computational geometry polygon triangulation, it presents a visual point using the maximum angle as triangular mesh triangle extension point construction algorithm, constraint conditions of the algorithm is the area of the triangle, and polygon triangulation by recursion. Combined with the example of contrast, boundary points processing the algorithm in both precision and accuracy are both good performances. The algorithm is simple to realize, easy to understand, after repeated modification and improvement, has become one of the digital mine 3D software Vrmine core algorithms.

Key words: polygon, triangularization, useable vertex, area, digital mine

摘要： 为满足地表及地下尤其是井下构建并显示三维图形的实际需求，针对图形学中广泛应用的计算几何多边形三角化这一经典算法问题，提出一种采用最大角度的可用点作为三角形扩充点的三角网构建算法，该算法的约束条件是三角形面积，并通过递归实现多边形三角化以便进行三维可视化。结合实例对比，该算法对边界点的处理无论精度还是准确度均有较好表现。算法实现简单，易于理解，经过多次修改完善，已经成为数字矿山三维软件Vrmine核心算法之一。

关键词: 多边形, 角形化, 可用点, 面积, 数字矿山