2D Packing Application

Constrained graph search-based polygon packing application

Packing app - Result Shirts

Genrewd
Year2015
Target audienceResearchers
LanguagePython 2
LibrariesShapely, generateDS, Tkinter, matplotlib
AI fieldsGraph search, Constrained search, 2D geometry, Collision detection
Production time2 years
RoleAlgorithm 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, cloth patterns, metal, etc.)
  • 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: sprite packing in games, cutting patterns in cloth, etc.

Screenshots

Packing app - App windowPacking app - Plot domain

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.

Acknowledgements

  • NestingXML data set on the ESICUP website for various set of pieces in XML to use in benchmarks