简单多边形的优化三角剖分  

Optimal Triangulation of Simple Polygon

作　　者：卢朝阳[1] 吴成柯[1] 陆心如[1] 

机构地区：[1]西安电子科技大学信息工程系

出　　处：《电子学报》1991年第2期82-87,共6页Acta Electronica Sinica

基　　金：国家自然科学基金

摘　　要：简单多边形的三角剖分(TSP)问题是计算几何的基础问题之一。本文给出了一种使用Delaunay三角形化的优化TSP算法。思路是设计一个矩形辅助窗口,并利用“四边形对角线交换”技术来获得简单多边形的三角剖分。The Iriangulation of a simple polygon(TSP) is one of the basic problems in computational geometry. In this paper we present an optimal TSP algorithm by using Delaunay triangulation. The TSP problem is solved by designing an auxiliary square window and utilizing a 'quadrilateral diagonal exchanging' technique.

关 键 词：多边形 三角剖分 计算几何 

分 类 号：O181[理学—数学]