一种平面点集凸包与三角网格综合生成的算法

平面点集作为一种觉数学模型，其上常做的运算是求其凸包和三角网格，目前二者的研究是独立进行的，鉴于在很多情形下这两种处理结果均需要，提出了一种综合算法：在对离散点集进行ｄｅｌａｕｎａｙ剖分的过程中，增加对三角形边界的判别、管理功能，记录其中作为点集凸包边界的线段，使得在实现剖分的同时产生出点集的凸包，从而提高了算法效率，且当该算法实现单一的点集剖分或凸包功能或是用于简单多边形的凸包与剖分时效果也很好

AN ALGORITHM FOR CONSTRUCTING THE CONVEX HULL AND THE TRIANGULATION OF A SET OF NODES IN A PLANE

Two kinds of common operation on the set of nodes in a plane are calculating its convex hull and triangulation, and usually the algorithms are studied independently. But in some cases, the two calculations are all needed. Therefore a comprehensive algorithm is presented in this paper. By adding a less time consumption model of distinguishing and managing the segments of the triangles during the triangulation of a set of nodes in a plane, the segments can be recorded, which would be the boundary of the convex hull of the node set. So the convex hull and the triangulation of the node set in a plane can be obtained in the same process. It means a higher efficiency. The algorithm can also work when it is used to implement one of the functions independently. It can also be used for calculating the convex hull of a simple polygon.