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")
../_images/binpacking-example.png

See also

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)