Research And Implement Of Minkowski Sum-based Algorithm For Nesting

Two-dimensional irregular shape nesting problem exists in various field in mechanical manufacturing such as plane, motor, ship etc. Traditional layout proceedings, from product design, unfolding to nesting, are finished by experienced technician through manual trial allocation follow their experience, intuition, and imagination. Although it could take out some success, its'cycle elongated and manpower exhausted as the shape became complicated, and it's difficult to gain the optimization solution. As the increasingly mature of CAD technology, it become important and necessary to use computer based optimal auto-nesting.Based on comprehensively investigation and study, combined with current research status and characteristic of nesting problem, this thesis made a profound research in the nesting algorithms. Specifically, the research contained:A suit of data structures, named as bidirectional connected edge list, for the two-dimensional polygon representation and related algorithms are designed and implemented. This data structure can support the action such as delete, add node. It was tuned to support highly efficient query and iterative operation which was needed in a optimization algorithm.A algorithm for the Minkowski Sum of concave polygons was put forward. However, it's difficult to take out the Minkowski Sum of two concave polygons directly. In this thesis, The author simplified this problem into the instance that calculating the Minkowski Sum of two triangle by decomposing the concave polygon into triangles.A optimization algorithm based on Minkowski Sum is provided, the algorithm combines a polygon C at the various position of the outface which the Minkowski Sum of the two polygons, then take out the Minkowski Sum between C and–C (-C is symmetrical to C at the origin point), gain the optimization solution, repeat the above steps until approach the global optimization.Based on the above research, the author carried out an optimized nesting system which based on Minkowski Sum by using the C++.