An Algorithm for Matching Two Simple Polygons with Free Rotation

In order to solve the matching problem in two-dimensional irregular packing problem, an algorithm for matching two simple polygons without holes under the condition of free rotation is proposed. Based on the assumption that the two polygons can rotate freely, the algorithm chooses the appropriate matching method for the case of concave or convex NFP of the two polygons, and finds out a matching scheme that makes the space of the matched polygons as small as possible and ensures the overall rectangular regularity of the matched polygons as high as possible. Utilization ratio and rectangular regularity of the whole matched object are used to measure the matching effect. Some representative polygon samples in ESICUP are selected to compare with several algorithms. Under the requirement of arbitrary rotation accuracy, the algorithm is fast, which makes it suitable for practical problems such as packing problem.