2D Packing Application
Constrained graph search-based polygon packing application
School | Keio University |
---|---|
Release | 2015 |
Type | App |
Programming language | Python |
Libraries | Tkinter, numpy, Shapely, matplotlib, generateDS |
Ai fields | Graph search, Constrained search, 2D geometry, Collision detection |
Working period | Nov 2014 - August 2015 |
Role | Algorithm design, Programming |
Description
This packing application places a set of 2D polygonal shapes into a rectangular container which is made as small as possible for a given computation time.
- Input: a set of polygonal pieces (wooden puzzle, game sprite bounding polygons, cloth patterns)
- Output: a list of translations and rotations for each piece + the size of the final rectangular container, where the container size has been minimized
- Real-world application: testing puzzle solutions, sprite packing in games, cutting patterns in cloth
Screenshots


Context
This program was developed as part of my research on Irregular Packing for my Master of Science in Artificial Intelligence at Keio University, Hagiwara Laboratory.
You can download the associated Master Thesis here.
Acknowledgements
- NestingXML data set on the ESICUP website for various set of pieces in XML to use in benchmarks