package grenier

  1. Overview
  2. Docs
A collection of various algorithms in OCaml

Install 

dune-project
 Dependency

github.com Readme Changelog Edit opam file Versions (11)

Authors

  1. F
    Frederic Bour <frederic.bour@lakaban.net>

Maintainers

  1. F
    Frederic Bour <frederic.bour@lakaban.net>

Sources

grenier-0.15.tbz
sha256=dec7f84b9e93d5825f10c7dea84d5a74d7365ede45664ae63c26b5e8045c1c44
sha512=b8aa1569c2e24b89674d1b34de34cd1798896bb6a53aa5a1287f68cee880125e6b687f66ad73da9069a01cc3ece1f0684f48328b099d43529bff736b772c8fd8

doc/grenier.binpacking/Maxrects/index.html

Module MaxrectsSource

Sourcetype 'bin t
Sourceval empty : 'bin t
Sourceval add_bin : 'bin -> int -> int -> 'bin t -> 'bin t

make ~width ~height return a packer ready to place stuff in a width * height area

Sourcetype 'tag box = {
  1. tag : 'tag;
  2. width : int;
  3. height : int;
  4. allow_rotation : bool;
    (*

    can the box be rotated to optimize packing

    *)
}

Input to packing is a box

Sourceval box : ?allow_rotation:bool -> 'tag -> int -> int -> 'tag box
Sourcetype ('bin, 'tag) rect = {
  1. x : int;
  2. y : int;
  3. w : int;
  4. h : int;
  5. rotated : bool;
    (*

    True iff the input box was rotated. If true, w = box.height && h = box.width Otherwise, w = box.width && h = box.height

    *)
  6. bin : 'bin;
  7. box : 'tag box;
}

Output of packing is an optional rectangle

Sourcetype heuristic = [
  1. | `Short_side_fit
    (*

    BSSF. Positions the rectangle against the short side of a free rectangle into which it fits the best.

    *)
  2. | `Long_side_fit
    (*

    BLSF: Positions the rectangle against the long side of a free rectangle into which it fits the best.

    *)
  3. | `Area_fit
    (*

    BAF: Positions the rectangle into the smallest free rect into which it fits.

    *)
  4. | `Bottom_left
    (*

    BL: Does the Tetris placement.

    *)
]
Sourceval insert : 'bin t -> ?heuristic:heuristic -> 'tag box -> 'bin t * ('bin, 'tag) rect option

Online insertion of one item. Efficient but the packing is not very good.

Worst-case: O(n^3) (n is total number of items inserted).

Sourceval insert_batch : 'bin t -> ?heuristic:heuristic -> 'tag box list -> 'bin t * ('bin, 'tag) rect option list

Online insertion of a batch of items. Runtime is roughly the cost of inserting each item independently, but order of insertion is chosen to give a better packing.

Worst-case: O(n^4) (n is total number of items inserted).

Sourceval insert_global : 'bin t -> ?heuristic:heuristic -> 'tag box list -> 'bin t * ('bin, 'tag) rect option list

Offline insertion. Better packing but way too slow for real-time usage.

Worst-case: O(n^5) (n is total number of items inserted).