基于一种曲率最小优化准则的散乱点三角剖分

Triangulations based on a criterion of minimized curvature for scattered point-sets

从曲率入手 ,提出一种空间凸四边形的曲率估计算法 ,由此建立了一种新的基于该曲率的三角剖分优化准则以及曲面三角剖分算法 .该算法修改了部分常用的数据结构 ,使得算法有更好的空间复杂度 .通过分析 ,算法的时间复杂度为O(m2 ) ,同时还将这一优化准则与几种常用的优化准则作了扼要比较 .实验结果分析表明本算法具有保形特性 ,这在曲面重构和曲面设计等方面有很好的实用价值 .

An algorithm to estimate the curvature of a quadrilateral is presented. And a new algorithm of triangulation based on the criterion of minimizing this curvature is proposed. Some commonly used data structures are improved in the algorithm to reduce the space complexity. The time and space complexities of the algorithm are analyzed in detail. It is proved that the time complexity is O(m2). Compar isons between minimal curvature criterion and other criteria are concisely enunc iated. Finally, two typical examples are given and the results indicate that the property of shape-preserving i s obtained with the algorithm. This triangulation algorithm is of practical value for surface reconstructions and surface designs.