rectpack

package module
v0.1.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 13, 2023 License: MIT Imports: 6 Imported by: 0

README

rectpack

A 2D rectangle packing library written in Go, supporting multiple algorithms and heuristics.

Documentation

Index

Constants

View Source 
const (

	// MaxRects selects the MaxRects algorithm for packing. This generally results in the
	// most efficiently packed results when packing to a static size. It can result in a lot of
	// waste if a sensible size and bin heustic is not chosen for the given inputs, but has the
	// most potential for efficiency.
	//
	// Type: Algorithm
	MaxRects Heuristic = 0x0

	// Skyline selects the Skyline algorithm for packing. Skyline provides a good balance between
	// speed and efficiency, and is good for maintaining the least amount of waste at any given
	// time, making it a good choice for dynamic data and simply using whatever the final size may
	// be.
	//
	// Type: Algorithm
	Skyline = 0x1

	// Guillotine selects the Guillotine algorithm for packing. This algorithm is typically
	// faster, but is much more sensitive to choosing the correct packing/splitting methods for
	// specific inputs. This makes it less "general-purpose", but can still be the best choice
	// in certain situations where the input sizes are predictable.
	//
	// Type: Algorithm
	Guillotine = 0x2

	// BestShortSideFit (BSSF) positions the rectangle against the short side of a free rectangle
	// into which it fits the best.
	//
	//	* Type: Bin-Selection
	//	* Valid With: MaxRects, Guillotine
	BestShortSideFit = 0x00
	// BestLongSideFit (BLSF) positions the rectangle against the long side of a free rectangle
	// into which it fits the best.
	//
	//	* Type: Bin-Selection
	//	* Valid With: MaxRects, Guillotine
	BestLongSideFit = 0x10
	// BestAreaFit (BAF) positions the rectangle into the smallest free rect into which it fits.
	//
	//	* Type: Bin-Selection
	//	* Valid With: MaxRects, Guillotine
	BestAreaFit = 0x20
	// BottomLeft (BL) does the Tetris placement.
	//
	//	* Type: Bin-Selection
	//	* Valid With: MaxRects, Skyline
	BottomLeft = 0x30
	// ContactPoint (CP) choosest the placement where the rectangle touches other rects as much
	// as possible.
	//
	//	* Type: Bin-Selection
	//	* Valid With: MaxRects
	ContactPoint = 0x40
	// WorstAreaFit (WAF) is the opposite of the BestAreaFit (BAF) heuristic. Contrary to its
	// name, this is not always "worse" with speciifc inputs.
	//
	//	* Type: Bin-Selection
	//	* Valid With: Guillotine
	WorstAreaFit = 0x50
	// WorstShortSideFit (WSSF) is the opposite of the BestShortSideFit (BSSF) heuristic. Contrary
	// to its name, this is not always "worse" with speciifc inputs.
	//
	//	* Type: Bin-Selection
	//	* Valid With: Guillotine
	WorstShortSideFit = 0x60
	// WorstLongSideFit (WLSF) is the opposite of the BestLongSideFit (BLSF) heuristic. Contrary
	// to its name, this is not always "worse" with speciifc inputs.
	//
	//	* Type: Bin-Selection
	//	* Valid With: Guillotine
	WorstLongSideFit = 0x70
	// MinWaste (MW) uses a "waste map" to split empty spaces and determine which placement will
	// result in the least amount of wasted space. This is most effective when flip/rotate is
	// enabled by the packer.
	//
	//	* Type: Bin-Selection
	//	* Valid With: Skyline
	MinWaste = 0x80

	// SplitShorterLeftoverAxis (SLAS)
	//
	//	* Type: Split Method
	//	* Valid With: Guillotine
	SplitShorterLeftoverAxis = 0x0000

	// SplitLongerLeftoverAxis (LLAS)
	//
	//	* Type: Split Method
	//	* Valid With: Guillotine
	SplitLongerLeftoverAxis = 0x0100

	// SplitMinimizeArea (MINAS) try to make a single big rectangle at the expense of making the
	// other small.
	//
	//	* Type: Split Method
	//	* Valid With: Guillotine
	SplitMinimizeArea = 0x0200

	// SplitMaximizeArea (MAXAS) try to make both remaining rectangles as even-sized as possible.
	//
	//	*Type: Split Method
	//	* Valid With: Guillotine
	SplitMaximizeArea = 0x0300

	// SplitShorterAxis (SAS)
	//
	//	* Type: Split Method
	//	* Valid With: Guillotine
	SplitShorterAxis = 0x0400

	// SplitLongerAxis (LAS)
	//
	//	* Type: Split Method
	//	* Valid With: Guillotine
	SplitLongerAxis = 0x0500

	// MaxRectsBSSF
	//
	//	* Type: Preset
	MaxRectsBSSF = MaxRects | BestShortSideFit

	// MaxRectsBL
	//
	//	* Type: Preset
	MaxRectsBL = MaxRects | BottomLeft

	// MaxRectsCP
	//
	//	* Type: Preset
	MaxRectsCP = MaxRects | ContactPoint

	// MaxRectsBLSF
	//
	//	* Type: Preset
	MaxRectsBLSF = MaxRects | BestLongSideFit

	// MaxRectsBAF
	//
	//	* Type: Preset
	MaxRectsBAF = MaxRects | BestAreaFit

	// GuillotineBAF
	//
	//	* Type: Preset
	GuillotineBAF = Guillotine | BestAreaFit

	// GuillotineBSSF
	//
	//	* Type: Preset
	GuillotineBSSF = Guillotine | BestShortSideFit

	// GuillotineBLSF
	//
	//	* Type: Preset
	GuillotineBLSF = Guillotine | BestLongSideFit

	// GuillotineWAF
	//
	//	* Type: Preset
	GuillotineWAF = Guillotine | WorstAreaFit

	// GuillotineWSSF
	//
	//	* Type: Preset
	GuillotineWSSF = Guillotine | WorstShortSideFit

	// GuillotineWLSF
	//
	//	* Type: Preset
	GuillotineWLSF = Guillotine | WorstLongSideFit

	// SkylineBLF
	//
	//	* Type: Preset
	SkylineBLF = Skyline | BottomLeft

	// SkylineMinWaste
	//
	//	* Type: Preset
	SkylineMinWaste = Skyline | MinWaste
)
View Source 
const DefaultSize = 4096

