三角网格模型的基本群分割

摘要：

提出一种有效的三角网格模型分割方法.用Dijkstra算法求出三角网格模型上任意给定一个基点到其余顶点的最短路径树；求出该模型对偶图的最大生成树,且对偶图的边与该最短路径树的边不相交；找出该模型上所有既不属于最短路径树也不和最大生成树相交的边,这些边分别与最短路径树组成的最短环集合就是给定基点处的基本群,沿着这些最短环就可以把网格分割成一个拓扑同胚于圆盘的区域.实验结果表明,该分割方法可以快速、有效地实现网格的分割.

关键词：网格分割、基本群、最短路径树、对偶图、最大生成树

所属期刊栏目：47

分类号：TP391.41(计算技术、计算机技术)

资助基金：国家自然科学基金the National Natural Science Foundation of China under Grant 60873175;安徽省教育厅自然科学基金KJ2010B423,KJ2011Z284

在线出版日期：2012-03-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：180-182