Optimal Marking of Garment Patterns using Rectilinear Polygon Approximation

Pattern marking is the allocation of garment patterns on the cloth roll minimizing the fabric loss, and thus very important for the cost reduction in garment manufacturing industries. But automatic marking is very difficult because it is a non-deterministic in polynomial time problem. Most previous pattern marking methods needed collision detection routine to lay out patterns without interfering each other, which was the bottle neck of nesting speed. In this study, rectilinear polygon approximation technique was used to reduce the overall calculation time because the garment patterns are usually in non-convex shape that can effectively be approximated by rectangles. Additionally, we adapted stochastic simulated annealing to search the optimal pattern marking