1 /* 2 * Copyright (C) 2012 The Android Open Source Project 3 * 4 * Licensed under the Eclipse Public License, Version 1.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.eclipse.org/org/documents/epl-v10.php 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 package com.android.ide.eclipse.adt.internal.editors.layout.gle2; 17 18 import com.android.annotations.Nullable; 19 import com.android.ide.common.api.Rect; 20 21 import java.awt.Color; 22 import java.awt.Graphics2D; 23 import java.awt.image.BufferedImage; 24 import java.io.File; 25 import java.io.IOException; 26 import java.util.ArrayList; 27 import java.util.List; 28 29 import javax.imageio.ImageIO; 30 31 /** 32 * This class implements 2D bin packing: packing rectangles into a given area as 33 * tightly as "possible" (bin packing in general is NP hard, so this class uses 34 * heuristics). 35 * <p> 36 * The algorithm implemented is to keep a set of (possibly overlapping) 37 * available areas for placement. For each newly inserted rectangle, we first 38 * pick which available space to occupy, and we then subdivide the 39 * current rectangle into all the possible remaining unoccupied sub-rectangles. 40 * We also remove any other space rectangles which are no longer eligible if 41 * they are intersecting the newly placed rectangle. 42 * <p> 43 * This algorithm is not very fast, so should not be used for a large number of 44 * rectangles. 45 */ 46 class BinPacker { 47 /** 48 * When enabled, the successive passes are dumped as PNG images showing the 49 * various available and occupied rectangles) 50 */ 51 private static final boolean DEBUG = false; 52 53 private final List<Rect> mSpace = new ArrayList<Rect>(); 54 private final int mMinHeight; 55 private final int mMinWidth; 56 57 /** 58 * Creates a new {@linkplain BinPacker}. To use it, first add one or more 59 * initial available space rectangles with {@link #addSpace(Rect)}, and then 60 * place the rectangles with {@link #occupy(int, int)}. The returned 61 * {@link Rect} from {@link #occupy(int, int)} gives the coordinates of the 62 * positioned rectangle. 63 * 64 * @param minWidth the smallest width of any rectangle placed into this bin 65 * @param minHeight the smallest height of any rectangle placed into this bin 66 */ 67 BinPacker(int minWidth, int minHeight) { 68 mMinWidth = minWidth; 69 mMinHeight = minHeight; 70 71 if (DEBUG) { 72 mAllocated = new ArrayList<Rect>(); 73 sLayoutId++; 74 sRectId = 1; 75 } 76 } 77 78 /** Adds more available space */ 79 void addSpace(Rect rect) { 80 if (rect.w >= mMinWidth && rect.h >= mMinHeight) { 81 mSpace.add(rect); 82 } 83 } 84 85 /** Attempts to place a rectangle of the given dimensions, if possible */ 86 @Nullable 87 Rect occupy(int width, int height) { 88 int index = findBest(width, height); 89 if (index == -1) { 90 return null; 91 } 92 93 return split(index, width, height); 94 } 95 96 /** 97 * Finds the best available space rectangle to position a new rectangle of 98 * the given size in. 99 */ 100 private int findBest(int width, int height) { 101 if (mSpace.isEmpty()) { 102 return -1; 103 } 104 105 // Try to pack as far up as possible first 106 int bestIndex = -1; 107 boolean multipleAtSameY = false; 108 int minY = Integer.MAX_VALUE; 109 for (int i = 0, n = mSpace.size(); i < n; i++) { 110 Rect rect = mSpace.get(i); 111 if (rect.y <= minY) { 112 if (rect.w >= width && rect.h >= height) { 113 if (rect.y < minY) { 114 minY = rect.y; 115 multipleAtSameY = false; 116 bestIndex = i; 117 } else if (minY == rect.y) { 118 multipleAtSameY = true; 119 } 120 } 121 } 122 } 123 124 if (!multipleAtSameY) { 125 return bestIndex; 126 } 127 128 bestIndex = -1; 129 130 // Pick a rectangle. This currently tries to find the rectangle whose shortest 131 // side most closely matches the placed rectangle's size. 132 // Attempt to find the best short side fit 133 int bestShortDistance = Integer.MAX_VALUE; 134 int bestLongDistance = Integer.MAX_VALUE; 135 136 for (int i = 0, n = mSpace.size(); i < n; i++) { 137 Rect rect = mSpace.get(i); 138 if (rect.y != minY) { // Only comparing elements at same y 139 continue; 140 } 141 if (rect.w >= width && rect.h >= height) { 142 if (width < height) { 143 int distance = rect.w - width; 144 if (distance < bestShortDistance || 145 distance == bestShortDistance && 146 (rect.h - height) < bestLongDistance) { 147 bestShortDistance = distance; 148 bestLongDistance = rect.h - height; 149 bestIndex = i; 150 } 151 } else { 152 int distance = rect.w - width; 153 if (distance < bestShortDistance || 154 distance == bestShortDistance && 155 (rect.h - height) < bestLongDistance) { 156 bestShortDistance = distance; 157 bestLongDistance = rect.h - height; 158 bestIndex = i; 159 } 160 } 161 } 162 } 163 164 return bestIndex; 165 } 166 167 /** 168 * Removes the rectangle at the given index. Since the rectangles are in an 169 * {@link ArrayList}, removing a rectangle in the normal way is slow (it 170 * would involve shifting all elements), but since we don't care about 171 * order, this always swaps the to-be-deleted element to the last position 172 * in the array first, <b>then</b> it deletes it (which should be 173 * immediate). 174 * 175 * @param index the index in the {@link #mSpace} list to remove a rectangle 176 * from 177 */ 178 private void removeRect(int index) { 179 assert !mSpace.isEmpty(); 180 int lastIndex = mSpace.size() - 1; 181 if (index != lastIndex) { 182 // Swap before remove to make deletion faster since we don't 183 // care about order 184 Rect temp = mSpace.get(index); 185 mSpace.set(index, mSpace.get(lastIndex)); 186 mSpace.set(lastIndex, temp); 187 } 188 189 mSpace.remove(lastIndex); 190 } 191 192 /** 193 * Splits the rectangle at the given rectangle index such that it can contain 194 * a rectangle of the given width and height. */ 195 private Rect split(int index, int width, int height) { 196 Rect rect = mSpace.get(index); 197 assert rect.w >= width && rect.h >= height : rect; 198 199 Rect r = new Rect(rect); 200 r.w = width; 201 r.h = height; 202 203 // Remove all rectangles that intersect my rectangle 204 for (int i = 0; i < mSpace.size(); i++) { 205 Rect other = mSpace.get(i); 206 if (other.intersects(r)) { 207 removeRect(i); 208 i--; 209 } 210 } 211 212 213 // Split along vertical line x = rect.x + width: 214 // (rect.x,rect.y) 215 // +-------------+-------------------------+ 216 // | | | 217 // | | | 218 // | | height | 219 // | | | 220 // | | | 221 // +-------------+ B | rect.h 222 // | width | 223 // | | | 224 // | A | 225 // | | | 226 // | | 227 // +---------------------------------------+ 228 // rect.w 229 int remainingHeight = rect.h - height; 230 int remainingWidth = rect.w - width; 231 if (remainingHeight >= mMinHeight) { 232 mSpace.add(new Rect(rect.x, rect.y + height, width, remainingHeight)); 233 } 234 if (remainingWidth >= mMinWidth) { 235 mSpace.add(new Rect(rect.x + width, rect.y, remainingWidth, rect.h)); 236 } 237 238 // Split along horizontal line y = rect.y + height: 239 // +-------------+-------------------------+ 240 // | | | 241 // | | height | 242 // | | A | 243 // | | | 244 // | | | rect.h 245 // +-------------+ - - - - - - - - - - - - | 246 // | width | 247 // | | 248 // | B | 249 // | | 250 // | | 251 // +---------------------------------------+ 252 // rect.w 253 if (remainingHeight >= mMinHeight) { 254 mSpace.add(new Rect(rect.x, rect.y + height, rect.w, remainingHeight)); 255 } 256 if (remainingWidth >= mMinWidth) { 257 mSpace.add(new Rect(rect.x + width, rect.y, remainingWidth, height)); 258 } 259 260 // Remove redundant rectangles. This is not very efficient. 261 for (int i = 0; i < mSpace.size() - 1; i++) { 262 for (int j = i + 1; j < mSpace.size(); j++) { 263 Rect iRect = mSpace.get(i); 264 Rect jRect = mSpace.get(j); 265 if (jRect.contains(iRect)) { 266 removeRect(i); 267 i--; 268 break; 269 } 270 if (iRect.contains(jRect)) { 271 removeRect(j); 272 j--; 273 } 274 } 275 } 276 277 if (DEBUG) { 278 mAllocated.add(r); 279 dumpImage(); 280 } 281 282 return r; 283 } 284 285 // DEBUGGING CODE: Enable with DEBUG 286 287 private List<Rect> mAllocated; 288 private static int sLayoutId; 289 private static int sRectId; 290 private void dumpImage() { 291 if (DEBUG) { 292 int width = 100; 293 int height = 100; 294 for (Rect rect : mSpace) { 295 width = Math.max(width, rect.w); 296 height = Math.max(height, rect.h); 297 } 298 width += 10; 299 height += 10; 300 301 BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB); 302 Graphics2D g = image.createGraphics(); 303 g.setColor(Color.BLACK); 304 g.fillRect(0, 0, image.getWidth(), image.getHeight()); 305 306 Color[] colors = new Color[] { 307 Color.blue, Color.cyan, 308 Color.green, Color.magenta, Color.orange, 309 Color.pink, Color.red, Color.white, Color.yellow, Color.darkGray, 310 Color.lightGray, Color.gray, 311 }; 312 313 char allocated = 'A'; 314 for (Rect rect : mAllocated) { 315 Color color = new Color(0x9FFFFFFF, true); 316 g.setColor(color); 317 g.setBackground(color); 318 g.fillRect(rect.x, rect.y, rect.w, rect.h); 319 g.setColor(Color.WHITE); 320 g.drawRect(rect.x, rect.y, rect.w, rect.h); 321 g.drawString("" + (allocated++), 322 rect.x + rect.w / 2, rect.y + rect.h / 2); 323 } 324 325 int colorIndex = 0; 326 for (Rect rect : mSpace) { 327 Color color = colors[colorIndex]; 328 colorIndex = (colorIndex + 1) % colors.length; 329 330 color = new Color(color.getRed(), color.getGreen(), color.getBlue(), 128); 331 g.setColor(color); 332 333 g.fillRect(rect.x, rect.y, rect.w, rect.h); 334 g.setColor(Color.WHITE); 335 g.drawString(Integer.toString(colorIndex), 336 rect.x + rect.w / 2, rect.y + rect.h / 2); 337 } 338 339 340 g.dispose(); 341 342 File file = new File("/tmp/layout" + sLayoutId + "_pass" + sRectId + ".png"); 343 try { 344 ImageIO.write(image, "PNG", file); 345 System.out.println("Wrote diagnostics image " + file); 346 } catch (IOException e) { 347 e.printStackTrace(); 348 } 349 sRectId++; 350 } 351 } 352 }