Improved Sliding Algorithm for Generating No-Fit Polygon in the 2D Irregular Packing Problem
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 t...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-08-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/10/16/2941 |
| _version_ | 1797431984678502400 |
|---|---|
| author | Qiang Luo Yunqing Rao |
| author_facet | Qiang Luo Yunqing Rao |
| author_sort | Qiang Luo |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T09:53:15Z |
| format | Article |
| id | doaj.art-cbdcf054956f40c1a8ca834d43c341b9 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-09T09:53:15Z |
| publishDate | 2022-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-cbdcf054956f40c1a8ca834d43c341b92023-12-01T23:57:42ZengMDPI AGMathematics2227-73902022-08-011016294110.3390/math10162941Improved Sliding Algorithm for Generating No-Fit Polygon in the 2D Irregular Packing ProblemQiang Luo0Yunqing Rao1School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, ChinaSchool of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, ChinaThis 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.https://www.mdpi.com/2227-7390/10/16/2941no-fit polygonirregular packing problemsliding algorithmcuttingconfiguration space obstacle |
| spellingShingle | Qiang Luo Yunqing Rao Improved Sliding Algorithm for Generating No-Fit Polygon in the 2D Irregular Packing Problem Mathematics no-fit polygon irregular packing problem sliding algorithm cutting configuration space obstacle |
| title | Improved Sliding Algorithm for Generating No-Fit Polygon in the 2D Irregular Packing Problem |
| title_full | Improved Sliding Algorithm for Generating No-Fit Polygon in the 2D Irregular Packing Problem |
| title_fullStr | Improved Sliding Algorithm for Generating No-Fit Polygon in the 2D Irregular Packing Problem |
| title_full_unstemmed | Improved Sliding Algorithm for Generating No-Fit Polygon in the 2D Irregular Packing Problem |
| title_short | Improved Sliding Algorithm for Generating No-Fit Polygon in the 2D Irregular Packing Problem |
| title_sort | improved sliding algorithm for generating no fit polygon in the 2d irregular packing problem |
| topic | no-fit polygon irregular packing problem sliding algorithm cutting configuration space obstacle |
| url | https://www.mdpi.com/2227-7390/10/16/2941 |
| work_keys_str_mv | AT qiangluo improvedslidingalgorithmforgeneratingnofitpolygoninthe2dirregularpackingproblem AT yunqingrao improvedslidingalgorithmforgeneratingnofitpolygoninthe2dirregularpackingproblem |