Bin-Packing Add-on

This add-on is based on the 3D bin packing module py3dbp hosted on PyPI. Both sources of this package are MIT licensed like ezdxf itself.

The Bin Packing Problem

Quote from the Wikipedia article:

The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used.

Example

This code replicates the example used by the py3dbp package:

from typing import List
import ezdxf
from ezdxf import colors
from ezdxf.addons import binpacking as bp

SMALL_ENVELOPE = ("small-envelope", 11.5, 6.125, 0.25, 10)
LARGE_ENVELOPE = ("large-envelope", 15.0, 12.0, 0.75, 15)
SMALL_BOX = ("small-box", 8.625, 5.375, 1.625, 70.0)
MEDIUM_BOX = ("medium-box", 11.0, 8.5, 5.5, 70.0)
MEDIUM_BOX2 = ("medium-box-2", 13.625, 11.875, 3.375, 70.0)
LARGE_BOX = ("large-box", 12.0, 12.0, 5.5, 70.0)
LARGE_BOX2 = ("large-box-2", 23.6875, 11.75, 3.0, 70.0)

ALL_BINS = [
    SMALL_ENVELOPE,
    LARGE_ENVELOPE,
    SMALL_BOX,
    MEDIUM_BOX,
    MEDIUM_BOX2,
    LARGE_BOX,
    LARGE_BOX2,
]


def build_packer():
    packer = bp.Packer()
    packer.add_item("50g [powder 1]", 3.9370, 1.9685, 1.9685, 1)
    packer.add_item("50g [powder 2]", 3.9370, 1.9685, 1.9685, 2)
    packer.add_item("50g [powder 3]", 3.9370, 1.9685, 1.9685, 3)
    packer.add_item("250g [powder 4]", 7.8740, 3.9370, 1.9685, 4)
    packer.add_item("250g [powder 5]", 7.8740, 3.9370, 1.9685, 5)
    packer.add_item("250g [powder 6]", 7.8740, 3.9370, 1.9685, 6)
    packer.add_item("250g [powder 7]", 7.8740, 3.9370, 1.9685, 7)
    packer.add_item("250g [powder 8]", 7.8740, 3.9370, 1.9685, 8)
    packer.add_item("250g [powder 9]", 7.8740, 3.9370, 1.9685, 9)
    return packer


def make_doc():
    doc = ezdxf.new()
    doc.layers.add("FRAME", color=colors.YELLOW)
    doc.layers.add("ITEMS")
    doc.layers.add("TEXT")
    return doc


def main(filename):
    bins: List[bp.Bin] = []
    for box in ALL_BINS:
        packer = build_packer()
        packer.add_bin(*box)
        packer.pack(bp.PickStrategy.BIGGER_FIRST)
        bins.extend(packer.bins)
    doc = make_doc()
    bp.export_dxf(doc.modelspace(), bins, offset=(0, 20, 0))
    doc.saveas(filename)


if __name__ == "__main__":
    main("py3dbp_example.dxf")

Packer Classes

class ezdxf.addons.binpacking.AbstractPacker

bins: List of containers to fill.

items: List of items to pack into the bins.

property is_packed: bool: Returns True if packer is packed, each packer can only be used once.

property unfitted_items: list[Item]: Returns the unfitted items.

__str__() → str: Return str(self).

append_bin(box: Bin) → None: Append a container.

append_item(item: Item) → None: Append a item.

get_fill_ratio() → float: Return the fill ratio of all bins.

get_capacity() → float: Returns the maximum fill volume of all bins.

get_total_weight() → float: Returns the total weight of all fitted items in all bins.

get_total_volume() → float: Returns the total volume of all fitted items in all bins.

pack(pick=PickStrategy.BIGGER_FIRST) → None: Pack items into bins. Distributes all items across all bins.

Packer

class ezdxf.addons.binpacking.Packer

3D Packer inherited from AbstractPacker.

add_bin(name: str, width: float, height: float, depth: float, max_weight: float = UNLIMITED_WEIGHT) → Box: Add a 3D Box container.

add_item(payload, width: float, height: float, depth: float, weight: float = 0.0) → Item: Add a 3D Item to pack.

FlatPacker

class ezdxf.addons.binpacking.FlatPacker

2D Packer inherited from AbstractPacker. All containers and items used by this packer must have a depth of 1.

add_bin(name: str, width: float, height: float, max_weight: float = UNLIMITED_WEIGHT) → Envelope: Add a 2D Envelope container.

add_item(payload, width: float, height: float, weight: float = 0.0) → Item: Add a 2D FlatItem to pack.

Bin Classes

class ezdxf.addons.binpacking.Bin(name, width: float, height: float, depth: float, max_weight: float = UNLIMITED_WEIGHT)

name: Name of then container as string.

width

height

depth

max_weight

property is_empty: bool

__str__() → str: Return str(self).

copy(): Returns a copy.

reset(): Reset the container to empty state.

put_item(item: Item, pivot: tuple[float, float, float]) → bool

get_capacity() → float: Returns the maximum fill volume of the bin.

get_total_weight() → float: Returns the total weight of all fitted items.

get_total_volume() → float: Returns the total volume of all fitted items.

get_fill_ratio() → float: Return the fill ratio.

Box Class

class ezdxf.addons.binpacking.Box(name, width: float, height: float, depth: float, max_weight: float = UNLIMITED_WEIGHT): 3D container inherited from Bin.

Envelope Class

class ezdxf.addons.binpacking.Envelope(name, width: float, height: float, max_weight: float = UNLIMITED_WEIGHT): 2D container inherited from Bin.

Item Class

class ezdxf.addons.binpacking.Item(payload, width: float, height: float, depth: float, weight: float = 0.0)

3D container item.

payload: Arbitrary Python object.

width

height

depth

weight

property bbox: AbstractBoundingBox

property rotation_type: RotationType

property position: tuple[float, float, float]: Returns the position of then lower left corner of the item in the container, the lower left corner is the origin (0, 0, 0).

copy(): Returns a copy, all copies have a reference to the same payload object.

__str__(): Return str(self).

get_volume() → float: Returns the volume of the item.

get_dimension() → tuple[float, float, float]: Returns the item dimension according the rotation_type.

get_transformation() → Matrix44: Returns the transformation matrix to transform the source entity located with the minimum extension corner of its bounding box in (0, 0, 0) to the final location including the required rotation.

FlatItem Class

class ezdxf.addons.binpacking.FlatItem(payload, width: float, height: float, weight: float = 0.0): 2D container item, inherited from Item. Has a default depth of 1.0.

Functions

ezdxf.addons.binpacking.shuffle_pack(packer: AbstractPacker, attempts: int) → AbstractPacker: Random shuffle packing. Returns a new packer with the best packing result, the input packer is unchanged.

Enums

RotationType

class ezdxf.addons.binpacking.RotationType(value, names=_not_given, *values, module=None, qualname=None, type=None, start=1, boundary=None)

Rotation type of an item:

W = width
H = height
D = depth

WHD

HWD

HDW

DHW

DWH

WDH

PickStrategy

class ezdxf.addons.binpacking.PickStrategy(value, names=_not_given, *values, module=None, qualname=None, type=None, start=1, boundary=None)

Order of how to pick items for placement.

BIGGER_FIRST

SMALLER_FIRST

SHUFFLE

Credits

py3dbp package by Enzo Ruiz Pelaez

bp3d by gedex - github repository on which py3dbp is based, written in Go

Optimizing three-dimensional bin packing through simulation (PDF)