anchovy.utils.rectbinpacker source code

1 /*
2 Copyright (c) 2013 Andrey Penechko
3 
4 Boost Software License - Version 1.0 - August 17th, 2003
5 
6 Permission is hereby granted, free of charge, to any person or organization
7 obtaining a copy of the software and accompanying documentation covered by
8 this license the "Software" to use, reproduce, display, distribute,
9 execute, and transmit the Software, and to prepare derivative works of the
10 Software, and to permit third-parties to whom the Software is furnished to
11 do so, all subject to the following:
12 
13 The copyright notices in the Software and this entire statement, including
14 the above license grant, this restriction and the following disclaimer,
15 must be included in all copies of the Software, in whole or in part, and
16 all derivative works of the Software, unless such copies or derivative
17 works are solely in the form of machine-executable object code generated by
18 a source language processor.
19 
20 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
21 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22 FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
23 SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
24 FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
25 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
26 DEALINGS IN THE SOFTWARE.
27 */
28 
29 module anchovy.utils.rectbinpacker;
30 
31 
32 import anchovy.utils.rect;
33 /**
34  * Rewrite of Jukka Jylanki's RectangleBinPacker
35  */
36 
37 struct Node
38 {
39 	Rect rect;
40 	Node* left, right;
41 }
42 
43 class RectBinPacker
44 {
45 	this(in uint width, in uint height, in uint x = 0, in uint y = 0)
46 	{
47 		binWidth = width;
48 		binHeight = height;
49 		root.left = root.right = null;
50 		root.rect.x = x;
51 		root.rect.y = y;
52 		root.rect.width = width;
53 		root.rect.height = height;
54 	}
55 
56 	/**
57 	 * Running time is linear to the number of rectangles already packed. Recursively calls itself.
58 	 * @Returns: null If the insertion didn't succeed.
59 	 */
60 	Node* insert(in uint width, in uint height)
61 	{
62 		return insert(&root, width, height);
63 	}
64 
65 	/++
66 	 + @Returns: A value [0, 1] denoting the ratio of total surface area that is in use.
67 	 + 0.0f - the bin is totally empty, 1.0f - the bin is full.
68 	 +/
69 	float Occupancy()
70 	{
71 		ulong totalSurfaceArea = binWidth * binHeight;
72 		ulong usedSurfaceArea = UsedSurfaceArea(&root);
73 
74 		return cast(float)usedSurfaceArea/totalSurfaceArea;
75 	}
76 
77 private:
78 
79 	uint binWidth;
80 	uint binHeight;
81 
82 	Node root;
83 
84 	Node* insert(Node* node, in uint width, in uint height)
85 	{
86 		if (node.left !is null || node.right !is null)
87 		{
88 			if (node.left !is null)
89 			{
90 				Node* newNode = insert(node.left, width, height);
91 				if (newNode)
92 					return newNode;
93 			}
94 			if (node.right !is null)
95 			{
96 				Node* newNode = insert(node.right, width, height);
97 				if (newNode !is null)
98 					return newNode;
99 			}
100 			return null; // Didn't fit into either subtree!
101 		}
102 
103 		if (width > node.rect.width || height > node.rect.height)
104 			return null; // no space.
105 
106 		int w = node.rect.width - width;
107 		int h = node.rect.height - height;
108 
109 		node.left = new Node();
110 		node.right = new Node();
111 
112 		if (w <= h) // Split the remaining space in horizontal direction.
113 		{
114 			node.left.rect.x = node.rect.x + width;
115 			node.left.rect.y = node.rect.y;
116 			node.left.rect.width = w;
117 			node.left.rect.height = height;
118 
119 			node.right.rect.x = node.rect.x;
120 			node.right.rect.y = node.rect.y + height;
121 			node.right.rect.width = node.rect.width;
122 			node.right.rect.height = h;
123 		}
124 		else // Split the remaining space in vertical direction.
125 		{
126 			node.left.rect.x = node.rect.x;
127 			node.left.rect.y = node.rect.y + height;
128 			node.left.rect.width = width;
129 			node.left.rect.height = h;
130 
131 			node.right.rect.x = node.rect.x + width;
132 			node.right.rect.y = node.rect.y;
133 			node.right.rect.width = w;
134 			node.right.rect.height = node.rect.height;
135 		}
136 
137 		node.rect.width = width;
138 		node.rect.height = height;
139 		return node;
140 	}
141 
142 	ulong UsedSurfaceArea(Node* node) const
143 	{
144 		if (node.left || node.right)
145 		{
146 			ulong usedSurfaceArea = node.rect.width * node.rect.height;
147 
148 			if (node.left !is null)
149 			{
150 				usedSurfaceArea += UsedSurfaceArea(node.left);
151 			}
152 			if (node.right !is null)
153 			{
154 				usedSurfaceArea += UsedSurfaceArea(node.right);
155 			}
156 
157 			return usedSurfaceArea;
158 		}
159 
160 		// This is a leaf node, it doesn't constitute to the total surface area.
161 		return 0;
162 	}
163 }