Improved Sliding Algorithm for Generating No-Fit Polygon in the 2D Irregular Packing Problem

Qiang Luo and Yunqing Rao ()
Additional contact information
Qiang Luo: School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China
Yunqing Rao: School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China

Mathematics, 2022, vol. 10, issue 16, 1-18

Abstract: This paper introduces an efficient and robust sliding algorithm for the creation of no-fit polygons. The improved algorithm can cope with complex cases and is given an implementation in detail. The proposed concept of a touching group can simplify the judging process when recognizing the potential translation vector for an orbital polygon. In addition, the generation of the no-fit polygon only involves three main steps based on the proposed concept. The proposed algorithm has a mechanism that searches other start positions to generate a complete no-fit polygon for handling complex cases. To improve the efficiency, many acceleration strategies have been proposed, such as point exclusion strategy and point inclusion test. The robust and efficient performance of the algorithm is tested by well-known benchmark instances and degenerate and complex cases, such as holes, interlocking concavities and jigsaw-type pieces. Experimental results show that the proposed algorithm can produce complete no-fit polygons for complex cases, and acceleration strategies can reduce the creation time of no-fit polygon on benchmark instances by more than sixteen percent on average.

Keywords: no-fit polygon; irregular packing problem; sliding algorithm; cutting; configuration space obstacle (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/16/2941/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/16/2941/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:16:p:2941-:d:888741

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().