-
Notifications
You must be signed in to change notification settings - Fork 0
/
binpacking.ts
60 lines (54 loc) · 1.64 KB
/
binpacking.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/******************************************************************************
The following code is taken from the "binpacker" node module
and translated to Typescript. I couldn't get a d.ts file for this package to work.
From its capabilities it's binary tree packing without the ability to rotate the item.
******************************************************************************/
export interface Item {
/**
* Width
*/
w: number;
/**
* Height
*/
h: number;
/**
* Side-effect by the binpack package once the block has been packed into
* the container area.
*/
fit?: { x: number; y: number };
}
interface Partitionable {
x: number;
y: number;
w: number;
h: number;
used: boolean;
down?: Partitionable;
right?: Partitionable;
}
class Packer {
root: Partitionable;
constructor(width: number, height: number) {
this.root = { x: 0, y: 0, w: width, h: height, used: false };
}
fit(blocks: Item[]) {
let node = null;
for (const block of blocks) {
node = this.findNode(this.root, block.w, block.h);
if (node) block.fit = this.splitNode(node, block.w, block.h);
}
}
private findNode(box: Partitionable, w: number, h: number): any {
if (box.used) {
return this.findNode(box.right!, w, h) || this.findNode(box.down!, w, h);
} else if (w <= box.w && h <= box.h) return box;
else return null;
}
private splitNode(node: Partitionable, w: number, h: number) {
node.used = true;
node.down = { x: node.x, y: node.y + h, w: node.w, h: node.h - h, used: false };
node.right = { x: node.x + w, y: node.y, w: node.w - w, h, used: false };
return node;
}
}