twod

Documentation

Index

• type Item
  • func (i *Item) SVG() string
• type NoSolutionError
  • func (e *NoSolutionError) Error() string
• type PackedItem
  • func (p *PackedItem) SVG() string
• type PackedSheet
  • func (s *PackedSheet) SVG() string
• type Problem
  • func (p *Problem) Validate() error
• type Sheet
  • func (s *Sheet) SVG() string
• type Solution
  • func FirstFitDecreasingHeight(problem Problem) (*Solution, error)
  • func NextFitDecreasingHeight(problem Problem) (*Solution, error)
  • func (s *Solution) SVG() string

Types

type Item

type Item struct {
	Name   string `json:"name"`
	Width  int64  `json:"width"`
	Height int64  `json:"height"`
}

Item describes a single item we want to pack on a sheet

func (*Item) SVG

func (i *Item) SVG() string

SVG produces an SVG representation of this item

type NoSolutionError

type NoSolutionError struct {
	Item   Item
	Reason string
}

NoSolutionError indicates that a problem has no solution

func (*NoSolutionError) Error

func (e *NoSolutionError) Error() string

type PackedItem

type PackedItem struct {
	Item
	OffsetX int64 `json:"x"`
	OffsetY int64 `json:"y"`
}

PackedItem is an item placed somewhere in space

func (*PackedItem) SVG

func (p *PackedItem) SVG() string

SVG produces an SVG representation of this item

type PackedSheet

type PackedSheet struct {
	Sheet
	Items []PackedItem `json:"items"`
}

PackedSheet contains a set of items aranged on a sheet

func (*PackedSheet) SVG

func (s *PackedSheet) SVG() string

SVG produces an SVG representation of this sheet

type Problem

type Problem struct {
	Sheet Sheet  `json:"sheet"`
	Items []Item `json:"items"`
}

Problem describes the situation we wish to optimize

func (*Problem) Validate

func (p *Problem) Validate() error

Validate checks if the problem can be solved. If this returns an error the problem definitely cannot be solved. If this does not return an error it's still possible that the problem has no solution.

type Sheet

type Sheet struct {
	Width int64 `json:"width"`

	// Height is the height of the sheet in units. If zero we'll pack a single infinite sheet
	Height int64 `json:"height,omitempty"`
}

Sheet describes the container we want to pack the items on

func (*Sheet) SVG

func (s *Sheet) SVG() string

SVG produces an SVG representation of this sheet

type Solution

type Solution struct {
	Sheets []PackedSheet `json:"sheet"`
	Cost   int64         `json:"cost"`
}

Solution has the items packed on sheets

func FirstFitDecreasingHeight

func FirstFitDecreasingHeight(problem Problem) (*Solution, error)

FirstFitDecreasingHeight implements the first-fit-decreasing-height algorithm of Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms E. G. Coffman, Jr., M. R. Garey, D. S. Johnson, and R. E. Tarjan SIAM Journal on Computing 1980 9:4, 808-826

func NextFitDecreasingHeight

func NextFitDecreasingHeight(problem Problem) (*Solution, error)

NextFitDecreasingHeight implements the next-fit-decreasing-height algorithm of Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms E. G. Coffman, Jr., M. R. Garey, D. S. Johnson, and R. E. Tarjan SIAM Journal on Computing 1980 9:4, 808-826

func (*Solution) SVG

func (s *Solution) SVG() string

SVG produces an SVG representation of this item