Similar articles

Abstract: Given a set of triangles and a rectangle container, the triangle packing problem is to determine if these triangles can be placed into the container without overlapping. triangle packing problem is a special case of polygon packing problem and also NP-hard, so it is unlikely that an efficient and exact algorithm can be developed to solve this problem. In this paper, a new concept of rigid placement is proposed, based on which a discrete solution space called rigid solution space is constructed. Each solution in the rigid solution space can be built by continuously applying legal rigid placements one by one until all the triangles are placed into the rectangle container without overlapping. The proposed Least-destruction-First (LDF) strategy determines which rigid placement has the privilege to go into the rectangle container. Based on this, a heuristic algorithm is proposed to solve the problem. Combining Least-destruction-First strategy with backtracking, the corresponding backtracking algorithm is proposed. Computational results show that our proposed algorithms are efficient and robust. With slight modification, these techniques can be conveniently used for solving polygon packing problem.

[1] Dowsland, K.A., Dowsland, W.B., 1992. Packing problems. European Journal of Operational Research, 56(1):2-14.

[2] Garey, M.R., Johnson, D.S., 1979. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York.

[3] Li, Z., Milenkovic, V.J., 1995. Compaction and separation algorithms for non-convex polygons and their applications. European Journal of Operational Research, 84:539-561.

[4] Liang, K.H., Yao, X., Newton, C., Hoffman, D., 2002. A new evolutionary approach to cutting stock problems with and without contiguity. Computers and Operations Research, 29(12):1641-1659.

[5] Lipnitskii, A.A., 2002. Use of genetic algorithms for solution of the rectangle packing problem. Cybernetics and Systems Analysis, 38(6):943-946.

[6] Milenkovic, V.J., Daniels, K.M., 1996. Translational Polygon Containment and Minimal Enclosure Using Mathematical Programming. Proceedings of the Annual ACM Symposium on Theory of Computing, p.109-118.

[7] Milenkovic, V.J., Daniels, K.M., Li, Z., 1991. Automatic Marker Making. Proceedings of the Third Canadian Conference on Computational Geometry, p.243-246.

[8] Osogami, T., Okano, H., 2003. Local search algorithms for the bin packing problem and their relationships to various construction heuristics. Journal of Heuristics, 9(1):29-49.

[9] Wang, H.Q., 2002. An improved algorithm for the packing of unequal circles within a larger containing circle. European Journal of Operational Research, 141(2):440-453.