服装裁剪中的画印布局,造船业板材切割中的部件拼装和机械行业中的冲压落料等二维不规则图形布局问题都属于NP-难问题,存在求解困难。为此,许多学者进行了大量的研究。其中,演化算法(例如,遗传算法、模拟退火算法、粒子群算法)是有效的算法。大多数演化算法求解不规则图形的布局问题时,其迭代过程中,都需要计算待布物之间、待布物与容器之间的干涉量,将它作为适应度函数的一部分,用以评估种群个体的优劣。由于其干涉量计算的时间是其它耗时的总和的50-500倍。因此,它成为演化布局算法求解效率和精度提高的瓶颈问题。为此,本文主要研究2-D不规则多边形的布局演化求解中的干涉量计算问题,提出基于凸多边形分解和裁剪的高效不规则多边形交叠面积计算方法,进而提高不规则多边形演化布局求解的效率和精度。希望所提出的方法能用于其它相关的问题。本文主要工作如下:1.本文提出了一种使用辅助点的不规则多边形凸剖分算法(IPSPCD)。它是提高不规则多边形交叠面积计算效率的前提。文中剖分算法是按顺时针方向依次将不规则多边形中相邻凹顶点分成4种情形,然后根据不同情形分解出一个凸多边形,直至所有凹顶点全部被剖分。算法复杂度分析与数值实验表明:与已存在的算法相比,本文算法剖分的凸多边形个数较少,计算效率较高。2.本文提出一种快速不规则多边形裁剪算法(FCPC)。它是提高不规则多边形交叠面积计算效率的关键。文中裁剪方法是基于其内顶点的判断和线段与凸折线段之间的快速相交判断与求交得到交叠多边形顶点。由算法复杂度分析可知:本文裁剪算法较已有的裁剪算法具有较低的计算复杂度。3.本文提出一种求解不规则多边形干涉量算法(CIPOA)。它首先分解不规则多边形为数目较少的凸多边形集,然后分别在两集合之间进行快速裁剪求交,并计算交叠多边形面积。算法复杂度分析和数值实验表明:与已存在的算法相比,CIPOA算法提高了不规则多边形之间的交叠面积的计算效率。本文以2-D不规则多边形布局问题的演化求解为背景,研究了不规则多边形交叠面积干涉计算,以及与之相关的两个问题:不规则多边形的凸剖分和裁剪,为不规则多边形布局问题的演化求解提供支撑。同时,也希望本文中的算法能够应用于其它相关问题。