计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (25): 5-7.DOI: 10.3778/j.issn.1002-8331.2010.25.002

• 博士论坛 • 上一篇    下一篇

求平面体投影图全部最小回路的算法

赵 军,高满屯,王三民   

  1. 西北工业大学 机电学院,西安 710072
  • 收稿日期:2010-03-10 修回日期:2010-07-06 出版日期:2010-09-01 发布日期:2010-09-01
  • 通讯作者: 赵 军

Algorithm for finding all minimum circles from single line drawings

ZHAO Jun,GAO Man-tun,WANG San-min   

  1. Northwestern Polytechnical University,Xi’an 710072,China
  • Received:2010-03-10 Revised:2010-07-06 Online:2010-09-01 Published:2010-09-01
  • Contact: ZHAO Jun

摘要: 提出了投影图中最小回路的概念和求全部最小回路的一种算法。首先构造图中各个顶点的关联边逆时针排列序列,然后分别从图中各个外围点出发沿外围边逆时针方向搜索,按照顺时针最小转角原则,寻找各个回路边,直到返回出发点得到最小回路,并逐步删除图中一些相关线条。最终可将图中线条全部删除,得到全部最小回路。算法简洁清晰,运算复杂度低。通过实例表明了算法是鲁棒的和高效率的。

Abstract: 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.

中图分类号: