摘要
平面点集作为一种常见数学模型 ,其上常做的运算是求其凸包和三角网格 .目前二者的研究是独立进行的 .鉴于在很多情形下这两种处理结果均需要 ,提出了一种综合算法 :在对离散点集进行 delaunay剖分的过程中 ,增加对三角形边界的判别、管理功能 ,记录其中作为点集凸包边界的线段 ,使得在实现剖分的同时产生出点集的凸包 ,从而提高了算法效率 .且当该算法实现单一的点集剖分或凸包功能或是用于简单多边形的凸包与剖分时效果也很好 .
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.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2000年第7期891-896,共6页
Journal of Computer Research and Development
基金
北京市科技干部局青年科技骨干培养基金项目资助
