摘要
提出了投影图中最小回路的概念和求全部最小回路的一种算法。首先构造图中各个顶点的关联边逆时针排列序列,然后分别从图中各个外围点出发沿外围边逆时针方向搜索,按照顺时针最小转角原则,寻找各个回路边,直到返回出发点得到最小回路,并逐步删除图中一些相关线条。最终可将图中线条全部删除,得到全部最小回路。算法简洁清晰,运算复杂度低。通过实例表明了算法是鲁棒的和高效率的。
This paper presents concept of minimum circle and an efficient algorithm for finding the minimum circle from single line drawings.Firstly, the edges which have a common vertex are arranged into a set in counterclockwise.Then each vertex on boundary serves as the starting point to search the minimum circle in counterclockwise, and the edge of circle is selected under the rule of turning minimum angle in clockwise.When coming back to the starting point, a minimum circle will be created.The certain line that is the starting edge of minimum circle and is included in two minimum circles is deleted from line drawing.Finally, all lines are deleted and all minimum circles are found.Test results show high efficiency and stability of this algorithm.
出处
《计算机工程与应用》
CSCD
北大核心
2010年第25期5-7,27,共4页
Computer Engineering and Applications
基金
国家自然科学基金重点项目No.50875210
兰州交通大学"青蓝"人才工程资助计划(No.QL-06-11A)~~
关键词
投影图
回路
算法
三维重建
line drawings
loop
algorithm
3D reconstruction
