Algorithm for the strip packing problem with guillotine cuts constraint

Project Name | Stars | Downloads | Repos Using This | Packages Using This | Most Recent Commit | Total Releases | Latest Release | Open Issues | License | Language |
---|---|---|---|---|---|---|---|---|---|---|

Algorithms Sedgewick Wayne | 1,967 | 2 months ago | 3 | mit | Java | |||||

Solutions to all the exercises of the Algorithms book by Robert Sedgewick and Kevin Wayne | ||||||||||

Mir Algorithm | 168 | 10 | 29 | 15 days ago | 610 | February 07, 2023 | 27 | other | D | |

Dlang Core Library | ||||||||||

Floaxie | 28 | 5 months ago | apache-2.0 | C++ | ||||||

Floating point printing and parsing library based on Grisu2 and Krosh algorithms | ||||||||||

Strip Packing | 14 | 4 years ago | 1 | mit | Python | |||||

Algorithm for the strip packing problem with guillotine cuts constraint | ||||||||||

Prettyprint | 8 | 2 months ago | 2 | bsd-2-clause | Ruby | |||||

This class implements a pretty printing algorithm. | ||||||||||

Gopprint | 5 | 5 years ago | mit | Go | ||||||

Implementation of Kiselyov et al's pretty printing algorithm in Go. | ||||||||||

Algorithms | 4 | a year ago | 3 | mit | C++ | |||||

A collection of templates/algorithms for competitive coding. | ||||||||||

Packager | 3 | 7 years ago | JavaScript | |||||||

Binary tree bin packing algorithm for packing pictures to sheet for printing | ||||||||||

Diff Java | 2 | 7 years ago | gpl-3.0 | Java | ||||||

Clone and improvements | ||||||||||

Soren Cslab Scripts | 2 | 7 years ago | mit | Shell | ||||||

Scripts for fixing firefox locks, printing, timing algorithms, and checking your quota. |

Alternatives To Strip PackingSelect To Compare

Alternative Project Comparisons

Readme

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**

```
@article{zhang2016priority,
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},
volume={116},
number={1},
pages={15--21},
year={2016},
publisher={Elsevier}
}
```

The results can be visualized with the `visualize`

method, **matplotlib** needs to be installed for this.

`example.py`

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:

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 vs 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.

Python

Algorithms

Printing