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

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

作　　者：张永春[1] 达飞鹏[1] 宋文忠[1] 

机构地区：[1]东南大学自动化研究所,南京210096

出　　处：《东南大学学报（自然科学版）》2004年第6期851-856,共6页Journal of Southeast University：Natural Science Edition

摘　　要：从曲率入手 ,提出一种空间凸四边形的曲率估计算法 ,由此建立了一种新的基于该曲率的三角剖分优化准则以及曲面三角剖分算法 .该算法修改了部分常用的数据结构 ,使得算法有更好的空间复杂度 .通过分析 ,算法的时间复杂度为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.

关 键 词：散乱点集 三角剖分算法 数据结构 优化准则 曲面保形 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]