[1]张永春,达飞鹏,宋文忠.基于一种曲率最小优化准则的散乱点三角剖分[J].东南大学学报(自然科学版),2004,34(6):851-856.[doi:10.3969/j.issn.1001-0505.2004.06.030]
 Zhang Yongchun,Da Feipeng,Song Wenzhong.Triangulations based on a criterion of minimized curvature for scattered point-sets[J].Journal of Southeast University (Natural Science Edition),2004,34(6):851-856.[doi:10.3969/j.issn.1001-0505.2004.06.030]
点击复制

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

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
34
期数:
2004年第6期
页码:
851-856
栏目:
计算机科学与工程
出版日期:
2004-11-20

文章信息/Info

Title:
Triangulations based on a criterion of minimized curvature for scattered point-sets
作者:
张永春 达飞鹏 宋文忠
东南大学自动化研究所, 南京 210096
Author(s):
Zhang Yongchun Da Feipeng Song Wenzhong
Research Institute of Automation, Southeast University, Nanjing 210096, China
关键词:
散乱点集 三角剖分算法 数据结构 优化准则 曲面保形
Keywords:
scattered point-sets algorithm of triangulations data structures optimal criterion shape preserving
分类号:
TP391.72
DOI:
10.3969/j.issn.1001-0505.2004.06.030
摘要:
从曲率入手,提出一种空间凸四边形的曲率估计算法,由此建立了一种新的基于该曲率的三角剖分优化准则以及曲面三角剖分算法.该算法修改了部分常用的数据结构,使得算法有更好的空间复杂度.通过分析,算法的时间复杂度为O(m2)2,同时还将这一优化准则与几种常用的优化准则作了扼要比较.实验结果分析表明本算法具有保形特性,这在曲面重构和曲面设计等方面有很好的实用价值.
Abstract:
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). Comparisons between minimal curvature criterion and other criteria are concisely enunciated. Finally, two typical examples are given and the results indicate that the property of shape-preserving is obtained with the algorithm. This triangulation algorithm is of practical value for surface reconstructions and surface designs.

参考文献/References:

[1] Lawson C L.C1 surface interpolation for scattered data on a sphere [J]. Rocky Mount J Math,1984,14(1):223-237.
[2] 周儒荣,张丽艳,苏旭,等.海量散乱点的曲面重建算法研究[J].软件学报,2001,12(2):249-255.
  Zhou Rurong,Zhang Liyan,Su Xu,et al.Algorithmic research on surface reconstruction from dense scattered points[J]. Journal of Software, 2001,12(2):249-255.(in Chinese)
[3] Choi B K,Shin H Y,Yoon Y I,et al.Triangulation of scattered data in 3D space[J].Computer Aided Design, 1988,20(5):239-248.
[4] 姜寿山,杨海成,侯增选.用空间形状优化准则完成散乱数据的三角剖分[J].计算机辅助设计与图形学学报,1995,7(4):241-249.
  Jiang Shoushan,Yang Haicheng,Hou Zengxuan.The triangulation of 3D scattered data with a space shape optimal criterion [J].China Journal of CAD and CG, 1995,7(4):241-249.(in Chinese)
[5] 柯映林,周儒荣.实现3D离散点优化三角剖分的三维算法[J].计算机辅助设计与图形学学报,1994,6(4):241-248.
  Ke Yinglin,Zhou Rurong.A new triangulation algorithm for 3D scattered points[J]. China Journal of CAD and CG, 1994,6(4):241-248.(in Chinese)
[6] Dyn N,Levin D,Rippa S.Data dependent triangulations for piecewise linear interpolation [J]. Journal of Numerical Analysis, 1990, 10(1):137-154.
[7] Alboul L,Kloosterman G,Traas C,et al.Best data-dependent triangulations[J]. Journal of Computational and Applied Mathematics, 2000,119(1):1-12.
[8] 张永春,达飞鹏,宋文忠.三维散乱点集的曲面三角剖分[J].中国图象图形学报,2003,8(12):1379-1388.
  Zhang Yongchun,Da Feipeng,Song Wenzhong.Surface triangulations based on 3D arbitrary point-sets [J]. Journal of Image and Graphics, 2003,8(12):1379-1388.(in Chinese)
[9] Koppel E.Approximating complex surfaces by triangulation of contour lines [J].IBM Journal of Research and Development, 1975,2:21-22.
[10] Cormen T, Leiserson C,Rivest R. Introduction to algorithms. 2nd Ed [M].The MIT Press,2002.21-23,149-155,204-209.
[11] Chen J. Computational geometry:methods and applications [M].Texas A & M University Press,1996.3-5.

备注/Memo

备注/Memo:
作者简介: 张永春(1968—),男,博士生; 达飞鹏(联系人),男,博士,教授,dafp@seu.edu.cn.
更新日期/Last Update: 2004-11-20