满足全局Delaunay特性的带特征约束的散乱数据最优三角剖分

OVERALL DELAUNAY TRIANGULATION OF 2D SCATTERED DATA WITH CHARACTERISTIC CONSTRAINTS

本文给出了一种新的全局满足Ｄｅｌａｕｎａｙ特性的带特征约束散乱数据的优化三角剖分算法．统一的数据结构允许散乱数据带有外部边界或内部孔洞，并且约束特征可以是有向折线或封闭多边形．由于采用了“对半划分增量型附加特征点插入”算法，从而可以用较少的附加点来使全局Ｄｅｌａｕｎａｙ特性得到满足．

This paper presents an algorithm for overall Delaunay triangulation of 2D scattered data with characteristic constraints. The outer polygonal boundary and/or inner polygonal holes that scattered data may have and the characteristic constraints which could be polylines and/or polygons are stored in a generic data structure. The overall Delaunay properties could be satisfied by inserting fewer points using a'half-separated additional characteristic point inserting technique'.