排样问题,又称为下料填充、零件布局优化问题。即在规定母版区域内,在保证零件轮廓不重叠的前提下,尽可能多地排布零件。二维不规则排样应用最为广泛。但是,由于排样轮廓的描述不具有旋转几何不变性,需要通过对轮廓进行旋转调整或者转化才能确定最终的排样姿态。而通过旋转确定排样姿态很容易错过最佳的排样姿态,影响排样质量。针对上述问题,本文借鉴曲线几何不变参数化表达的思想,提出基于轮廓几何不变描述和编码匹配策略的二维不规则排样算法。算法首先通过编码的形式实现排样轮廓的几何不变描述;然后通过相似特征匹配的方式确定排样姿态和位置。论文主要内容如下:(1)轮廓几何不变描述实现。分析排样轮廓的经典表达方法,通过图形预处理将链码描述符应用到排样轮廓的描述中;结合曲线几何不变表达理论,推导排样轮廓几何描述形式,实现排样轮廓旋转几何不变表达。(2)轮廓形状特征信息提取。在获得轮廓的几何不变性描述后,对轮廓进行编码,获取具有几何描述不变性的编码信息用以表示轮廓的形状特征。(3)轮廓相似特征匹配靠接及轮廓定位。针对排样轮廓相似匹配问题,提出基于最长公共子串的相似匹配算法。该算法首先采用最长公共子串匹配方法搜索两个待排样轮廓的相似特征,以相似特征引导轮廓的靠接及定位。针对母版边界对排样轮廓定位限制的问题,提出基于中心辐射思想的排样定位策略。为验证算法的有效性,选取若干自由曲面的投影轮廓图形对上述排样算法进行了验证,结果表明提出的算法可以大幅度提高排样填充率和排样效率;(4)基于最长公共子序列相似匹配的不规则排样算法。针对最长公共子串匹配的缺点,在轮廓信息提取、相似特征度量及匹配和靠接方法上进行改进。首先,在差分链码的基础上重新提取夹角序列作为轮廓的形状描述,加快匹配速度;其次,基于动态规划算法求解待匹配轮廓的最长公共子序列确定相似特征;最后则是以判距—靠接算法引导轮廓完成互不干涉的图形靠接及定位。结果显示,经改进,本文方法在有效识别利用轮廓特征信息的基础上,可进一步提升排样填充率和排样效率。