Strip Packing

Algorithm for the strip packing problem with guillotine cuts constraint
Alternatives To Strip Packing
Project NameStarsDownloadsRepos Using ThisPackages Using ThisMost Recent CommitTotal ReleasesLatest ReleaseOpen IssuesLicenseLanguage
Algorithms Sedgewick Wayne1,967
2 months ago3mitJava
Solutions to all the exercises of the Algorithms book by Robert Sedgewick and Kevin Wayne
Mir Algorithm168102915 days ago610February 07, 202327otherD
Dlang Core Library
5 months agoapache-2.0C++
Floating point printing and parsing library based on Grisu2 and Krosh algorithms
Strip Packing14
4 years ago1mitPython
Algorithm for the strip packing problem with guillotine cuts constraint
2 months ago2bsd-2-clauseRuby
This class implements a pretty printing algorithm.
5 years agomitGo
Implementation of Kiselyov et al's pretty printing algorithm in Go.
a year ago3mitC++
A collection of templates/algorithms for competitive coding.
7 years agoJavaScript
Binary tree bin packing algorithm for packing pictures to sheet for printing
Diff Java2
7 years agogpl-3.0Java
Clone and improvements
Soren Cslab Scripts2
7 years agomitShell
Scripts for fixing firefox locks, printing, timing algorithms, and checking your quota.
Alternatives To Strip Packing
Select To Compare

Alternative Project Comparisons

About Strip-Packing

This repository contains implementations for the strip packing problem.

The strip packing problem optimizes the placing of rectangles in a strip of fixed width and variable length, such that the overall length of the strip is minimised.

Currently the 'Priority Heuristic' algorithm is implemented for the variant in which rotations are allowed and cuts have to follow the guillotine constraint. This is implemented in the phspprg method. More information about parameters and return values can be found in the docstrings in the source.

note: This algorithm is heuristic which means that the outcome is possibly not the most optimal.

This algorithms is based on the following paper: A priority heuristic for the guillotine rectangular packing problem

  title={A priority heuristic for the guillotine rectangular packing problem},
  author={Zhang, Defu and Shi, Leyuan and Leung, Stephen CH and Wu, Tao},
  journal={Information Processing Letters},

The results can be visualized with the visualize method, matplotlib needs to be installed for this.

Example demonstrates an example, including visualization:

    boxes = [
        [5, 3], [5, 3], [2, 4], [30, 8], [10, 20],
        [20, 10], [5, 5], [5, 5], [10, 10], [10, 5],
        [6, 4], [1, 10], [8, 4], [6, 6], [20, 14]
    width = 10
    height, rectangles = phspprg(width, boxes)
    visualize(width, height, rectangles)
    print("The height is: {}".format(height))

The output of the visualization is:

Output of example


It is important to realize that the algorithm is an heuristic and will not always find the optimal result.

The authors of the algorithm sort the rectangles internally by width, this is the most optimal for a lot of cases but not always. Sometimes it can be much better to sort by height. This can be changed by setting the parameter sorting='height'. The next outputs are an example how sorting can influence the result:

width Example when sorting by width vs height Example when sorting by height

And it can also happen that none of the two sorting options result in THE optimal solution.

Know the difference between heuristic and optimal when using this algorithm.

Popular Algorithms Projects
Popular Printing Projects
Popular Computer Science Categories
Related Searches

Get A Weekly Email With Trending Projects For These Categories
No Spam. Unsubscribe easily at any time.