DefaultSize is the default width/height used as the maximum extent for packing rectangles.

There is based off a maximum texture size for many modern GPUs. If this library is not being used for creating a texture atlas, then there is absolutely no significance about this number other than providing a sane starting point.

Variables

This section is empty.

Functions

func SortArea 

func SortArea(a, b Size) int

SortArea sorts two rectangle sizes in descending order (greatest to least) by comparing the total area of each.

func SortDiff 

func SortDiff(a, b Size) int

SortDiff sorts two rectangle sizes in descending order (greatest to least) by comparing the difference between the width/height of each.

func SortMaxSide 

func SortMaxSide(a, b Size) int

SortMaxSide sorts two rectangle sizes in descending order (greatest to least) by comparing the longest side of each.

func SortMinSide 

func SortMinSide(a, b Size) int

SortMinSide sorts two rectangle sizes in descending order (greatest to least) by comparing the shortest side of each.

func SortPerimeter 

func SortPerimeter(a, b Size) int

SortPerimeter sorts two rectangle sizes in descending order (greatest to least) by comparing the perimeter of each.

func SortRatio 

func SortRatio(a, b Size) int

SortRatio sorts two rectangle sizes in descending order (greatest to least) by comparing the ratio between the width/height of each.

Types

type Heuristic 

type Heuristic uint16

Heuristic is a bitfield used for configuration of a rectangle packing algorithm, including the general type, bin selection method, and strategy for how to split empty areas. Specific combinations of values can be XOR'ed together to achieve the desired behavior.

Note that not not all combinations are valid, each constant of this type will indicate what it is valid with. If in doubt, simply use a preset.

To test if a value is valid, use the Validate function, which will return an error message describing the issue. When an invalid value is used, the algorithm default will be used, but otherwise no error will occur.

func (Heuristic) Algorithm 

func (e Heuristic) Algorithm() Heuristic

Algorithm returns the algorithm portion of the bitmask.

func (Heuristic) Bin 

func (e Heuristic) Bin() Heuristic

Bin returns the bin selection method portion of the bitmask.

func (Heuristic) Split 

func (e Heuristic) Split() Heuristic

Split returns the split method portion of the bitmask.

func (Heuristic) String 

func (e Heuristic) String() string

String returns the string representation of the heuristic.

func (Heuristic) Validate 

func (e Heuristic) Validate() error

Validate tests whether the combination of heuristics are in good form. A value of nil is returned upon success, otherwise an error with message explaining the error.

Note that invalid heuristics will silently fail and cause the packer to revert to its default for that setting.

type Packer 

type Packer struct {

	// Padding defines the amount of empty space to place around rectangles. Values of 0 or less
	// indicates that rectangles will be tightly packed.
	//
	// Default: 0
	Padding int

	// Online indicates if rectangles should be packed as they are inserted (online), or simply
	// collected until Pack is called.
	//
	// There is a trade-off to online/offline packing.
	//
	// * Online packing is faster to pack due to a lack of sorting or comparing to
	//	 other rectangles, but results in significantly less optimized results.
	// * Offline packing can be significantly slower, but allows the algorithm to achieve its
	//   maximum potential by having all sizes known ahead of time and sorting for efficiency.
	//
	// Unless you are packing and using the results in real-time, it is recommended to use
	// offline mode (default). For tasks such creating a texture atlas, spending the extra time
	// to prepare the atlas in the most efficient manner is well worth the extra milliseconds
	// of computation.
	//
	// Default: false
	Online bool
	// contains filtered or unexported fields
}

