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

doi:10.3778/j.issn.1002-8331.2010.25.002

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

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

赵军，高满屯，王三民

西北工业大学机电学院，西安 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

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

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

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.

中图分类号:

TP391.41

赵军，高满屯，王三民. 求平面体投影图全部最小回路的算法[J]. 计算机工程与应用, 2010, 46(25): 5-7.

ZHAO Jun，GAO Man-tun，WANG San-min. Algorithm for finding all minimum circles from single line drawings[J]. Computer Engineering and Applications, 2010, 46(25): 5-7.

[1]	刘光帅，李柏林，何朝明. 分段光滑曲面重构的面片图稀疏优化方法[J]. 计算机工程与应用, 2011, 47(4): 22-25.
[2]	张聪，桂志国. 噪声控制的图像非线性锐化方法[J]. 计算机工程与应用, 2011, 47(4): 154-156.
[3]	孙力胜，郑建靖，陈建军，戴美晃，梁义. 二维自适应前沿推进网格生成[J]. 计算机工程与应用, 2011, 47(3): 146-148.
[4]	张莹，李言俊，张科，王红梅. 基于NSCT的红外与可见光图像融合[J]. 计算机工程与应用, 2011, 47(3): 196-198.
[5]	刘伟锋，李树娟，王延江. 人脸表情的LBP特征分析[J]. 计算机工程与应用, 2011, 47(2): 149-152.
[6]	段建伟，彭国华，胡玫瑰. 曲面三参数binary细分法[J]. 计算机工程与应用, 2011, 47(2): 194-196.
[7]	汤敏. 标准细胞神经网络完全稳定性分析及初步应用[J]. 计算机工程与应用, 2011, 47(2): 173-175.
[8]	胡晓东¹，骆剑承¹，吴炜¹，程熙¹，沈占锋¹，贾银芳². 手写粉笔数字自动识别方法研究[J]. 计算机工程与应用, 2011, 47(2): 182-184.
[9]	陈展展，汤进，罗斌，孔敏. 基于最优子序列双射的骨架树匹配[J]. 计算机工程与应用, 2011, 47(1): 162-165.
[10]	郭华磊^1，2，马苗¹. 改进的模糊C均值聚类的图像分割算法[J]. 计算机工程与应用, 2011, 47(1): 176-178.
[11]	杨茂龙^1，2，王远方³，孙权森²，夏德深². 偏最小二乘改进算法与特征抽取[J]. 计算机工程与应用, 2011, 47(1): 179-181.
[12]	原魁，肖晗，何文浩. 采用FPGA的机器视觉系统发展现状与趋势[J]. 计算机工程与应用, 2010, 46(36): 1-6.
[13]	杨福艳，周明全，邓擎琼. 勾画式交互的网格模型分割[J]. 计算机工程与应用, 2010, 46(36): 175-177.
[14]	赵军，肖冰. 基于边界的二次曲面重建与分类[J]. 计算机工程与应用, 2010, 46(35): 199-201.
[15]	吴刚. 隐式多项式曲线的信息相似性分析研究[J]. 计算机工程与应用, 2010, 46(35): 228-230.

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

Algorithm for finding all minimum circles from single line drawings

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics