Skip to content

This repository contains the code to solve rectilinear packing problem

License

Notifications You must be signed in to change notification settings

Mrlution/RectilinearPackingProblemSolver

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

38 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Rectilinear Packing Problem Solver

Packing and layout problems are common in both engineering and non-engineering applications. In the Very Large Scale Integrated Circuit design, we often pack different IP Cores into a rectangular container. Usually, the IP Core is a rectilinear shape. To cut down the cost, we need to minimize the container. So the EDA software needs a fast and robust and high performance algorithm to solve the packing problem. Apart from EDA Software, many other industrial applications such as cloth cutting and newspaper layout are involved with this algorithm.

The term rectilinear means the interior angles of the packed blocks are either 90 degrees or 270 degrees. The container is usually a rectangle with a fixed width and unrestricted height. The algorithm will pack all the polygonal blocks into the container without overlapping, and generate a height as small as possible.

Requirements

mpi4py==3.0.3 Before you install mpi4py, you need to install a mpi software such as OpenMpi or Microsoft MPI.

pyclipper==1.2.0

Polygon3==3.0.8 When you install Polygon3, you must begin with a capital "P"

How to run

python main.py -d data_file.txt

look at data/polygon_area_etc_input_id.txt for data format

Result

This is an packing example. For our dataset, the average occupation rate is 85%.

How this work

NFP

Outter NFP is used to avoid overlap between objects. Inner NFP is used to ensure the objects in the bin.

Below left stratage

All Object is packed at the below left position.

Complex and big first stratage

Parallel computation

The computation of NFPs can be parallelized, we use MPI as the parallel computation tool.

More about this project

the "doc" folder contains docx and pptx files, they described this software in detail.

About

This repository contains the code to solve rectilinear packing problem

Topics

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages