bp3d

README

bp3d

3D Bin Packing implementation based on this paper. The code is based on binpacking by bom-d-van but modified to allow flexible bins and use float64 instead of int.

Install

go get github.com/gedex/bp3d

Usage

p := bp3d.NewPacker()

// Add bins.
p.AddBin(bp3d.NewBin("Small Bin", 10, 15, 20, 100))
p.AddBin(bp3d.NewBin("Medium Bin", 100, 150, 200, 1000))

// Add items.
p.AddItem(bp3d.NewItem("Item 1", 2, 2, 1, 2))
p.AddItem(bp3d.NewItem("Item 2", 3, 3, 2, 3))

// Pack items to bins.
if err := p.Pack(); err != nil {
	log.Fatal(err)
}

// Each bin, b, in p.Bins might have packed items in b.Items

See example/example.go

Credit

• http://www.cs.ukzn.ac.za/publications/erick_dube_507-034.pdf
• https://github.com/bom-d-van/binpacking

License

MIT

Documentation

Index

• Variables
• type Axis
• type Bin
  • func NewBin(name string, w, h, d, mw float64) *Bin
  • func (b *Bin) GetDepth() float64
  • func (b *Bin) GetHeight() float64
  • func (b *Bin) GetMaxWeight() float64
  • func (b *Bin) GetName() string
  • func (b *Bin) GetVolume() float64
  • func (b *Bin) GetWidth() float64
  • func (b *Bin) PutItem(item *Item, p Pivot) (fit bool)
  • func (b *Bin) String() string
• type BinSlice
  • func (bs BinSlice) Len() int
  • func (bs BinSlice) Less(i, j int) bool
  • func (bs BinSlice) Swap(i, j int)
• type Dimension
• type Item
  • func NewItem(name string, w, h, d, wg float64) *Item
  • func (i *Item) GetDepth() float64
  • func (i *Item) GetDimension() (d Dimension)
  • func (i *Item) GetHeight() float64
  • func (i *Item) GetName() string
  • func (i *Item) GetVolume() float64
  • func (i *Item) GetWeight() float64
  • func (i *Item) GetWidth() float64
  • func (i *Item) Intersect(i2 *Item) bool
  • func (i *Item) String() string
• type ItemSlice
  • func (is ItemSlice) Len() int
  • func (is ItemSlice) Less(i, j int) bool
  • func (is ItemSlice) Swap(i, j int)
• type Packer
  • func NewPacker() *Packer
  • func (p *Packer) AddBin(bins ...*Bin)
  • func (p *Packer) AddItem(items ...*Item)
  • func (p *Packer) FindFittedBin(i *Item) *Bin
  • func (p *Packer) Pack() error
• type Pivot
  • func (pv Pivot) String() string
• type RotationType
  • func (rt RotationType) String() string

Variables

var RotationTypeStrings = [...]string{
	"RotationType_WHD (w,h,d)",
	"RotationType_HWD (h,w,d)",
	"RotationType_HDW (h,d,w)",
	"RotationType_DHW (d,h,w)",
	"RotationType_DWH (d,w,h)",
	"RotationType_WDH (w,d,h)",
}

Types

type Axis

type Axis int

const (
	WidthAxis Axis = iota
	HeightAxis
	DepthAxis
)

type Bin

type Bin struct {
	Name      string
	Width     float64
	Height    float64
	Depth     float64
	MaxWeight float64

	Items []*Item // Items that packed in this bin
}

Bin represents a container in which items will be put into.

func NewBin

func NewBin(name string, w, h, d, mw float64) *Bin

NewBin constructs new Bin with width w, height h, depth d, and max weight mw.

func (*Bin) GetDepth

func (b *Bin) GetDepth() float64

GetDepth returns bin's depth.

func (*Bin) GetHeight

func (b *Bin) GetHeight() float64

GetHeight returns bin's height.

func (*Bin) GetMaxWeight

func (b *Bin) GetMaxWeight() float64

GetDepth returns bin's max weight.

func (*Bin) GetName

func (b *Bin) GetName() string

GetName returns bin's name.

func (*Bin) GetVolume

func (b *Bin) GetVolume() float64

GetDepth returns bin's volume.

func (*Bin) GetWidth

func (b *Bin) GetWidth() float64

GetWidth returns bin's width.

func (*Bin) PutItem

func (b *Bin) PutItem(item *Item, p Pivot) (fit bool)

PutItem tries to put item into pivot p of bin b.

func (*Bin) String

func (b *Bin) String() string

type BinSlice

type BinSlice []*Bin

func (BinSlice) Len

func (bs BinSlice) Len() int

func (BinSlice) Less

func (bs BinSlice) Less(i, j int) bool

func (BinSlice) Swap

func (bs BinSlice) Swap(i, j int)

type Dimension

type Dimension [3]float64

type Item

type Item struct {
	Name   string
	Width  float64
	Height float64
	Depth  float64
	Weight float64

	// Used during packer.Pack()
	RotationType RotationType
	Position     Pivot
}

func NewItem

func NewItem(name string, w, h, d, wg float64) *Item

NewItem returns an Item named name, with width w, height h, depth h, and weight w. The quantity defaults to one.

func (*Item) GetDepth

func (i *Item) GetDepth() float64

func (*Item) GetDimension

func (i *Item) GetDimension() (d Dimension)

func (*Item) GetHeight

func (i *Item) GetHeight() float64

func (*Item) GetName

func (i *Item) GetName() string

func (*Item) GetVolume

func (i *Item) GetVolume() float64

func (*Item) GetWeight

func (i *Item) GetWeight() float64

func (*Item) GetWidth

func (i *Item) GetWidth() float64

func (*Item) Intersect

func (i *Item) Intersect(i2 *Item) bool

Intersect checks whether there's an intersection between item i and item it.

func (*Item) String

func (i *Item) String() string

type ItemSlice

type ItemSlice []*Item

func (ItemSlice) Len

func (is ItemSlice) Len() int

func (ItemSlice) Less

func (is ItemSlice) Less(i, j int) bool

func (ItemSlice) Swap

func (is ItemSlice) Swap(i, j int)

type Packer

type Packer struct {
	Bins       []*Bin
	Items      []*Item
	UnfitItems []*Item // items that don't fit to any bin
}

func NewPacker

func NewPacker() *Packer

func (*Packer) AddBin

func (p *Packer) AddBin(bins ...*Bin)

func (*Packer) AddItem

func (p *Packer) AddItem(items ...*Item)

func (*Packer) FindFittedBin

func (p *Packer) FindFittedBin(i *Item) *Bin

FindFittedBin finds bin in which item i will be fitted into.

func (*Packer) Pack

func (p *Packer) Pack() error

type Pivot

type Pivot [3]float64

func (Pivot) String

func (pv Pivot) String() string

type RotationType

type RotationType int

const (
	RotationType_WHD RotationType = iota
	RotationType_HWD
	RotationType_HDW
	RotationType_DHW
	RotationType_DWH
	RotationType_WDH
)

func (RotationType) String

func (rt RotationType) String() string