【作者】 何妍；

【导师】 黎自强；

【作者基本信息】 湘潭大学 ， 计算机科学与技术， 2011， 硕士

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

【Abstract】 The layout problem of 2-D irregular objects, for example, drawing mark-lines in clothing cutting, parts assembly for the plate cutting in the shipbuilding industry, stamping and blanking in the machine industry, belongs to NP-hard problem. It is difficulty to solution. So, some scholars have done a lot of research for it. In the all algorithms, evolutionary algorithms (for example, genetic algorithm, particle swarm optimization) are a kind of effective algorithm. When using evolutionary algorithms to solve the layout problems of irregular polygons, the sum of overlapping area between objects and between objects and container is computed at each iterative for evolutionary layout and is used to evaluate perfermane of population individual. The time of computing overlapping area is 50-500 times of sum of other cost time. So it becomes the bottleneck that restricts improvement of solution efficiency and accuracy of evolutionary layout algorithm. Therefore, in this paper mainly, author discusses problems of convex decomposition and clipping, and on basis of them studies on problem of overlapping area calculation between 2-D irregular polygons for its evolutionary layout, furthermore presents a high efficiency algorithm for computing irregular polygon overlapping area in order to improve solution efficiency and accura- cy of evolutionary layout of irregular polygons.The main contents in the paper are as follows.Firstly, an irregular polygon convex decomposition method with Steiner point (IPSPCD) is proposed. It is the premise for improving efficiency of overlapping area computation between irregular polygons. The adjacent reflex vertex of an irregular polygon can deal with 4 cases by clockwise in our IPSPCD. Then according to differ- ent situations, we decompose the irregular polygon convex until the all reflex vertices deal with. The algorithm complexity analysis and the experimental results show that the IPSPCD can product the minimum number of convex polygons and improve com- position efficiency of irregular polygons compared with existing algorithms.Secondly, a fast clip method is put forward in this paper. It is a key step for improving efficiency of overlapping area computation between irregular polygons. The clip method in this paper is on basis of internal vertex judgment and fast intersec- tion test and intersection compute between a line segment and any convex broken line segment. The algorithm complexity analysis and the experimental results clear that the method in this paper reduces the computational complexity compared with the existing algorithms.Thirdly, this paper presents an algorithm for computing irregular polygon over- lapping area(CIPOA algorithm). At first, two irregular polygons are respectively decomposed into the minimum number of convex polygons; afterwards, each pair of the overlapping convex polygons from two resulting partitions is clipped and their overlapping area is calculated. The time complexity analysis and numerical experi- ments indicate that the calculation efficiency of our CIPOA algorithm outperforms the existing algorithms, and the less two irregular polygons overlap, the more obvious computation efficiency of our CIPOA algorithm improves.The paper studies overlapping area computation between 2-D objects for its evolutionary layout and two associated problems based on the nesting problem as the study background. That is convex decomposition and clipping of irregular polygons, which support the performance of evolutionary algorithm for the irregular polygon layout. In addition, author hope the above approaches will be spread and applied to some other problems.更多还原