Study On Overlapping Area Computation Between 2-D Objects For Its Evolutionary Layout

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.