Low efficiency of interference calculation hasbecome the bottleneck that restricts further development ofthe performance of evolutionary algorithm for the polygonlayout. To solve the problem, in this paper, we propose analgorithm of calculating overlapping area between twoirregular polygons. For this algorithm, at first, two irregularpolygons are respectively decomposed into the minimumnumber of convex polygons; afterwards, each pair of theoverlapping convex polygons from two resulting partitionsis clipped and their overlapping area is calculated. Becausethrough a fast non-overlapping test to all pairs of convexpolygons to be clipped, invalid computation is decreased; bymaking use of simple internal vertex judgment and sheartransformationbased on intersecting test and intersectioncalculation between a line segment and any convex brokenline segment, its speed of clipping overlapping convexpolygons is improved. The time complexity analysis andnumerical experiments indicate that the performance of ourpresented algorithm superiors to the existing algorithms.
展开▼
