图形轮廓分层路由提取的MST生长算法  

MST Growth Algorithms for Hierarchical Routing Extraction of Graph Outline

作　　者：覃斌[1] 阎春平[1] 刘飞[1] 

机构地区：[1]重庆大学机械传动国家重点实验室,重庆400030

出　　处：《计算机辅助设计与图形学学报》2011年第2期256-262,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(50975299);国家"十一五"科技支撑计划(2006BAF01A27)

摘　　要：在以可达路径决策为核心的图形轮廓提取中,为有效地解决路由决策困难及路径特征值精度等问题,提出了图形轮廓分层路由提取的MST生长算法.该算法将图形路由拓扑结构划分为域内路由和域间路由.域内路由对非支配点关联路径进行重组,建立以支配点为节点的图形有权无向图;域间路由以无向图最小生成树MST为基础,利用树节点间唯一可达特性构造MST生长算法.最后综合这2个层次实现完整的图形轮廓提取.通过算例及应用证明了文中算法的可行性和有效性.For there exist routing decision making difficulties and weak precision of path eigenvalues in graph outline extraction with reachable path decision as its core, the MST growth algorithms are proposed to hierarchically extract graph outline. The topological structure of graph routing is partitioned into two parts, including intra domain routing and inter-domain routing. By recombining coherent paths of no dominated points, the weighted undirected graph with dominated points as its nodes is established in intra-domain routing. And based on MST of the undirected graph, utilizing the unique teachability between any two trees nodes, the MST growth algorithms are constructed in interdomain routing. Then, the entire graph outline is extracted with the above processes achieved. An example and a practical application validate the feasibility and effectiveness of the proposed algorithms.

关 键 词：图形轮廓提取 分层路由 有权无向图 最小生成树 路由算法 

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