期刊文献+

带权优化约束Delaunay三角化算法 被引量:7

Conforming Delaunay triangulation optimized by weighted method
下载PDF
导出
摘要 Delaunay细化算法是目前大多数约束Delaunay三角化算法的主要思想,针对其要求输入的约束条件中不能包含夹角较小的尖角的问题,给出了Delau-nay细化算法收敛的充分条件,并通过在尖角点和尖角边处引入带权点和带权Delau-nay空圆/球准则的方法提出了一种带权优化约束Delaunay三角化算法,解决了经典的细化算法在尖角处算法不收敛时需引入辅助控制区域以及过多辅助点的问题,对算法的收敛性进行了分析,给出了相应的算法应用实例,可以应用于复杂几何对象的科学计算和工程分析. As a conforming Delaunay triangulation (CDT) algorithm, Delaunay refinement method has widely application both in theory and practice. It always fails to terminate when there are some small angles intersected by input geometry constraints, so a sufficient condition for termination of Delaunay refinement method was introduced and a new conforming Delaunay triangulation algorithm was presented, which is based on Delaunay refinement method and optimized by weighted method. The algorithm imposes no angle restrictions on the input geometry domains by setting weight value to point where input constraints intersected with small angles and applying the rule of weighted Delaunay circumcircle/cireumsphere claim to generate Delaunay triangular mesh, and it avoids appending any additional complex region and need not adding any Steiner points to mesh. Analysis of termination and some results applied by this algorithm were also presented. This method will be useful in the computation and analysis of complicated geometry objects.
出处 《北京航空航天大学学报》 EI CAS CSCD 北大核心 2005年第12期1284-1288,共5页 Journal of Beijing University of Aeronautics and Astronautics
关键词 计算机图形学 三角剖分 算法 约束DELAUNAY三角化 Delaunay细化算法 带权 computer graphics triangulation algorithms conforming Delaunay triangulation Delaunay refinement weighted
  • 相关文献

参考文献11

  • 1Ruppert J.A Delaunay refinement algorithm for quality 2-dimensional mesh generation[J].Journal of Algorithms,1995,18(3):548~585
  • 2Shewchuk J R.Tetrahedral mesh generation by Delaunay refinement[A].Proceedings of the 14th ACM Symposium on Computational Geometry[C].New York:ACM,1998.86~95
  • 3Shewchuk J R.Delaunay refinement algorithms for triangular mesh generation[J].Computational Geometry,2002,22(1-3):21~74
  • 4Cheng S W,Dey T K.Quality meshing with weighted Delaunay refinement[A].Proceeding of the 13th ACM-SIAM Symposium on Discrete Algorithms[C].New York:ACM-SIAM Press,2002.137~146
  • 5Li X Y.Generating well-shaped d-dimensional Delaunay meshes[J].Theoretical Computer Science,2003,296(1):145~165
  • 6Cheng S W,Dey T K,Edelsbrunner H,et al.Silver exudation[J].Journal of the ACM,2000,47(5):883~904
  • 7Murphy M,Mount D M,Gable C W.A point-placement strategy for conforming Delaunay tetrahedralization[A].Proceeding of the 11th ACM-SIAM Symposium on Discrete Algorithms[C].New York:ACM,2000.67~74
  • 8Cohen-Steiner D,De Verdiere E C,Yvinec M.Conforming Delaunay triangulations in 3D[A].Proceeding of the 18th Annual Symposium on Computational Geometry[C].New York:ACM,2002.199~208
  • 9Cheng S W,Poon S H.Graded conforming Delaunay tetrahedralization with bounded radius-edge ratio[A].Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms[C].New York:ACM,2003.295~304
  • 10Edelsbrunner H.Geometry and topology for mesh generation[M].New York:Cambridge University Press,2001

二级参考文献10

  • 1Bowyer A.Computing dirichlet tessellations[].Computer Journal.1981
  • 2Edelsbrunner H,Mucke E P.Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms[].ACM Transactions on Graphics.1990
  • 3Edelsbrunner H,Shah N R.Incremental topological flipping works for regular triangulations[].In: Proc the th Annual ACM Symposium on Computational Geometry Berlin Germany.1992
  • 4Facello M.Implementation of a randomized algorithm for Delaunay and regular triangulations in three dimensions[].Computer Aided Geometric Design.1995
  • 5Vigo M.Two simple flipping algorithms for computing regular triangulations in the plane[]..2000
  • 6Eelsbrunner H.Weighted alpha shapes[]..1992
  • 7Boissonat J,Teillaud M.On the randomized construction of the Delaunay tree[].Theoretical Computer Science.1993
  • 8Aurenhammer F.Voronoi diagram-A survey of a fundamental geometry data structure[].ACM Computing Surveys.1991
  • 9Lawson C L.Generation of a triangular grid with applications to contour plotting[]..1972
  • 10Lawson CL.Software for C1surface interpolation[].Mathematical Software III.1977

共引文献2

同被引文献69

引证文献7

二级引证文献43

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部