任意多边形内带特征约束的散列数据的最优三角剖分

OPTIMAL TRIANGULATION OF DATA POINTS SCATTERED IN ARBITRARY POLYGON WITH CHARACTERISTIC CONSTRAINTS

给出了一种新的基于Ｄｅｌａｕｎａｙ三角形化的任意多边形边界内散列数据的优化三角剖分算法。该算法可允许散列数据带任意复杂的折线及封闭多边形环的特征约束。算法用统一的数据结构来记录散列数据、约束特征和三角剖分信息，并且引入了辅助窗的概念。

This paper presents an algorithm based on the Delaunay strategy for optimal triangulation of data points scattered in 2D region with polygonal boundary. The characteristic constraints of the data, which could be polylines and/or polygons with any complicated contour, can be imposed on the triangulation. A generic data structure is used to store the scattered data, their constraints and triangulation information. Besides, an auxiliary window is introduced to facilitate the construction and programming.