| 摘 要: 本文把笔式绘图仪绘图过程时间最少的调度问题转换为在加权无向图中求解最优H-回路，并且利用最小 生成树、欧拉回路、非二部图赋权匹配的算法给出了一种近似调度算法，旨在减少绘图仪移动空走时间和换笔时间，从 而提高绘图效率。本算法经RP-MF160等绘图仪应用，效率提高约15%。 |
| 关键词: 笔式绘图仪；调度算法；H-回路；加权图匹配 |
|
中图分类号: TP301
文献标识码: A
|
|
| The Application of Non-oriented Graph in Computer Drawing |
|
ZHANG Qiang
|
( Guangzhou Commanding School of Frontier Force, Guangzhou 510663, China)
|
| Abstract: This paper formalizes the problem of drawing procedure schedule costing minimal times in pen-plotter into the problem of solving optimal H-cycle in weighted graph,and given an approximate algorithm using minimal spanning tree,E-cycle,non-bipartite weighted graph mat-ching.This algorithm can remarkably reduce the times for raisingpen empty moving and excha-nging pen of pen plotter,therefore improve drawing efficiency.This algorithm was applied to the plotter RP-MF160,increased efficiency about 15%. |
| Keywords: pen-plotter;schedule algorithm;H-cycle;weighted graph matching |
