A solver to find a solution of the 2D rectangle packing problem by simulated annealing (SA) optimization.
Project description
rectangle-packing-solver
A solver to find a solution of the 2D rectangle packing problem by simulated annealing (SA) optimization. Sequence-pair [1] is used to represent a rectangle placement (floorplan).
Features
- Solution quality and execution time are tunable, since the solver is SA-based.
- Not only integers but also real numbers can be set as a rectangle width and height.
- A rectangle can rotate while optimizing.
- The built-in visualizer visualizes a floorplan solution.
Installation
pip install rectangle-packing-solver
Example Usage
Sample code:
import rectangle_packing_solver as rps
# Define a problem
problem = rps.Problem(rectangles=[
[4, 6], # Format: [width, height] as list. Default rotatable: False
(4, 4), # Format: (width, height) as tuple. Default rotatable: False
{"width": 2.1, "height": 3.2, "rotatable": False}, # Or can be defined as dict.
{"width": 1, "height": 5, "rotatable": True},
])
print("problem:", problem)
# Find a solution
solution = rpm.Solver().solve(problem=problem)
print("solution:", solution)
# Visualization (to floorplan.png)
rps.Visualizer().visualize(solution=solution, path="./floorplan.png")
# [Other Usages]
# We can also give a solution width (and/or height) limit
solution = rps.Solver().solve(problem=problem, height_limit=6.5)
print("solution (with limit):", solution)
rps.Visualizer().visualize(solution=solution, path="./figs/floorplan_limit.png")
Output:
problem: Problem({'n': 4, 'rectangles': [{'id': 0, 'width': 4, 'height': 6, 'rotatable': False}, {'id': 1, 'width': 4, 'height': 4, 'rotatable': False}, {'id': 2, 'width': 2.1, 'height': 3.2, 'rotatable': False}, {'id': 3, 'width': 1, 'height': 5, 'rotatable': True}]})
solution: Solution({'sequence_pair': SequencePair(([0, 1, 3, 2], [3, 0, 2, 1])), 'floorplan': Floorplan({'positions': [{'id': 0, 'x': 0, 'y': 1}, {'id': 1, 'x': 4, 'y': 3.2}, {'id': 2, 'x': 5.0, 'y': 0.0}, {'id': 3, 'x': 0, 'y': 0}], 'bounding_box': (8, 7.2), 'area': 57.6})})
solution (with limit): Solution({'sequence_pair': SequencePair(([0, 1, 2, 3], [0, 3, 1, 2])), 'floorplan': Floorplan({'positions': [{'id': 0, 'x': 0, 'y': 0, 'width': 4, 'height': 6}, {'id': 1, 'x': 4, 'y': 1, 'width': 4, 'height': 4}, {'id': 2, 'x': 8.0, 'y': 1.0, 'width': 2.1, 'height': 3.2}, {'id': 3, 'x': 4, 'y': 0, 'width': 5, 'height': 1}], 'bounding_box': (10.1, 6), 'area': 60.599999999999994})})
Floorplan (example):
Floorplan (larger example):
References
[1] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "VLSI module placement based on rectangle-packing by the sequence-pair," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, no. 12, pp. 1518--1524, Dec 1996.
License
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Close
Hashes for rectangle-packing-solver-0.0.3.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | 24255228497ea2369f2fb4e24c044001a22fa71047ea16a4e0f2b5bf11002764 |
|
MD5 | 02c344250f0ea780c4342d3e8daf980a |
|
BLAKE2b-256 | 91a78615556c346a6606354e59b2cd85e37b84faef08d305c89bd572a8da2145 |
Close
Hashes for rectangle_packing_solver-0.0.3-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e99ed510dcf9bafd17ff1f15e57574cbd562b7b08b3fb545de8eabc082745e0f |
|
MD5 | db2f37d7cdc1eca1541aadd8f9a1a3f7 |
|
BLAKE2b-256 | 2300ea3e3c29f94d8d1e1574cea38215e8422b962ce0308043f8dbd83eb53d53 |