1 | import { EDGE_MAX_VALUE, IOption } from "./maxrects-packer";
|
2 | import { Rectangle, IRectangle } from "./geom/Rectangle";
|
3 | import { Bin } from "./abstract-bin";
|
4 |
|
5 | export class MaxRectsBin<T extends IRectangle = Rectangle> extends Bin {
|
6 | public width: number;
|
7 | public height: number;
|
8 | public freeRects: Rectangle[] = [];
|
9 | public rects: IRectangle[] = [];
|
10 | private verticalExpand: boolean = false;
|
11 | private stage: Rectangle;
|
12 |
|
13 | constructor (
|
14 | public maxWidth: number = EDGE_MAX_VALUE,
|
15 | public maxHeight: number = EDGE_MAX_VALUE,
|
16 | public padding: number = 0,
|
17 | public options: IOption = { smart: true, pot: true, square: true, allowRotation: false, tag: false }
|
18 | ) {
|
19 | super();
|
20 | this.width = this.options.smart ? 0 : maxWidth;
|
21 | this.height = this.options.smart ? 0 : maxHeight;
|
22 | this.freeRects.push(new Rectangle(this.maxWidth + this.padding, this.maxHeight + this.padding));
|
23 | this.stage = new Rectangle(this.width, this.height);
|
24 | }
|
25 |
|
26 | public add (rect: T): T | undefined;
|
27 | public add (width: number, height: number, data: any): Rectangle | undefined;
|
28 | public add (...args: any[]): any {
|
29 | let width: number;
|
30 | let height: number;
|
31 | let data: any;
|
32 | let rect: IRectangle | undefined;
|
33 | if (args.length === 1) {
|
34 | if (typeof args[0] !== 'object') throw new Error("MacrectsBin.add(): Wrong parameters");
|
35 | rect = args[0] as T;
|
36 | width = rect.width;
|
37 | height = rect.height;
|
38 |
|
39 | if (this.options.tag && this.tag !== rect.tag) return undefined;
|
40 | } else {
|
41 | width = args[0];
|
42 | height = args[1];
|
43 | data = args.length > 2 ? args[2] : null;
|
44 |
|
45 | if (this.options.tag) {
|
46 | if (data && this.tag !== data.tag) return undefined;
|
47 | if (!data && this.tag) return undefined;
|
48 | }
|
49 | }
|
50 |
|
51 | let node: Rectangle | undefined = this.findNode(width + this.padding, height + this.padding);
|
52 | if (node) {
|
53 | this.updateBinSize(node);
|
54 | let numRectToProcess = this.freeRects.length;
|
55 | let i: number = 0;
|
56 | while (i < numRectToProcess) {
|
57 | if (this.splitNode(this.freeRects[i], node)) {
|
58 | this.freeRects.splice(i, 1);
|
59 | numRectToProcess--;
|
60 | i--;
|
61 | }
|
62 | i++;
|
63 | }
|
64 | this.pruneFreeList();
|
65 | this.verticalExpand = this.width > this.height ? true : false;
|
66 | if (!rect) {
|
67 | rect = new Rectangle(width, height, node.x, node.y, node.rot);
|
68 | rect.data = data;
|
69 | } else {
|
70 | rect.x = node.x;
|
71 | rect.y = node.y;
|
72 | rect.rot = node.rot;
|
73 | }
|
74 | this.rects.push(rect);
|
75 | return rect;
|
76 | } else if (!this.verticalExpand) {
|
77 | if (this.updateBinSize(new Rectangle(width + this.padding, height + this.padding, this.width + this.padding, 0))
|
78 | || this.updateBinSize(new Rectangle(width + this.padding, height + this.padding, 0, this.height + this.padding))) {
|
79 | return rect ? this.add(rect as T) : this.add(width, height, data);
|
80 | }
|
81 | } else {
|
82 | if (this.updateBinSize(new Rectangle(
|
83 | width + this.padding, height + this.padding,
|
84 | 0, this.height + this.padding
|
85 | )) || this.updateBinSize(new Rectangle(
|
86 | width + this.padding, height + this.padding,
|
87 | this.width + this.padding, 0
|
88 | ))) {
|
89 | return rect ? this.add(rect as T) : this.add(width, height, data);
|
90 | }
|
91 | }
|
92 | return undefined;
|
93 | }
|
94 |
|
95 | private findNode (width: number, height: number): Rectangle | undefined {
|
96 | let score: number = Number.MAX_VALUE;
|
97 | let areaFit: number;
|
98 | let r: Rectangle;
|
99 | let bestNode: Rectangle | undefined;
|
100 | for (let i in this.freeRects) {
|
101 | r = this.freeRects[i];
|
102 | if (r.width >= width && r.height >= height) {
|
103 | areaFit = r.width * r.height - width * height;
|
104 | if (areaFit < score) {
|
105 | bestNode = new Rectangle(width, height, r.x, r.y);
|
106 | score = areaFit;
|
107 | }
|
108 | }
|
109 | if (!this.options.allowRotation) continue;
|
110 |
|
111 | if (r.width >= height && r.height >= width) {
|
112 | areaFit = r.width * r.height - height * width;
|
113 | if (areaFit < score) {
|
114 | bestNode = new Rectangle(width, height, r.x, r.y, true);
|
115 | score = areaFit;
|
116 | }
|
117 | }
|
118 | }
|
119 | return bestNode;
|
120 | }
|
121 |
|
122 | private splitNode (freeRect: Rectangle, usedNode: Rectangle): boolean {
|
123 |
|
124 | if (!freeRect.collide(usedNode)) return false;
|
125 |
|
126 |
|
127 | if (usedNode.x < freeRect.x + freeRect.width && usedNode.x + usedNode.width > freeRect.x) {
|
128 |
|
129 | if (usedNode.y > freeRect.y && usedNode.y < freeRect.y + freeRect.height) {
|
130 | let newNode: Rectangle = new Rectangle(freeRect.width, usedNode.y - freeRect.y, freeRect.x, freeRect.y);
|
131 | this.freeRects.push(newNode);
|
132 | }
|
133 |
|
134 | if (usedNode.y + usedNode.height < freeRect.y + freeRect.height) {
|
135 | let newNode = new Rectangle(
|
136 | freeRect.width,
|
137 | freeRect.y + freeRect.height - (usedNode.y + usedNode.height),
|
138 | freeRect.x,
|
139 | usedNode.y + usedNode.height
|
140 | );
|
141 | this.freeRects.push(newNode);
|
142 | }
|
143 | }
|
144 |
|
145 |
|
146 | if (usedNode.y < freeRect.y + freeRect.height &&
|
147 | usedNode.y + usedNode.height > freeRect.y) {
|
148 |
|
149 | if (usedNode.x > freeRect.x && usedNode.x < freeRect.x + freeRect.width) {
|
150 | let newNode = new Rectangle(usedNode.x - freeRect.x, freeRect.height, freeRect.x, freeRect.y);
|
151 | this.freeRects.push(newNode);
|
152 | }
|
153 |
|
154 | if (usedNode.x + usedNode.width < freeRect.x + freeRect.width) {
|
155 | let newNode = new Rectangle(
|
156 | freeRect.x + freeRect.width - (usedNode.x + usedNode.width),
|
157 | freeRect.height,
|
158 | usedNode.x + usedNode.width,
|
159 | freeRect.y
|
160 | );
|
161 | this.freeRects.push(newNode);
|
162 | }
|
163 | }
|
164 | return true;
|
165 | }
|
166 |
|
167 | private pruneFreeList () {
|
168 |
|
169 | let i: number = 0;
|
170 | let j: number = 0;
|
171 | let len: number = this.freeRects.length;
|
172 | while (i < len) {
|
173 | j = i + 1;
|
174 | let tmpRect1 = this.freeRects[i];
|
175 | while (j < len) {
|
176 | let tmpRect2 = this.freeRects[j];
|
177 | if (tmpRect2.contain(tmpRect1)) {
|
178 | this.freeRects.splice(i, 1);
|
179 | i--;
|
180 | len--;
|
181 | break;
|
182 | }
|
183 | if (tmpRect1.contain(tmpRect2)) {
|
184 | this.freeRects.splice(j, 1);
|
185 | j--;
|
186 | len--;
|
187 | }
|
188 | j++;
|
189 | }
|
190 | i++;
|
191 | }
|
192 | }
|
193 |
|
194 | private updateBinSize (node: Rectangle): boolean {
|
195 | if (!this.options.smart) return false;
|
196 | if (this.stage.contain(node)) return false;
|
197 | let tmpWidth: number = Math.max(this.width, node.x + node.width - this.padding);
|
198 | let tmpHeight: number = Math.max(this.height, node.y + node.height - this.padding);
|
199 | if (this.options.pot) {
|
200 | tmpWidth = Math.pow(2, Math.ceil(Math.log(tmpWidth) * Math.LOG2E));
|
201 | tmpHeight = Math.pow(2, Math.ceil(Math.log(tmpHeight) * Math.LOG2E));
|
202 | }
|
203 | if (this.options.square) {
|
204 | tmpWidth = tmpHeight = Math.max(tmpWidth, tmpHeight);
|
205 | }
|
206 | if (tmpWidth > this.maxWidth + this.padding || tmpHeight > this.maxHeight + this.padding) {
|
207 | return false;
|
208 | }
|
209 | this.expandFreeRects(tmpWidth + this.padding, tmpHeight + this.padding);
|
210 | this.width = this.stage.width = tmpWidth;
|
211 | this.height = this.stage.height = tmpHeight;
|
212 | return true;
|
213 | }
|
214 |
|
215 | private expandFreeRects (width: number, height: number) {
|
216 | this.freeRects.forEach((freeRect, index) => {
|
217 | if (freeRect.x + freeRect.width >= Math.min(this.width + this.padding, width)) {
|
218 | freeRect.width = width - freeRect.x;
|
219 | }
|
220 | if (freeRect.y + freeRect.height >= Math.min(this.height + this.padding, height)) {
|
221 | freeRect.height = height - freeRect.y;
|
222 | }
|
223 | }, this);
|
224 | this.freeRects.push(new Rectangle(width - this.width - this.padding, height, this.width + this.padding, 0));
|
225 | this.freeRects.push(new Rectangle(width, height - this.height - this.padding, 0, this.height + this.padding));
|
226 | this.freeRects.forEach((freeRect, index) => {
|
227 | if (freeRect.width <= 0 || freeRect.height <= 0) {
|
228 | this.freeRects.splice(index, 1);
|
229 | }
|
230 | }, this);
|
231 | this.pruneFreeList();
|
232 | }
|
233 | }
|