Packer contains the state of a 2D rectangle packer.

func NewDefaultPacker 

func NewDefaultPacker() *Packer

NewDefaultPacker initializes a new Packer with sensible default settings suitable for general-purpose rectangle packing.

func NewPacker 

func NewPacker(maxWidth, maxHeight int, heuristic Heuristic) (*Packer, error)

NewPacker initializes a new Packer using the specified maximum size and heustistics for packing rectangles.

A width/height less than 1 will cause a panic,

func (*Packer) AllowFlip 

func (p *Packer) AllowFlip(enabled bool)

AllowFlip indicates if rectangles can be flipped/rotated to provide better placement.

Default: false

func (*Packer) Clear 

func (p *Packer) Clear()

Clear resets the internal state of the packer without changing its current configuration. All currently packed and pending rectangles are removed.

func (*Packer) Insert 

func (p *Packer) Insert(sizes ...Size) []Size

Insert adds to rectangles to the packer.

When online mode is enabled, the rectangle(s) are immediately packed. The return value will contain any values that could not be packed due to size limitations, or an empty slice upon success.

When online mode is disabled, the rectangles(s) are simply staged to be packed with the next call to Pack. The return value will contain a slice of all rectangles that are currently staged.

func (*Packer) InsertSize 

func (p *Packer) InsertSize(id, width, height int) bool

Insert adds to rectangles to the packer.

When online mode is enabled, the rectangle(s) are immediately packed. The return value will contain any values that could not be packed due to size limitations, or an empty slice upon success.

When online mode is disabled, the rectangles(s) are simply staged to be packed with the next call to Pack. The return value will contain a slice of all rectangles that are currently staged.

func (*Packer) Map 

func (p *Packer) Map() map[int]Rect

Map creates and returns a map where each key is an ID, and the value is the rectangle it pertains to.

func (*Packer) Pack 

func (p *Packer) Pack() bool

Pack will sort and pack all rectangles that are currently staged.

The return value indicates if all staged rectangles were successfully packed. When false, Unpacked can be used to retrieve the sizes that failed.

func (*Packer) Rects 

func (p *Packer) Rects() []Rect

Rects returns a slice of rectangles that are currently packed.

The backing memory is owned by the packer, and a copy should be made if modification or persistence is required.

func (*Packer) RepackAll 

func (p *Packer) RepackAll() bool

RepackAll clears the internal packed rectangles, and repacks them all with one operation. This can be useful to optimize the packing when/if it was previously performed in multiple pack operations, or to reflect settings for the packer that have been modified.

func (*Packer) Size 

func (p *Packer) Size() Size

Size computes the size of the current packing. The returned value is the minimum size required to contain all packed rectangles.

func (*Packer) Sorter 

func (p *Packer) Sorter(compare SortFunc, reverse bool)

Sorter sets the comparer function used for pre-sorting sizes before packing. Depending on the algorithm and the input data, this can provide a significant improvement on efficiency.

Default: SortArea

func (*Packer) Unpacked 

func (p *Packer) Unpacked() []Size

Unpacked returns a slice of rectangles that are currently staged to be packed.

The backing memory is owned by the packer, and a copy should be made if modification or persistence is required.

func (*Packer) Used 

func (p *Packer) Used(current bool) float64

Used computes the ratio of used surface area to the available area, in the range of 0.0 and 1.0.

When current is set to true, the ratio will reflect the ratio of used surface area relative to the current size required by the packer, otherwise it is the ratio of the maximum possible area.

type Point 

type Point struct {
	// X is the location on the horizontal x-axis.
	X int `json:"x"`
	// Y is the location on the vertical y-axis.
	Y int `json:"y"`
}

Point describes a location in 2D space.

func NewPoint 

func NewPoint(x, y int) Point

NewPoint initializes a new point with the specified coordinates.

func (*Point) Eq 

func (p *Point) Eq(point Point) bool

Eq tests whether the receiver and another point have equal values.

func (*Point) Move 

func (p *Point) Move(x, y int)

Move will move the location of the receiver to the specified absolute coordinates.

func (*Point) Offset 

func (p *Point) Offset(x, y int)

Offset will move the location of receiver by the specified relative amount.

func (*Point) String 

func (p *Point) String() string

String returns a string representation of the point.

type Rect 

