摘 要： 随着Internet的迅速发展和个人电脑的普及，出现了数量惊人的电子文档，促使设计工作者从传统的设计方式向计算机辅助设计过渡，在计算机辅助设计中经常要过度的点击鼠标来选择自己需要的图形，有时很难表达自己的设计思想，本文将图形通过图形矢量化中直线的拟合和合并算法，将曲线进行直线拟合，并通过短直线进行合并，还原设计者的意图，能很好地让设计者随心所欲地表达自己的设计思想，从而达到提高工作效率的目的。
关键词：直线拟合；图形矢量化；图形识别；直线合并 1、 引言 在计算机辅助设计中用户通过图形化软件通过鼠标点击来选择自己的图形，当有许多预定义的图形时，用户很难记住在哪里选择自己需要的图形，这给设计者在输入上带来了不方便，并且在有些设计用户需要随时随地地记录其设计思路，而不是拘泥于某一个细节，是用户感觉起来输入不自然，并且这些操作不适合在小型的终端设备中应用。对此我们很多时候都需要自己进行手绘图形，但是手绘图形在很多时候都不是很精确，设计草图和设计者的本意相差很大，这个问题的关键在于计算机辅助设计软件对手绘图形进行识别，解决手绘图形的识别问题将对设计工作者来说可以大大减轻他们的工作负担。 2、 直线拟合算法 对于手绘的曲线，我们采用动态分割的方法来对曲线进行短直线拟合，通过短直线拟合我们可以将手绘的曲线变成直线组合的图形，具体步骤如下： (1) 建立一个邻接表，将曲线的端点存入邻接表中。 (2) 连接每条边的两个端点A 、B 构成直线L , 如下图1 中虚线所示, 计算边上每个点至L 的距离, 找到距L 最远的点P , 若P 至L 的距离大于阈值k , 则连接A 、P。 (3) 在A、P之间的边上重复第一步的做法,直至找到一点X ,使边上A与X之间的点距直线A X的距离均小于阈值k。此时A与X之间的曲线可用直线A X拟合,并将X保存。 (4) 在X与B之间的边上重复步骤(1)和(2) ,即可将整条边(曲线)用短直线拟合。拟合的结果如图1右所示。拟合之后的邻接表无需再存储每条边上的点,但需要增加节点数目,因为拟合要增添新的节点。 图1直线拟合曲线实例 3、直线合并算法 在对手绘图形进行直线拟合后，我们将拟合后的短直线进行合并，在合并的过程中我们主要是采用对短直线所在的邻接表进行搜索，同时对一些错位的直线进行合并，直线合并算法具体步骤如下： (1) 在图中有两条近似直线的线段以较小的角度相交，细化后形成了C、D两个新的节点，由于后C、D的存在，我们在进行直线合并算法之前先建立图形中点和边的邻接表，故我们应该在邻接表中应该存入5条边AC、BC、CD、DE和DF。 (2) 从节点栈底节点A开始处理，通过节点A的边ＡC，将AC作为搜索过程中的起始边，再通过节点C开始搜索通过节点C的边BC、CD考察(A,C,D)和(B,C,D)发现只有一组点(A,C,D)属于同一条直线，可得AC只属于一条直线，因此将AC标记，表示该边已搜索过以后不再搜索。 (3) 从D开始搜索，从邻接表可以搜索到DE和DF，考察(C,D,E)和(C,D,F)，发现这两组点都可以属于一条直线，表明C、D属于两条不同的直线，因此此时不能标记CD，以后还要搜索CD。 (4) 搜索E、F发现邻接表中所有的边都已经搜索完毕，考察ACDF和BCDE，同时通过E、F两个点反向搜索，发现ACDF为一条直线，因此从节点E出发将ED、CD和BD合并为一条直线。 (5) 建立新的邻接表来存储合并后的边，合并结束。 图2 直线合并示意图 4、图形识别 根据邻接表快速生成一个直线模型,设分支节点的块数为mL，节点数为nL，若nL/mL>δ(δ为阈值),则该分支为一直线，其参数用该直线方程与首末节点矩形上下边的交点来表示，宽度为分支节点宽度的平均值。引入权的概念，某一节点的权这里被定义为该节点的y向长度,因此前述直线的识别条件修正为 式中，j=1，2，…，nL为在直线上的点；i=1，2，…，mL为分支的所有节点；w是分支节点的权。引入记忆因子F，F初始化为0；当第一次直线匹配不成功时，F=F+1，分别取次首末节点矩形中点进行匹配，依次下去；如果，即连续次匹配不成功，则可认为该分支不是一直线分支；若0
