（机械制造及其自动化专业论文）二维钣金排套料的算法研究及软件设计.pdf

一 国防科学技术大学研究生院学位论文 摘要 排样问题是一个n p 难几何优化问题，广泛的应用于钣金切割、服装、皮革等行业， 长期以来，一直是c a d c a m 和自动化领域的研究热点之一。本文根据排样问题的特点， 针对任意形状的二维不规则钣金件排样问题的算法进行了研究，提出了局部贪心的搜索方 法，并对该方法涉及的若干具体问题进行了研究。本文有以下一些成果： 夺 提出了钣金优化排样的实用算法局部贪心法。该方法基于现有的优化排样算法， 以排样利用率为目标，先将一些小的样件充填到其他样件的孔洞中形成局部具有高利 用率的群组，然后对群组进行排样得到总体的初步排样结果，最后在初排结果中充填 群组间的缝隙，得到整体优化排样结果。算法采用试排一评估一再试排的循环计算， 比一些经典算法中的递归计算具有更高的计算效率。 夺改进了n f p ( n o f i t p o l y g o n ) 的求法。n f p 是判别两个多边形的碰撞关系的一个非常有 效的工具，在排样算法有很重要的作用。但由于求解两个凹多边形的n f p 比较困难， 长期以来限制了它的应用。本文利用闵可夫斯基和( m i n k o w s k is u m ) 和斜度图，得 出一种n f p 的求法，该方法比传统方法更简单和容易使用。 夺给出了任意图形的多边形逼近、非凸图形的凸组合、利用n f p 做碰撞检测和扫描线搜 索图形间缝隙等方法。这些方法能够很好地解决排样中的局部优化问题，提高排样利 用率。 夺设计开发了钣金排套料c a d c a m 软件排样系统。将本文提出的算法应用于生产实践。 该系统采用v c + + 直接从底层开发，主要有图形输入输出、特征处理、排套处理、n c 前后置处理四大模块。系统开发过程中着重研究了开发原理并解决了一些关键技术， 在解决二维图形的编辑、钣金切割中的设计计算、优化排样、数控工艺等问题方面取 得很大的成功，在几何与切割特征设计方面采用了新的思想和方法，尤其成功解决了 切割引线与切割路径优化的实用问题。 关键词：c a dc a m 钣金排样问题优化算法 a b s t r a c t c u t t i n gs t o c kp r o b l e m sf r e q u e n t l yo c c u ri ni n d u s t r i e so fs h e e tm e t a lc u t t i n g , a p p a r e la n d f u r n i t u r ep r o d u c t i o n ，a n da r en p h a r dp r o b l e m sm a t h e m a t i c a l l y i th a sb e e nar e s e a r c h i n gf o c u s i nt h ef i e l d so fc a d c a ma n da u t o m a t i o n t h i sp a p e rm a k e sai n v e s t i g a t i o no nt h en e s t i n g a l g o r i t h m so fa r b i t r a r ys h e e tm e t a lp a r t sa n dp u t sf o r w a r dal o c a lg r e e d ys e a r c hm e t h o d t h e k e y n o t e so f t h i st h e s i sa r ea sf o l l o w s ： ah e u r i s t i cs e a r c hm e t h o df o r2 dc s p si sp r e s e n t e d a i m i n ga ts t o c ke f f i c i e n c ya n db a s e d o np r e s e n tp a c k i n ga l g o r i t h m s ，t h i sm e t h o df i r s tn e s t ss o m es m a l li t e m si n t ot h eh o l e so ft h e b i go n e ss oa st of o r mas e q u e n c eo fg r o u p sw h i c hh a v eab e t t e rl o c a ls t o c ke f f i c i e n c y , t h e np a c k st h e s eg r o u p st og e tf l p r e l i m i n a r yg l o b a lr e s u l t ，a n di nt h ee n df i l l st h eg a p s a m o n gt h eg r o u p si nt h ep r e v i o u sr e s u l tt og e tt h el a s to p t i m a lr e s u l t t h em e t h o do f c a l c u l a t i n gt h en of i tp o l y g o n ( n f p ) i si m p r o v e d t h en f p i sap o w e r f u la n d e f f e c t i v et o o lf o rh a n d l i n gt h eg e o m e t r yr e q u i r e df o rar a n g eo fs o l u t i o na p p r o a c h e st o2 d i r r e g u l a rc s p s h o w e v e r , u n l e s s 越lt h ep i e c o sa r ec o z t v e x ，i ti sd i f f i c u l tt oi m p l e m e n t ，a n di t s u s eh a st h e r e f o r eb e e ns o m e w h a tl i m i t e d a l t h o u g ht h em e t h o di sb a s e do np r e v i o u s a p p r o a c h e sw h i c hu s et h em a t h e m a t i c a lc o n c e p to fm i n k o w s k is t i l l i s t h i sn e wm e t h o dc a n b ee a s i e rt ou n d e r s t a n d t h er e s u l ti sa na p p r o a c ht h a ti sb o t hv e r yg e n e r a la n de a s yt ou s e t h e p a p e rg i v e so u tam e t h o dt oc o m b i n en o n - c o n v e xf i g u r e si n t oac o n v e xo n e ，am e t h o dt o g e tb u m p i n gr e g i o nb yu s i n gn f p , a n das c a n n i n g - l i n em e t h o dt os e a r c ht h eg a p sa m o n g a d j a c e n tf i g u r e s ；t h e s em e t h o d sc a nw e l ls o l v et h el o c a lo p t i m a lp r o b l e mi np a c k i n ga n d n e s t i n gp r o c e s s ，a n di m p r o v et h es t o c ke f f i c i e n c y ac a d c a ms o f t w a r ef o rc u t t i n ga n dn e s t i n go fs h e e tm e t a l si sd e s i g n e d s o m ed e s i g n i n g a n dd e v e l o p i n gp r i n c i p l e sa r cp r e s e n t e da n ds o m ek e yt e c h n i q u e so fo n ec a d c a m s o f t w a r ef o rc u t t i n ga n dn e s t i n go fs h e e tm e t a l sa r es o l v e d t h es o r w a r em a i n l yg i v e s r e s o l u t i o n sf o rd e s i g na n dc a l c u l a t i o n ，o p t i m a lp a c k i n ga n dn e s t i n g ，a sw e l la sn u m e r i c a l c o n t r o lp r o c e s si nc u t t i n go fs h e e tm e t a l s al o to fn e wi d e a sa n dm e t h o d sa r eu s e di nt h e s o f t w a r ef o rg e o m e t r ya n df e a t u r ed e s i g na n dh e u r i s t i cs e a r c hs t r a t e g i e s i np a r t i c u l a r , t h e s o f t w a r es u c c e s s f u l l ys o l v e st h ep r o b l e m so fc u t t i n gl e a d e r - l i n ea n dt o o lp a t ho p t i m i z a t i o n k e y w o r d s ：c a dc a ms h e e tm e t a lc u t t i n gs t o c kp r o b l e ma l g o r i t h m 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：三丝笾垒挂奎盘的篡洼篮窒及熟往遮盐 学位论文作者签名：二豸a 叁 日期：川p 年f f 月，夕日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：三丝堡垒扯套粒煎篡洼丛窒丛鏊往遮盐 学位论文作者签名： 作者指导教师签名： 日期：沙x 年f 月孑 日 日期：c 2o 嘶年f ，月2 审日 国防科学技术大学研究生院学位论文 第一章绪论 【本章摘要】本章主要介绍排样问题的基本概念及相关问题，着重介g t q y - - 维排样问题及 其在工业中的应用。根据二维排样技术的研究现状，提出了本文的主要研究工作内容和意 义。本章的最后简要介绍了本文的章节组织。 - 1 1 排样问题描述 排样问题( 有些文献称为装箱问题或嵌套问题) 是指给定一排样空间( 一维、二维或 多维) 和若干待排样物体，找到种在排样空间内摆放排样物体的方法，使得排样物体互 不重叠的情况下排样区域的几何占有率最高。排样问题通常表现为两种形式：一种为待排 放的对象固定，要求占用最小的区域；另一种为排样空间固定，研究放入最多的待排对象。 通常按维数将排样问题一维排样、二维排样、三维排样和多维排样。图1 1 是一个典 型的一维排样实例。给定作为原料的管材，从上面切割给定数目和长度的管材零件，目的 是使得需要的原料管根数最少。图1 - 2 需要从一宽度一定长度无限的板料上切割形状和数 量给定的零件片，目的是使得需要板料的长度最小。这是一个二维排样。图1 3 是集装箱 装货的问题，将一些形状大小不一的箱子装入集装箱，使占用的集装箱数目最少，这是三 维排样问题。 图1 - 1 管材切割实例 国防科学技术人学研究生院学位论文 原材料扳材排样方法 图1 - 2 二维矩形排样 集装箱 待装箱体装箱结果 图1 - 3 集装箱装货 本文要研究的是钣金切割排样问题，即要求在一块( 或者多块) 固定大小的板料上( 后 文称容器) 切割出尽可能多的形状各异的工件使得材料耗费最少。这是二维排样优化问题， 这类问题在工业中应用最广泛。 排样问题可以从两个方面加以说明，一个是排样过程中的几何问题，主要是针对规则 或者不规则形状的零件，如何确定零件的最佳排放位置，检测排样位置的合理性以及相关 算法。另一个是排样的调度问题，即如何从参加排样的零件库中选出最优的排样零件，如 何得到一个优化的零件排样顺序。无论是几何问题还是调度问题，都是非常复杂的问题。 这种复杂性一方面来源于零件形状的不规则性，同时也与参与排样零件的多样性以及零件 的批量、生产周期、排样方向性要求等有关。这些相互没有明确逻辑关系的因素，很难用 统一的数学公式表达，因此也很难达到一个预期的全局最优解。 1 2 二维排样问题的研究发展及现状 排样问题由来已久，早期主要研究简单的矩形排样。六十年代初，g i l m o r e 和g o m o 一5 。1 用线性规划的方法和背包算法研究了矩形图形的二维排样问题。从七 年代以来，由于实 际应用的需要，人们开始对不规则零件的排样问题进行了研究。起先采用的办法是将不规 口 l ；佃j 森 国防科学技术大学研究生院学位论文 则的零件用规则零件来代替，然后按照规则零件的方法实现排样。其中应用最多的是最小 包络矩形( 所谓最小包络矩形就是指包含多边形的面积最小的矩形) 。如果零件的形状和矩 形相差甚远，这种方法的效果就比较差。1 9 7 6 年，a d a m o w i c z 和a l b a n o 改进了这种方法 s h ，他们将几个零件组合，然后再寻找这个组合的最小包络矩形。除了使用矩形以外，也 有人使用三角形、四边形、五边形以及六边形，因为这些形状可以相互完全靠接，从而能 够达到较为理想的排样结果。1 9 9 1 年，k a r o u p i 和l o f t u s 将这种方法扩展到曲线和凹多边 形【8 ”，即先用一个凸多边形嵌套这些曲线和凹多边形，然后再将这个多边形转化成正六边 形。然而，当零件的形状为近似矩形时，这种方法在边角处仍然会产生较多的废料。总之， 这些方法都是用规则零件替换不规则零件，应用很受限。一种对某种形状零件很有效的方 法对另一种形状的零件可能就效果很差。 随着计算机技术的发展和人工智能的发展，从上世纪9 0 年代开始，传统的爬山法 ( h i l l d i m b i n 曲已很少使用，启发式搜索方法逐渐成为人们研究的热点。1 9 9 2 年j a l n 等人提 出的模拟退火算法【2 1 】，1 9 9 3 年b l a z e w i c z 等人提出的t a b u 搜索【3 0 】，1 9 9 5 年k r s g e r 提出的 遗传算法【2 5 1 。这三种算法，在求解的问题比较小时都可以得到很好的解，但当问题很大时， 遗传算法耗时要长，并且解的质量要低一些，而模拟退火和t a b u 搜索的解差不多，并且都 好于遗传算法f 1 8 j 。对于多边形的排样，b u r k ee 等人提出的蚂蚁算法p 2 j 和模拟退火算法f z 3 ， 这两个算法都是基于n f p ，在排样凸多边形时可以取得良好的效果。1 9 9 7 年h o p p e re + 提 出遗传算法f i 7 ，由于对非凸多边形也能得到不错的解，目前遗传算法的应用较为广泛。这 些启发式算法在解各自的问题时都能得到很好的解，但是当解一个包含有各种形状排样件 的完整问题时，目前这些方法都不能胜任。在9 5 年d a n i e l s 提出一种基于m i n k o w s k is h i n 的算法f 6 2 】，但由于该算法过于复杂，应用起来非常困难。 目前研究的热点是遗传算法、蚂蚁算法、模拟退火算法等，下面分别做介绍： 遗传算法( g a 。g e n e t i ca l g o r i t h m s ) 遗传算法是模拟生物在自然环境中的遗传和进化 过程而形成的一种自适应全局优化概率搜索算法。生物在进化发展过程中，总是以优者生 存延续下去，劣者被淘汰而消亡的方式，发展和进化自身。遗传算法正是模仿了生物的这 一进化原理，并引用了随机统计理论形成的优化搜索计划，用于在人工系统中实现特定目 标的优化。当然，并不是完全模仿生物界复杂的进化机制，而是利用其适当简化的形式。 遗传算法从随机产生一组候选解开始，通过模拟自然选择和遗传过程中发生的交叉、选择 和变异等现象，在候选解中搜索最优解，并利用原有优良解的信息来加快收敛速度。 1 9 7 5 年，h o l l a n d 教授在其专著a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s ) ) 中全面 国防科学技术大学研究生院学位论文 地阐述了遗传算法，标志着遗传算法的诞生。8 0 年代中期，遗传算法在美国成为人工智能 研究的一个热点，目前，遗传算法己经成为人工智能领域的热点，在机器学习、工程优化、 任务调度、图像处理等领域得到了成功的应用。 遗传算法具有良好的全局搜索能力，但同时应用实践表明，在遗传算法的应用中也会 出现一些不尽人意的问题，这些问题中最主要的是它容易产生早熟现象、局部寻优能力较 差等。 蚂蚁算法( a n t a l g o r i t h m s ) 蚂蚁算法是模拟了自然界中蚂蚁的行为特性，通过其内在 的搜索机制，取得组合优化的一种算法。研究表明，蚂蚁具有找到蚁巢与食物之间的最短 路径的能力，并且能随环境的变化而变化，适应性地搜索新的路径，产生新的选择。蚂蚁 在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物一一信息激素 ( p h e r o m o n e ) ，使得一定范围内的其它蚂蚁能够察觉到并由此影响它们以后的行为。当一些 路径上通过的蚂蚁越来越多时，其留下的信息素轨迹( t r a i l ) 也越来越多，以致信息素强度增 大( 但会随时间的推移会逐渐减弱) ，后来蚂蚁选择该路径的概率也越高。选择某路径的 蚂蚁越多，则在该路径上蚂蚁所留下的信息素的强度就越大，而强度大的信息素会吸引更 多的蚂蚁，从而形成一种正反馈。通过这种正反馈，蚂蚁最终可以发现最短路径。蚂蚁算 法即利用此正反馈以获得最优解。 蚂蚁算法的优点主要在于：大规模的并行计算，使蚂蚁避开了局部最优；采用正反馈 机制，收敛速度加快；使用构造性的贪婪算法，能在搜索的早期阶段找到好的可接受的解。 模拟退火( s i m u l a t e da n n e a l i n ga l g o r i t h m s ) 模拟退火算法是从自然界固体退火过程中 得到启发并从中抽象得来的解决优化问题的一种随机优化算法，由k i r k p a t r i c k 等于1 9 8 3 年首先提出来的，这种算法用于求解优化问题的出发点是基于物理现象中固体物质的退火 过程与一般优化问题间的相似性，在对固体物质进行退火处理时，常先将其加温至使其粒 子可自由运动，随着温度的逐渐下降，粒子逐渐形成低能态晶格。若在凝结点附近的温度 下降速度足够慢，则固体物质定会形成最低能量的基态。优化问题则是每一个点代表一个 解，不同的解有不同的目标函数。 模拟算法最显著的特征是以一定的概率接受使目标函数值增大的移动，即恶化解，所 以能从局部最优解的“陷阱”中爬出来而不是简单地终止于局部最优解上，具有全局收敛 性，并且在理论上已经证明了只要系统过程满足一定的要求( 系统温度无限趋于零度且在 每温度下模拟充分) ，算法将渐近收敛于全局最优解。由于遗传算法局部寻优能力差， 而模拟退火算法却具有很强的局部搜索能力，因此通常将遗传算法与模拟退火算法相结 国防科学技术大学研究生院学位论文 合，互相取长补短，称为遗传模拟退火算法。 1 3 课题来源及意义 本课题来源于广州市科技攻关项目“钣金排套料c a d c a m 软件系统的设计与开发” ( 0 2 3 g 2 0 2 1 ) 。该项目主要研究二维钣金排套料的算法及软件设计。 二维切割排样在工业领域应用非常广泛，尤其是需要将大的板料或长条切割成小片行 业，通常用于切割的原材料为钢材、玻璃、木头，塑料、皮革、布料等。如大规模集成电 路的制造中，将芯片合理地布置在电路板上就是排样问题，该问题主要涉及到矩形排样， 目前研究成果已经比较成熟。钣金、冲压、造船工业中，将零件从大的钢板上切割或冲压 下来，为了最大程度减少废料，就需要一种合理的切割方法，通常用来切割的钢板是矩形， 因此属于矩形内不规则零件的排样问题。最复杂的是皮革工业和制衣工业，一般来讲，用 于原料的皮革是不规则的，要割下的皮革片也是不规则的。 尽管排样问题在许多行业中都有非常广泛的应用，而且经济效益和社会效益也非常可 观的，但由于其复杂性，许多行业还大多数依靠人工进行，不仅浪费人力和时间，而且排 样的效果与人有关。而利用计算机辅助优化排样不仅可以大大减轻工作人员的劳动强度， 而且可以大大提高原料的利用率和布局速度。因此，目前钣金排套料c a d c a m 软件系统 在工业上有极其广泛的需求。 g a r e y 和j o h n s o n 关于n p 难问题理论的研究表明：在有限合理的时间内，不可能求得 大规模n p 难问题的精确解，问题的求解只能依赖于各种启发式算法。而即使是最简单的 切割排样问题都是n p 难问题，这意味着找不到一种算法可以在有限合理内解决切割排样 问题。而且事实证明：尽管历经近4 0 年的研究，排样问题目前只能以近似求解和启发式 搜索为主要方法求解，而且由于行业的不同，对排样的要求也大不相同，问题的性质与研 究方法就各不相同，因此目前尚没有种通用的解决切割排样问题的方法。另外，当排样 数量巨大时切割排样的方法即使是很小的改进也会导致大量材料的节约。而且，由于现在 计算机硬件的快速发展，目前衡量算法的标准在改变。如以前很重要的时间复杂度，现在 不是很重要，而代之以排样的利用率。有鉴于此，有必要提出一种搜索策略以解决任意图 形的排样问题【4 】。 国防科学技术大学研究生院学位论文 1 4 本文的主要内容 本文研究了钣金切割下料优化排样的一种实用算法一局部贪心法。该方法以排样利 用率为优化目标，以现有矩形、圆、凸多边形的优化排样算法为基础，采用试排一评估一 再试排的循环计算，比一些经典算法中的递归计算具有更高的计算效率。最后在初排结果 中充填群组间的缝隙并利用n f p 作碰撞检测，得到整体优化排样结果。 本文主要研究内容： 1 、零件预处理。 主要内容有不规则封闭图形的逆时针化、闭轮廓的包络多边形和内包含多边形的求 解、平面多边形凸壳算法、不规则多边形凸、凹点的判定、最小包络矩形的求法、封闭轮 廓面积的计算、判定两个轮廓之间的包含关系等。 2 、在充分研究目前各种排样算法的基础上提出一种搜索策略局部贪心法。 算法首先将一些小的样件充填到其他样件的孔洞中形成局部具有高利用率的群组，然 后对群组进行排样得到总体的初步排样结果。具体研究了非凸图形的凸组合方法和扫描线 搜索图形间缝隙的方法。 3 、研究了n f p ( 临界多边形) 的求法及利用n f p 作碰撞检测 首先利用闵可夫斯基和( m i n k o w s k is u m ) 求两个凸多边形的n f p ；然后利用斜度图 求一个凸多边形和非凸多边形的n f p ，并将此方法扩展到不产生干涉的两个非凸多边形； 对于任意形状的多边形，提出了仍然利用斜度图的新方法，该方法比传统方法更简单直观 和容易实现。最后研究了脱离斜度图求n f p 的过程。 4 、设计开发钣金排套料c a d ，c a m 软件排样系统 本软件系统采用v c 阡直接从底层开发，包括了图形输入输出、特征处理、排套处理、 n c 前后置处理四大模块。系统开发过程中着重研究了开发原理并解决了一些关键技术。 在解决二维图形的编辑、钣金切割中的设计计算、优化排样、数控工艺等问题方面取得很 大的成功，在几何与切割特征设计、排套搜索策略方面采用了新的思想和方法，尤其成功 解决了切割引线与切割路径优化的实用问题。目前本软件系统已成功应用于k h c n c 系列 的数控切割机和一些造船企业，用户反馈信息表明：系统在二维设计方面优于s i 掣n a n e s t 可与a u t o c a d 相比，在特征处理、排样处理及数控工艺方面不比s i g m a n e s t 差。 第6 页 国防科学技术大学研究生院学位论文 1 5 本文的体系结构 第一章介绍了排样算法的应用领域、研究背景、现状以及目前存在的问题。针对这些 问题，提出了本文的研究方案和主要内容。第二章主要介绍与排样相关的部分算法。第三 章讲述了n f p 在排样中的应用及两个任意多边形的n f p 求解方法。第一步是将凹多边形 用凸壳代替，第二步是代替的多边形求n f p ，第三步将虚拟边用真正的边还原。本章最后 提出了脱离斜度图的求解n f p 的计算流程论文的第四章讲述了利用现有成熟算法解决任 意多边形零件排套的局部贪心法，着重讲述了总体搜索策略和局部优化。第五章主要讲述 了钣金排套料c a d c a m 软件系统的总体结构和各重要模块的实现方法。第六章是论文的 结果、不足以及今后研究的力一向。 国防科学技术大学研究生院学位论文 第二章不规则轮廓的预处理 【本章摘要】本章对与排样有关的基本算法进行了研究。由于待排零件为手工输入或文件 读取的各种不规则轮廓，混乱无序，为了使得算法统一，且减少不必要的重复运算，在正 式排样前有必要首先对不规则轮廓进行规则化处理和算法准各。本章的主要算法有封闭轮 廓的逆时针化、不规则轮廓的外包络多边形和内包含多边形求解、多边形的面积计算、任 意多边形的凸壳、任意多边形的最小包络矩形、点与轮廓位置关系的判定等。 2 1 封闭图形的逆时针化 当根据给定的方向沿着封闭图形的轮廓行进时会有顺时针和逆时针之别，顺时针的封 闭图形和逆时针的封闭图形在在处理时方法是不一样的。为了统一和减少运算，文中的算 法都是针对逆时针轮廓，所以封闭轮廓的逆时针化有很重要的意义。具体流程为：l 、判 断封闭轮廓的方向，2 、如果是顺时针则将所有轮廓反向排列，否则不变。 如果封闭图形为n 边简单多边形时，设顶点依次为岛，p ，一 p i ，将多边形 的边从起点_ 丌始按轮廓的顺序变为矢量，h ，k ， 巧= 鼻。一只( 如图2 - i 所示) ，按顺序计算每两个相邻矢量形成的角度岛，o ，g ，( c f 为矢量h 一到 矢量k 的夹角，顺时针为负，逆时针为正) 最后求g ，如果g = 2 石，则给定顺序的 多边形顺序为逆时针；如果e = 2 石，则给定顺序的多边形为顺时针。 如果多边形按顺时针排列，则将所有顶点反向排列为逆时针多边形。 图2 1 ( a ) ，每个相邻矢量间的角度和为- - 2 n ，可以看出是逆时针排列。 而图2 一l ( b ) 每个相邻矢量间的角度和为2n ，可以看出是顺时针排列。 国防科学技术大学研究生院学位论文 夕、p o 、| | p ，i p jp 】、7p 5 p l 、一 v 2v 2 图2 - i ( a ) 顺时钟多边形p 。p l p 4图2 - i 逆时针多边形p 。p l p 4 如果在封闭轮廓中含有圆弧或椭圆弧，首先从起点开始，按轮廓的顺序依次处理线段 或圆弧或椭圆弧。如果是线段，将线段转化为矢量。如果是圆弧或椭圆弧，首先在圆弧或 椭圆弧的起点取过该点且与轮廓走向一致的切线方向为矢量v i ，在圆弧或椭圆弧的终点取 过该点且与轮廓走向一致的切线方向为矢量v i + l ，最后将所得到的矢量轮廓的顺序排列v 。 按顺序计算每两个相邻矢量形成的角度c o ，c l ，c i ，( c i 为矢量v i 一，到矢量 v i 的夹角，顺时针为负，逆时针为正) 最后求c ，如果e = 2 万，则给定顺序的多边 形顺序为逆时针；如果c s = _ 2 丌，则给定顺序的多边形为顺时针。 以图2 - 2 为例，图a 中有9 个矢量，按顺序用上面的方法处理，可以得出是逆时针方 向。图b 中则相反。 如果在封闭轮廓中含有其它的光滑曲线，处理方法同上，首先在光滑曲线的起点取过 该点且与轮廓走向一致的切线方向为矢量v i ，在光滑曲线的终点取过该点且与轮廓走向一 致的切线方向为矢量v i + l ，后面的处理方法同上。图2 3 为一个含有样条曲线的逆时针封 闭轮廓。 国防科学技术大学研究生院学位论文 ( a ) 图2 - 2 含有圆弧的封闭轮廓的方向判定 图2 _ 3 含有光滑曲线段的封闭轮廓的方向判定 2 2 闭轮廓的外包络多边形和内包含多边形 任意形状轮廓都是由线段、圆弧、椭圆弧或其它曲线连接而成，在排样过程中，对于 多边形轮廓的算法运算量小，容易实现，而对于圆弧、椭圆弧等曲线轮廓则运算量剧增， 有些甚至无法实现。为了减少运算的时间和复杂性，通常首先用简单多边形轮廓替代真正 的排样轮廓参与排样，排样完成后再用真正的排样件替换简单多边形。在处理得当的情况 下，排样结果没有太大的影响。通常替换不规则轮廓的方法是用数个线段去逼近轮廓中的 曲线段，这种方法实现简单，但有可能会在排样件很紧密时出现重叠的情况，见图2 - 4 。 图a 中用多边形拟和圆弧，图b 排样过程中拟和的多边形并未重叠，但真正的排样件之问 重叠了( 图b ) 。这样的后果是出现大量废品，为了避免这种情况出现，本文对于所有的外 轮廓用外包络多边形去替代，内轮廓则用内包含多边形替代。因为任何时候替换的多边形 都是原始排样件的子集，只要替换的多边形之间不重叠，即可保证换成排样件后亦不重叠。 国防科学技术大学研究生院学位论文 ( a ) ( b ) 排样件原始轮廓 重叠部分 图2 - 4 排样件出现重叠 求包络多边形的步骤如下： 1 ) 所有封闭轮廓逆时针化 2 ) 按顺序依次处理每个轮廓段，如果是线段，则不改变。 3 ) 如果是逆时针的圆弧段，用其外切多边形代替，圆弧的起点和终点分别为2 个外 切点，见图2 5 ( a ) 。如果是顺时针的圆弧段，用其那接多边形代替，圆弧的起点和 终点分别为2 个内接点，见图2 5 ( b ) 。 图2 5 不规则轮廓的外包络多边形 求内包含多边形的步骤如下： 1 ) 所有封闭轮廓为逆时针化 2 1 按顺序依次处理每个轮廓段，如果是线段，则不改变。 3 ) 如果是逆时钟的圆弧段，用其内接多边形代替，圆弧的起点和终点分别为2 个内 接点。见图2 - 6 ( a ) 。如果是顺时针的圆弧段，用其外切多边形代替，圆弧的起点和 终点分别为2 个外切点。见图2 - 6 ( b ) 。 垦堕型兰垫查查兰堕茎竺堕兰垡笙苎 ( b 图2 - 6 不规则轮廓的内包含多边形 2 3 平面多边形凸壳算法 点集q 的凸包( c o n v e xb u l l ) 是指一个最小的凸多边形，满足o 中的点或者在多边形边 上或者在多边形内。形象的表示就是用一根橡皮圈套住o 中的所有点，当橡皮圈收缩到最 小时形成的图形就是点集q 的凸壳( 图2 7 ) 。多边形的凸壳就是一个包住该多边形的最小 凸多边形，或者是该多边形的所有顶点组成的点集的凸壳。显然凸多边形的凸壳就是它本 身。 图2 7 点集的凸壳 凸壳的生成本文采用g r a h a m 算法，从所需时间上来讲该算法是求解平面点集凸壳问 题的最佳算法，算法的时间复杂度为o ( n l o g n ) 。 g r a h a m 算法的具体步骤如下： 1 1 将多边形的各个顶点重新排序，将y 坐标最小的点设为p o ，把p o 同其它点用线段 相连，按线段与x 正坐标的夹角由小到大重新排序( 如果有多个点有相同的极角， 国防科学技术大学研究生院学位论文 除了距p o 最远的点外全部移除) ，得到一序列p o ，p 1 ，p n 。 依次连接这些点 则得到一多边形。p o 是凸壳边界的起点，p l 和p i i 也必是凸壳上的点。注意：排序 时不需要求每个线段与x 正坐标的真正夹角，只要比较线段之间的相互关系。比 较时将线段作为矢量，矢量之间作点积即可。 2 ) 删去不是凸壳顶点的点，具体过程如下： b e g i n 压p 0 进栈s 压p l 进栈s 压p 2 进栈s f o r i 一3t o n d ow h i l e 由s 的栈顶元素的下一个元素、s 的栈顶元素以及p i 构成的折线段不拐 向左侧 对s 弹栈 压p i 进栈s r e t u r ns e n d 3 ) 此过程执行后，栈s 由底至顶的元素就是q 的凸包顶点按逆时针排列的点序列。 6 5 ，j ： 二三一一 三 、 0 d 、 4 0 图2 - 8 g r a h a m 应用实例 ( a ) 初始的多边形 ( b ) 根据各点的倾角大小排列( 其中有两个点倾角相同，距p o 近的一个点已被舍去) ( c ) 各点按顺序连成一多边彤 ( d ) i = 3 ，p ，p 4 相对p 2 p 3 拐向左侧，顶点p 3 保留；商+ 1 ，p 4 p 5 相对，3 p 4 拐向右侧，删掉p 4 后面的点依次前移一个，# i 1 。 ( e ) i = 3 ，p 3 p 4 相对p 2 p 3 拐向右侧，删掉p 3 ，后面的点依次前移一个，重复上面的过程。 ( d 得到凸壳的顶点。 2 4 任意多边形凸、凹顶点的确定 假设封闭图形为n 边简单多边形，且为逆多边形，其顶点依次为p d ，p ，一竹， 顶点只的坐标为p i j ，f ) ，将多边形的边从起点开始按轮廓的顺序变为矢量，巧， ，= 瓦虿。显然，如果k 折向巧一左侧，则p i 为凸点，如图2 9 ( a ) 所示；反 呷， 。、k 一 、弋 一 国防科学技术大学研究生院学位论文 之，如果折向巧一，右侧，则p i 为凹点，如图2 9 ( b ) 所示。 ( b ) r v 。折向v 左侧p i 为凸点v 。折向v 。i 右侧，p i 为凹点 图2 - 9 多边形凹、凸点判定 根据矢量叉积的公式，如果k + 。k 0 ，则巧折向一。左侧；如果k 一。l o 时，b 为凸点；反之p i 为凹点，亦即当 g ，一一一，) 。一儿) 一g 。一薯) 一y , - 1 ) 0 时，p t 为凸点，反之只为凹点；当 g ，一x i - i ) o 。一y i ) 一0 。一t ) ( y 。一 一。) = o 时，说明p ，冗余，可以剔除。 国防科学技术大学研究生院学位论文 2 5 最小包络矩形的求法 所谓多边形的包络矩形是指完全包含了多边形上所有的点，且其各边均与多边形相接 触的矩形。凸多边形最简单的一种包络矩形求法就是求出其横、纵坐标最大与最小值共四 个点，然后将其相连；对于凹多边形的包络矩形可以首先求出其凸壳，然后依据凸多边形 求包络矩形的方法而得到的。如图2 1 0 。 图2 一l o 凸多边形和非凸多边形的包络矩形 所谓最小包络矩形，就是所有的包络矩形中面积最小的一个。 如果将一个多边形置于一直角坐标系中，可以证明，只有使多边形的两凸顶点之间的 边或连线平行于坐标轴时才能产生最佳的矩形包络。本文的算法即基于此。 步骤如下： 1 ) 求出多边形凸壳，作为新的凸多边形。 2 ) 求出新凸多边形每条边与坐标轴所成的角。 3 ) 以凸多边形每条边为基准，对应角为旋转角对其进行旋转，得到新的凸多边形。 4 1 求出新凸多边形的包络矩形，并求出包络矩形的面积。 5 ) 求出所有包络矩形的面积，其中面积最小的即为所求的包络矩形。 图2 1 l 为一个实例，图中深色多边形为要求最小包络矩形的多边形，浅色线段为多边形凸 壳的边。 国防科学技术大学研究生院学位论文 匾圆 ( 2 ) 图2 - 11 求多边形的最小包络矩形 2 6 封闭轮廓面积的计算 ( 6 ) 在求排样利用率时必须知道排样件的面积，而且许多排样算法在确定零件的排样顺序 时根据的是零件面积大小，因此最终都归结为任意多边形面积的计算。 一般计算一个有n 个顶点的多边形的面积的算法都是从一个顶点往其它顶点间连线， 将多边形分割成n 一2 个三角形，计算所有三角形的面积再叠加。这种算法原理简单，但 运算量大，且编程实现时难度大。本文采取封闭轮廓积分求面积的思想，结合边矢量的概 念，容易编程实现。 以图2 - 1 2 ( a ) 的凸多边形为例，多边形的边为逆时针排列。可以看出，所有与x 轴正方 向夹角小于9 0 。的边矢量与x 轴形成的面积之和( 图中为区域) 减去所有与x 轴正方 向夹角大于9 0 。的边矢量与x 轴形成的面积之和( 图中为区域) 即为多边形的面积。如 果多边形非凸，如图2 1 2 ( b ) ，则沿着y 方向将多边形分解为凸多边形，此算法同样适用。 事实上，采用下面的计算公式，如果边矢量与x 轴正方向夹角小于9 0 。，则算出来的面积 是正的，否则是负的。例子见图2 - 1 2 ( c ) 、图2 - 1 2 ( d ) 。 设某条边顶点为b + j l + ，+ 小p f j ) ，则边与x 轴形成的面积& 为 s ，= 一，+ 。+ y 。) g 。一x ，) 国防科学技术大学研究生院学位论文 多边形的面积s 为 s = s ， 具体步骤如下： 1 ) 所有边逆时针排列 2 ) 求每条边与x 轴形成的面积 3 ) 所有面积相加 y ( d ) 图2 1 2 求多边形的面积 2 7 判断点和轮廓的包含关系 判断点与轮廓的包含关系的基本原理是：从点p 水平方向作射线l ，确定l 与轮廓q 的交点数n 。首先判断点是构在轮廓上，不在，则如果n 为奇数，p 在q 内，反之p 在轮 廓外。图2 1 3 直观地表示了该原理。 详细求解流程见图2 1 4 。 国防科学技术大学研究生院学位论文 图2 1 3 轮廓与点的包含关系的判定 图2 1 4 求a 与轮廓q 的包含关系 其中计算射线与轮廓b 每个实体的交点个数是关键，容易产生奇异的是下面四种情况： 1 射线和轮廓相切( 如图2 1 5 中的a 处) 。 2 射线和轮廓相交的地方正好在诱实体( 线段或圆弧) 的连接处( 如图2 1 5 中的b 处) 。 国防科学技术大学研究生院学位论文 3 点正好在轮廓的某线段延长线上( 如2 - 1 5 中的c 处) 。 4 点与两个线段的连接处相交，且两线段在射线l 的同侧( 如2 1 5 中的d 处) 。 为解决这几种情况我们约定：如果l 和实体相切，则交点数为0 ；如果实体在 起点或终点处和l 相交，则将p 点纵坐标减小一个非常小的值( 例如o 0 0 0 0 1 ) 再 作射线和实体求交点。采用上面约定后，图2 1 5 中p 1 、p 2 、p 3 、p 4 和轮廓的交点 个数分别为0 、l 、2 、0 ，与实际情况相符。 图2 1 5 射线与轮廓相交容易出现奇异的情况 2 8 判断两个轮廓的包含关系 判断两个轮廓的包含关系，核心是判断点与轮廓的包含关系。根据机械零件的几何结 构特征，若轮廓a 上有一个点被轮廓b 包含，则轮廓a 全部被轮廓b 包含。关于点与轮 廓的包含关系，上节有详细的算法介绍。 需要注意的是；上述方法在一些边界点( 局部极值点) 可能发生歧义。特别是点与轮 廓的边界很接近时，会发生误判，如图2 1 6 的例子：图中a 点和b 点与轮廓c 的边界非 常接近，由于点的坐标是浮点数，在求点与边界的交点个数时极有可能出现错误，从而使 轮廓a 和轮廓c ，轮廓b 和轮廓c 的包含关系出 国防科学技术大学研究生院学位论文 图2 1 6 可能会发生误判的情形 因此需要视情采用以下方法处理： 1 不取起点、终点、顶点等边界点，取实体段的中点。 2 比较多个点与轮廓的包含关系。用方法1 从一个轮廓上( 假设a ) 取得数个点， 将这些点逐个与要判断的轮廓( 假设b ) 比较，看轮廓内的点多还是轮廓外的点 多，如果轮廓内点多于轮廓外，则b 包含a ，否则a 包含b 。这样即使个别点发 生了误判，亦不会影响整个轮廓。 国防科学技术大学研究生院学位论文 第三章n f p 的应用与求解 【本章摘要】n f p ( n of i tp o l y g o n ，某些文献译为临界多边形) 是数学中的重要概念，其 意义是与多边形接触但是没有重叠的邻接多边形。n f p 在工业中应用广泛，主要用t ：干涉 和碰撞检测。在本章的排样算法中，主体排样后的局部优化利用了n f p 作碰撞检测。但 由于任意非凸多边形的n f p 的传统解法很繁琐，因此影响了n f p 的应用f 7 “。本章研究了 一种基于斜度图的n f p 求法，可以解决任意非凸多边形的求解，并最终给出了脱离斜度 图的程序设计的流程。 3 1n f p 定义 多边形b 相对于多边形a 的n f p ( 记做n f p a b ) 是这样定义的：多边形a 固定，多 边形b 绕着a 运动一圈，任何时候必须满足b 与a 接触但不重叠，且a 和b 均不能旋转， 在这个过程中，b 上的任一点( 称为参考点) 形成的轨迹就是n f p