type Rect struct {
	// Point is the location of the rectangle.
	Point
	// Size is the dimensions of the rectangle.
	Size
	// Flipped indicates if a rectangle has been flipped to achieve a better fit while
	// being packed. Only relevant when the packer has AllowFlip enabled.
	Flipped bool `json:"flipped,omitempty"`
}

Rect describes a location (top-left corner) and size in 2D space.

func NewRect 

func NewRect(x, y, w, h int) Rect

NewRect initialzies a new rectangle using the specified point and size values.

func NewRectLTRB 

func NewRectLTRB(l, t, r, b int) Rect

NewRectLTRB initializes a new rectangle using the specified left/top/right/bottom values.

func (*Rect) Bottom 

func (r *Rect) Bottom() int

Bottom returns the coordinate of the bottom-edge of the rectangle on the y-axis.

func (*Rect) BottomLeft 

func (r *Rect) BottomLeft() Point

BottomLeft returns a point representing the bottom-left corner of the rectangle.

func (*Rect) BottomRight 

func (r *Rect) BottomRight() Point

BottomRight returns a point representing the bottom-right corner of the rectangle.

func (*Rect) Center 

func (r *Rect) Center() Point

Centers returns a point representing the center of the rectangle. For rectangles that are a power of two, the coordinate is floored.

func (*Rect) Contains 

func (r *Rect) Contains(x, y int) bool

Contains tests whether the specified coordinates are within the bounds of the receiver.

func (*Rect) ContainsRect 

func (r *Rect) ContainsRect(rect Rect) bool

ContainsRect tests whether the specified rectangle is contained within the bounds of the current receiver.

func (*Rect) Eq 

func (r *Rect) Eq(rect Rect) bool

Eq compares two rectangles to determine if the location and size is equal.

func (*Rect) Inflate 

func (r *Rect) Inflate(width, height int)

Inflate pushes each edge of the rectangle out from the center by the specified relative amount on each axis.

func (*Rect) Intersect 

func (r *Rect) Intersect(rect Rect) (result Rect)

Intersect returns a rectangle representing only the overlapping area of this rectangle and another, or an empty recatangle when no overlap is present.

func (*Rect) Intersects 

func (r *Rect) Intersects(rect Rect) bool

Intersects tests whether the receiver has any overlap with the specified rectangle.

func (*Rect) IsEmpty 

func (r *Rect) IsEmpty() bool

IsEmpty tests whether the width or size of the rectangle is less than 1.

func (*Rect) Left 

func (r *Rect) Left() int

Left returns the coordinate of the left-edge of the rectangle on the x-axis.

func (*Rect) Right 

func (r *Rect) Right() int

Right returns the coordinate of the right-edge of the rectangle on the x-axis.

func (*Rect) String 

func (r *Rect) String() string

String returns a string describing the rectangle.

func (*Rect) Top 

func (r *Rect) Top() int

Top returns the coordinate of the top-edge of the rectangle on the y-axis.

func (*Rect) TopLeft 

func (r *Rect) TopLeft() Point

TopLeft returns a point representing the top-left corner of the rectangle.

func (*Rect) TopRight 

func (r *Rect) TopRight() Point

TopRight returns a point representing the top-right corner of the rectangle.

func (*Rect) Union 

func (r *Rect) Union(rect Rect) Rect

Union returns a minimum rectangle required to contain the receiver and another rectangle.

type Size 

type Size struct {
	// Width is the dimension on the horizontal x-axis.
	Width int `json:"width"`
	// Height is the dimensions on the vertical y-axis.
	Height int `json:"height"`
	// ID is a user-defined identifier that can be used to differentiate this instance from others.
	ID int `json:"-"`
}

Size describes dimensions of an entity in 2D space.

func NewSize 

func NewSize(width, height int) Size

NewSize creates a new size with specified dimensions.

func NewSizeID 

func NewSizeID(id, width, height int) Size

NewSizeID creates a new size with specified dimensions and unique identifier.

func (*Size) Area 

func (sz *Size) Area() int

Area returns the total area (width * height).

func (*Size) Eq 

func (sz *Size) Eq(size Size) bool

Eq tests whether the receiver and another size have equal values. The ID field is ignored.

func (*Size) MaxSide 

func (sz *Size) MaxSide() int

MaxSide returns the value of the greater side.

func (*Size) MinSide 

func (sz *Size) MinSide() int

MinSide returns the value of the lesser side.

func (*Size) Perimeter 

func (sz *Size) Perimeter() int

Perimeter returns the sum length of all sides.

func (*Size) Ratio 

func (sz *Size) Ratio() float64

Ratio compute the ratio between the width/height.

func (*Size) String 

func (p *Size) String() string

String returns a string representation of the size.

type SortFunc 

type SortFunc func(a, b Size) int

SortFunc is a prototype for a funcion that compares two rectangle sizes, returning standard comparer result of -1 for less-than, 1 for greater-than, or 0 for equal to.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.