徐云云，江玉清
（合肥工业大学计算机与信息学院VCC研究室，安徽合肥230009）
摘要：服装排料是将衣片在满足一定约束下，将衣片尽量紧凑地排放在布料上。衣片多边形是排料算法的基本输入对象，工业上通常从PLT文件中获得衣片多边形信息。PLT文件是一个面向打印机的绘图文件，常在服装排料中得到应用，但它仅包含打印机的动作信息，没有衣片信息。因此提出一种面向服装排料的自动衣片多边形算法研究，根据PLT文件构造图G=（V，E），对图中的环进行提取过滤，得到衣片的边缘边框，最后寻找衣片的附加信息。通过上述方法最终实现了衣片及其附加信息的提取。
教育期刊网 http://www.jyqkw.com
关键词 ：服装排料系统；衣片样板；深度遍历；最短路径；Floyed算法
中图分类号：TN919?34 文献标识码：A 文章编号：1004?373X（2015）16?0084?04
收稿日期：2015?01?28
基金项目：国家自然科学基金项目：面向三维辐射屏蔽最优化的快速自动建模方法研究（11305205）；国家自然科学基金项目：拟人角色风格化运动生成研究（61370167）；国家自然科学基金项目：自然姿态交互界面中的一致性问题研究（61305093）
0 引言
服装排料又称排版，是指将服装的衣片样板在规定的面料幅宽内合理排放的过程[1?2]，即将纸样依工艺要求（正反面，倒顺向，对条、格、花等）形成能紧密啮合的不同形状的排列组合，以期望使用布料利用率最大化，达到降低产品成本的目的。衣片是一款衣服上的一块面片，通过打板系统[3]构造出来，为了方便服装的生产。
PLT 文件是利用HPGL（Hewlett Packard Graphics Language）[4?5]语言模拟绘图操作，用户可以快捷地得到图形的矢量信息，准确地解析PLT文件是一项基础却很重要的任务。PLT文件由于其独特的优点：文件指令丰富、易于读/写、构图灵活性较大、设备之间的兼容性强、内存占用较少、输入/输出调用效率高等，越来越受到工业界的欢迎，成为工业服装排料的主要输入文件之一。
在服装排料的过程中以衣片为对象进行排放[6?7]，那么能否正确从排料输入文件中提取出衣片将直接影响最终的排料结果。鉴于此，本文提出了一种能够快速高效的提取PLT中衣片样板的方法，详细说明了其实现过程，并给出了其基本实现方法。
1 问题分析
排料系统的PLT文件由衣片信息组成，其中衣片信息主要由2个部分组成：衣片的边缘边框和衣片的说明信息。具有以下特点：
（1）封闭性：衣片样板的边缘为封闭的闭合曲线，由一系列的顶点构成，如图1所示的衣片起边缘边框均是封闭的。
（2）不包含性：所有的衣片之间不存在相互包含的情况，即一个衣片不可能存在于另一个衣片的内部。
（3）其他信息：每个衣片有其所属的附加信息且位于衣片的内部，这些信息说明衣片的尺寸以及名称，如图2所示，衣片和其附加信息均为于边框内部。
上述衣片的特点可以作为寻找衣片的有力根据，下文中关于衣片提取的具体方法就是基于衣片此3个特点展开的。
2 衣片自动提取方法
根据上文对PLT文件中衣片的特点分析，本文归结出找出衣片样板的一般性方法。衣片样板由最外层边缘闭合曲线和内部的文字说明信息构成。所以本文提出首先找出衣片样板中的所有环，由于得到的环只是衣片的候选项，可能存在非法环的现象，所以需要对所有环进行过滤处理，得到所有衣片样板的边缘边框。最后找出衣片的所有衣片的附加信息。上述方法的关键在于寻找衣片的边缘边框，即寻找环的问题。对于一个图G=（V，E），可以利用深度遍历算法[8]快速找出其中所包含的环。由上述PLT文件特点，可以在初步提取出PLT文件中边的信息后，构造出图的数据结构。根据以上分析，本文提出首先根据PLT文件快速构图，然后对生成的图的数据结构采用深度遍历算法获得图中的所有环，进而对所得环进行过滤处理，最后寻找衣片文字说明信息的一般性方法。具体实现流程如图3所示。
2.1 由PLT文件构图
通过对样板衣片的PLT文件测试可知，文件具有顶点多，顶点之间的关联度小的特点，属于稀疏图。所以本文提出的方法采用邻接表的数据结构保存图的信息，以节省空间。
在将PLT文件构成图G=（V，E）时，对PLT文件中的每一个点将对应于图G 中的一个顶点，对PLT文件中由指令之间的组合所构成的边将看作图G 中的一条边，经过对PLT文件进行解析处理便可得到图的数据结构G=（V，E），下面以此作为对象，展开环的提取操作。
2.2 衣片样板的提取
按照前文提出的总体方针，关于衣片样板的提取，主要分为2步实现：首先提取出图中的所有环路；其次对所得的所有环路进行过滤，排除掉不是衣片边缘边框的非法环路，并加以处理。其中第1步可以通过改进的深度遍历算法实现。第2步实现后得到的所有环路中的非法环路可分为以下2种情况：
（1）附加信息中的环路，例如：“0”；
（2）如图4所示的2个衣片边缘边框相接的情况，即实际abcg 和cdef 分别为两个衣片，但在寻找环的过程中按照abcdefcg 的顺序得到了非法环路。
在算法实现上前面第1步采用深度遍历算法实现，第2步采用Floyed处理非法环，由文献[9]可知Floyed算法同样可以用来寻找图中的环路。本文之所以在第1步中利用深度遍历，而在第2 步中采用Floyed 算法，是因为Floyed算法处理的时间复杂度远大于深度遍历，特别是在像PLT文件数据量大的情况下更为明显。所以首先使用深度遍历实现，而第2步对部分环过滤处理时针对图4所示的情况只是少数现象，采用Floyed算法在整体时间上影响不会很大。
2.2.1 衣片的初提取
本文采用改进的深度遍历算法，即：以某点为起点的深度序列中，当访问到某点与第一个点相同时，且该序列中顶点的个数大于2的时候，即找到了环。由于根据PLT文件生成的图的连通分量可能不止一个，需要多次采用深度遍历。在深度遍历的过程中需要利用以下数据结构对访问过程中的信息进行保存。其中利用栈的结构，存放每次访问到的顶点。采用容器结构，存放访问过的边，在寻找环失败的时候利用其还原图中相关点的度的信息和其边的访问信息。
（1）从图的数据结构的顶点表的第一个节点开始，依次向后遍历，当顶点v0 的度数大于1 的时候，则以该顶点为起点进行深度遍历；当完成所有顶点的遍历之后，算法结束。
（2）从图中某个顶点x 出发，首先访问x，将x 顶点的度减1。找出x 顶点的第一个未被访问的相邻边，将该边的访问位置true；由于在无向图的邻接表中，一条边存在于两个顶点的边表中，需要将该边所指向点的度数减1，同时将该顶点中指向x 的边的访问位置true点。重复此步骤，直到刚访问过的顶点没有未被访问的邻接点，转步骤（3）；或是访问到的点等于深度序列的第一个点，转步骤（4）。
（3）返回前一个访问过的顶点，找出该顶点的下一个未被访问的邻接点x，访问该顶点，转步骤（2）；若返回的是深度序列的第一个点，且该点的所有邻接点均被访问过，说明由该点出发寻找环失败，对相应的顶点的度和其边的访问信息进行还原。
（4）此时说明找到了环，输出环。并将所得的环压入多边形序列中，转步骤（1）。
2.2.2 衣片的过滤
对一个无向图经过上述处理之后，得到了一系列的环，但是这些环不一定满足封闭多边形条件，需要这些多边形进行过滤和再处理。
针对衣片说明信息中的环路，可以利用其上的一个点是否在衣片内部进行快速判断，并将其加入衣片的数据结构中。
针对2个衣片边缘边框相接的情况，可以利用下述判断多边形是否为最小环的公式进行过滤。设一个多边形的边数为m，顶点的个数为n，若m-（n-1）>1，那么该多边形不是最小封闭多边形，如图5所示的环的边数m=8，顶点数n=7，则m-（n-1）=2>1。本文就是利用上述条件，将不满足最小环的多边形找出来进行再处理。按照上述条件对上操作获得的环进行过滤，得到需要再处理的环。采用如下方法获得封闭多边形：
（1）对于任意一个需要再处理的环，首先在其上寻找一组相邻的顶点；
（2）在该环中这2 个顶点之间除了直接相连的边以外的最短路径[10]。采用Floyed算法寻找2个点的最短路径算法，属于经典算法，文献[11]中做了比较详细的说明，此处不做过多说明。
至此经过上述2步对所有非法封闭环的处理，便可获得所有最小环。
2.3 寻找排料衣片附加信息
寻找排料衣片附加信息，是排料系统不可或缺的一个部分，主要利用衣片样板附加信息的内部性，即所有文字说明信息均存在于衣片样板的内部。其具体实现可从2个方面进行，从包容性考虑凡是在衣片边缘边框内部的均是衣片的边缘信息。从速度上考虑，对提取出衣片边缘边框后的图进行再处理，找出图中的最小子图，每一个最小子图为衣片附加信息中的一部分。所以在判定其是否为某块衣片的附加信息的时候，只需对该子图上的一个点进行判断即可。若该点在某块衣片边缘边框的内部，则可说明该最小子图为衣片的附加信息，并将其加入该衣片所属的数据结构中。
3 实验结果与分析
实验的配置环境如下：2.93 GHz Intel I3 CPU，2.0 GB 内存，NVIDIA GeForce GTS450 GPU，编程环境为Microsoft Visual Studio 2008，程序主框架采用C++编写，使用了stl等函数库。
本文实验所用的PLT文件包含5套衣片信息，总共包含衣片个数为87块。在经过初步提出所有环后显示的部分衣片如图5所示，可知存在非法衣片。
对上面出现的情况继续处理，经过过滤操作后，执行Floyed算法后可得到正确的衣片，如图6所示。
经过过滤操操作，对所有衣片样板进行排料，最后显示附加信息如图7所示。
4 结语
本文提出面向服装的自动衣片多边形提取算法研究与应用，首先将PLT文件解析成边的结构，其次根据这些边之间的关系，构造图的邻接表数据结构，接着在图的邻接表数据结构中根据DFS算法寻找环，最后过滤环寻找衣片的附加信息。经过这些步骤后，使之能够从仅仅包含顶点间矢量关系的PLT文件，读取出衣片样板的信息，供排料系统使用。
本文采用方法在对非法环进行处理的时候采用Floyed算法来寻找图中2点之间的最短路径来获得最终的最小封闭多边形，由于Floyed算法的时间复杂度比较大。如何快速的从非法环中获得正确的最小封闭多边形成为下一步的研究方向。
教育期刊网 http://www.jyqkw.com
参考文献
[1] 李旭，严寒冰，罗戎蕾.服装CAD中衣片设计和排料模块技术的研究[J].浙江工程学院学报，2000，17（3）：166?172.
[2] 陆美琴.服装排料技术的研究[D].上海：东华大学，2006.
[3] 陈义华.服装CAD的打板模式及其应用分析[D].北京：北京服装学院，2008.
[4] 蔡明.基于HPGL 文件的图元优化排序[J].计算机系统应用，2013（5）：203?206.
[5] 王建军.服装切割系统的软件研究与设计[D].杭州：浙江工业大学，2012.
[6] 汤跃忠.HPGL/2及RTL绘图仪语言编程指南[M].北京：清华大学出版社，1994.
[7] 张书伟，刘建群，施为，等.数控系统中HPGL图形文件识别与图形处理研究[J].组合机床与自动化加工技术，2013（2）：84?87.
[8] 田翠华，许卫平，陈玉明.深度优先遍历算法、随机布点法及回溯法在迷宫游戏中的应用[J].河北北方学院学报：自然科学版，2013（3）：19?24.
[9] 刘萍，冯桂莲.图的深度优先搜索遍历算法分析及其应用[J].青海师范大学学报：自然科学版，2007（3）：41?44.
[10] 贺鹏，殷亚君.最短路径算法浅析[J].甘肃科技，2010（2）：42?43.
[11] 陆锋.最短路径算法：分类体系与研究进展[J].测绘学报，2001（3）：269?275.
作者简介：徐云云（1991—），女，安徽怀远人，硕士研究生。主要研究领域为计算机图形学和图像处理与模式识别。
江玉清（1989—)，男，安徽怀宁人，硕士研究生。主要研究领域为计算机图形学和图像处理与模式识别。