BPP

[ytgui]

https://github.com/wwei10/ga-bpp https://github.com/YacineGACI/BinPacking-GeneticAlgorithm https://github.com/pnvasko/GeneticBinPacker https://github.com/scottndiku/Binpacking-GA

[ytgui]

import random
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import patches

class Rect:
    def __init__(self, left_top, right_bottom=None):
        if not right_bottom:
            self.left, self.top = 0, 0
            self.right, self.bottom = left_top
        else:
            self.left, self.top = left_top
            self.right, self.bottom = right_bottom

    def height(self):
        return self.bottom - self.top

    def width(self):
        return self.right - self.left

    def area(self):
        return self.height() * self.width()

class BPPSolver:
    def __init__(self):
        self.option_rects = [Rect([2, 2]), Rect([3, 3]), Rect([4, 4]),
                             Rect([2, 3]), Rect([3, 2]), Rect([2, 4]), Rect([4, 2]), 
                             Rect([3, 4]), Rect([4, 3])]
        self.target_rect = None

    def solve(self, target_rect, depth=0):
        if depth == 0:
            self.target_rect = target_rect
        # exit condition
        assert target_rect.area() >= 0
        assert target_rect.width() >= 0
        assert target_rect.height() >= 0
        if target_rect.area() == 0:
            return True, []
        # recursive
        option_rects = self.option_rects.copy()
        random.shuffle(option_rects)
        for rect in option_rects:
            for new_target_1, new_target_2 in self.fill_area(target_rect, rect):
                if not self.rect_valid(new_target_1):
                    continue
                if not self.rect_valid(new_target_2):
                    continue
                assert new_target_1.area() + new_target_2.area() + rect.area() == target_rect.area()
                current_path = list()
                ret_1, path_1 = self.solve(new_target_1, depth=depth+1)
                ret_2, path_2 = self.solve(new_target_2, depth=depth+1)
                if ret_1 and ret_2:
                    rect_with_coord = Rect(left_top=[target_rect.left, target_rect.top],
                                           right_bottom=[target_rect.left + rect.width(), target_rect.top + rect.height()])
                    current_path.extend(path_1)
                    current_path.extend(path_2)
                    current_path.append(rect_with_coord)
                    return True, current_path
        return False, None

    def fill_area(self, current_rect, padding_rect):
        def spilt_vertical():
            new_rect_1 = Rect(left_top=(current_rect.left, current_rect.top + padding_rect.height()),
                            right_bottom=(current_rect.left + padding_rect.width(), current_rect.bottom))
            new_rect_2 = Rect(left_top=(current_rect.left + padding_rect.width(), current_rect.top),
                            right_bottom=(current_rect.right, current_rect.bottom))
            if random.random() < 0.5:
                return new_rect_1, new_rect_2
            return new_rect_2, new_rect_1

        def spilt_horizontal():
            new_rect_1 = Rect(left_top=(current_rect.left, current_rect.top + padding_rect.height()),
                            right_bottom=(current_rect.right, current_rect.bottom))
            new_rect_2 = Rect(left_top=(current_rect.left + padding_rect.width(), current_rect.top),
                            right_bottom=(current_rect.right, current_rect.bottom + padding_rect.height()))
            if random.random() < 0.5:
                return new_rect_1, new_rect_2
            return new_rect_2, new_rect_1

        if random.random() < 0.5:
            yield spilt_vertical()
            yield spilt_horizontal()
        else:
            yield spilt_horizontal()
            yield spilt_vertical()
        return

    def rect_valid(self, rect):
        if not self.target_rect.left <= rect.left <= rect.right <= self.target_rect.right:
            return False
        if not self.target_rect.top <= rect.top <= rect.bottom <= self.target_rect.bottom:
            return False
        return True

def check_no_overlap(big_rect, small_rect_list):
    pass

def main():
    #
    solver = BPPSolver()
    target_rect = Rect([16, 24])
    ret, result = solver.solve(target_rect=target_rect)
    print(ret, len(result))
    #
    plt.figure()
    plt.xlim(-5, target_rect.width() + 5)
    plt.ylim(-5, target_rect.height() + 5)
    currentAxis = plt.gca()
    for rect in result:
        currentAxis.add_patch(patches.Rectangle((rect.left, rect.top), rect.width(), rect.height(), alpha=1, color=np.random.rand(3)))
    plt.tight_layout()
    plt.show()

if __name__ == "__main__":
    # random.seed(4)
    main()

[ytgui]