Skip to main content

A solver to find a solution of the 2D rectangle packing problem by simulated annealing (SA) optimization.

Project description

rectangle-packing-solver

PyPI PyPI - Python Version GitHub Repo Size GitHub Workflow Status Codecov branch GitHub License FOSSA Status

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
print("\n=== Solving without width/height constraints ===")
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, as well as progress bar and random seed
print("\n=== Solving with width/height constraints ===")
solution = rps.Solver().solve(problem=problem, height_limit=6.5, show_progress=True, seed=1111)
print("solution:", 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}]})

=== Solving without width/height constraints ===
solution: Solution({'sequence_pair': SequencePair(([3, 0, 2, 1], [0, 1, 3, 2])), 'floorplan': Floorplan({'positions': [{'id': 0, 'x': 0, 'y': 0, 'width': 4, 'height': 6}, {'id': 1, 'x': 4, 'y': 0, 'width': 4, 'height': 4}, {'id': 2, 'x': 5.0, 'y': 4.0, 'width': 2.1, 'height': 3.2}, {'id': 3, 'x': 0, 'y': 6, 'width': 5, 'height': 1}], 'bounding_box': (8, 7.2), 'area': 57.6})})

=== Solving with width/height constraints ===
Progress: 100%|█████████████████████████████████████████████████████████████| 10000/10000 [00:05<00:00, 1764.33it/s]
solution: 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_example

Floorplan (larger example):

floorplan_large

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

FOSSA Status

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

rectangle-packing-solver-0.0.5.tar.gz (19.2 kB view hashes)

Uploaded source

Built Distribution

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page