APP下载

无向图在计算机绘图中的应用

2016-05-30张强

软件工程 2016年1期

张强

摘 要:本文把笔式绘图仪绘图过程时间最少的调度问题转换为在加权无向图中求解最优H-回路,并且利用最小生成树、欧拉回路、非二部图赋权匹配的算法给出了一种近似调度算法,旨在减少绘图仪移动空走时间和换笔时间,从而提高绘图效率。本算法经RP-MF160等绘图仪应用,效率提高约15%。

关键词:笔式绘图仪;调度算法;H-回路;加权图匹配

中图分类号:TP301 文献标识码:A

1 引言(Introduction)

计算机绘图是CAD和CAM的重要组成部分。随着计算机应用技术的飞速发展,目前已广泛应用于各个领域。

笔式绘图仪在完成一幅图的绘制时,其总时间消耗由三段组成:即实际绘图时间,抬笔移动空走时间以及更换画笔时间。由于实际绘图这段时间是必不可少的,因此,为了减少总时间消耗,提高绘图仪的使用效率,必须尽可能地减少另两段的时间耗费,即减少抬笔移动空走时间和换笔时间。这样一来,我们实际上面临的是一个绘图仪绘图过程的时间优化问题,解决的主要途径就是设计一个高效的绘图过程调度算法。目前,在设计绘图仪绘图过程时,采用的主要方法基本上是根据一幅图上各个基本图形的分布情况、相对位置以及程序设计人员的实际编程经验进行安排,还没有一个公认高效的调度算法作为依据。因此,不难想象,在某种复杂情况下,采用上述方法将会大大增加绘图仪绘图过程的时间开销,降低其使用效率。为此,下面将针对绘图仪绘图建立一种具体的数学模型,在此基础上给出一种相应的调度算法,并对其时间复杂度进行分析,旨在尽可能地减少绘图时的抬笔移动空走时间和换笔时间,降低其时间耗费。……

登录APP查看全文