public Array<Page> pack (Array<Rect> inputRects) { for (int i = 0, nn = inputRects.size; i < nn; i++) { Rect rect = inputRects.get(i); rect.width += settings.paddingX; rect.height += settings.paddingY; } if (settings.fast) { if (settings.rotation) { // Sort by longest side if rotation is enabled. sort.sort(inputRects, new Comparator<Rect>() { public int compare (Rect o1, Rect o2) { int n1 = o1.width > o1.height ? o1.width : o1.height; int n2 = o2.width > o2.height ? o2.width : o2.height; return n2 - n1; } }); } else { // Sort only by width (largest to smallest) if rotation is disabled. sort.sort(inputRects, new Comparator<Rect>() {
/** @param fully If true, the only results that pack all rects will be considered. If false, all results are considered, not * all rects may be packed. */ private Page packAtSize (boolean fully, int width, int height, Array<Rect> inputRects) { Page bestResult = null; for (int i = 0, n = methods.length; i < n; i++) { maxRects.init(width, height); Page result; if (!settings.fast) { result = maxRects.pack(inputRects, methods[i]); } else { Array<Rect> remaining = new Array(); for (int ii = 0, nn = inputRects.size; ii < nn; ii++) { Rect rect = inputRects.get(ii); if (maxRects.insert(rect, methods[i]) == null) { while (ii < nn) remaining.add(inputRects.get(ii++)); } } result = maxRects.getResult(); result.remainingRects = remaining; } if (fully && result.remainingRects.size > 0) continue; if (result.outputRects.size == 0) continue; bestResult = getBest(bestResult, result); } return bestResult; }
private int contactPointScoreNode (int x, int y, int width, int height) { int score = 0; if (x == 0 || x + width == binWidth) score += height; if (y == 0 || y + height == binHeight) score += width; Array<Rect> usedRectangles = this.usedRectangles; for (int i = 0, n = usedRectangles.size; i < n; i++) { Rect rect = usedRectangles.get(i); if (rect.x == x + width || rect.x + rect.width == x) score += commonIntervalLength(rect.y, rect.y + rect.height, y, y + height); if (rect.y == y + height || rect.y + rect.height == y) score += commonIntervalLength(rect.x, rect.x + rect.width, x, x + width); } return score; }
public Array<Page> pack (Array<Rect> inputRects) { if (!settings.silent) System.out.print("Packing"); int cellWidth = 0, cellHeight = 0; for (int i = 0, nn = inputRects.size; i < nn; i++) { Rect rect = inputRects.get(i); cellWidth = Math.max(cellWidth, rect.width); cellHeight = Math.max(cellHeight, rect.height); } cellWidth += settings.paddingX; cellHeight += settings.paddingY; inputRects.reverse(); Array<Page> pages = new Array(); while (inputRects.size > 0) { Page result = packPage(inputRects, cellWidth, cellHeight); pages.add(result); } return pages; }
/** The image won't be kept in-memory during packing if {@link Settings#limitMemory} is true. */ public void addImage (File file) { BufferedImage image; try { image = ImageIO.read(file); } catch (IOException ex) { throw new RuntimeException("Error reading image: " + file, ex); } if (image == null) throw new RuntimeException("Unable to read image: " + file); String name = file.getAbsolutePath().replace('\\', '/'); // Strip root dir off front of image path. if (rootPath != null) { if (!name.startsWith(rootPath)) throw new RuntimeException("Path '" + name + "' does not start with root: " + rootPath); name = name.substring(rootPath.length()); } // Strip extension. int dotIndex = name.lastIndexOf('.'); if (dotIndex != -1) name = name.substring(0, dotIndex); Rect rect = addImage(image, name); if (rect != null && settings.limitMemory) rect.unloadImage(file); }
/** The image will be kept in-memory during packing. * @see #addImage(File) */ public Rect addImage (BufferedImage image, String name) { Rect rect = processImage(image, name); if (rect == null) { if (!settings.silent) System.out.println("Ignoring blank input image: " + name); return null; } if (settings.alias) { String crc = hash(rect.getImage(this)); Rect existing = crcs.get(crc); if (existing != null) { if (!settings.silent) System.out.println(rect.name + " (alias of " + existing.name + ")"); existing.aliases.add(new Alias(rect)); return null; } crcs.put(crc, rect); } rects.add(rect); return rect; }
/** The image will be kept in-memory during packing. * @see #addImage(File) */ public Rect addImage (BufferedImage image, String name) { Rect rect = processImage(image, name); if (rect == null) { if(!settings.silent) System.out.println("Ignoring blank input image: " + name); return null; } if (settings.alias) { String crc = hash(rect.getImage(this)); Rect existing = crcs.get(crc); if (existing != null) { if (!settings.silent) System.out.println(rect.name + " (alias of " + existing.name + ")"); existing.aliases.add(new Alias(rect)); return null; } crcs.put(crc, rect); } rects.add(rect); return rect; }
/** @param fully If true, the only results that pack all rects will be considered. If false, all results are considered, not all * rects may be packed. */ private Page packAtSize (boolean fully, int width, int height, Array<Rect> inputRects) { Page bestResult = null; for (int i = 0, n = methods.length; i < n; i++) { maxRects.init(width, height); Page result; if (!settings.fast) { result = maxRects.pack(inputRects, methods[i]); } else { Array<Rect> remaining = new Array(); for (int ii = 0, nn = inputRects.size; ii < nn; ii++) { Rect rect = inputRects.get(ii); if (maxRects.insert(rect, methods[i]) == null) { while (ii < nn) remaining.add(inputRects.get(ii++)); } } result = maxRects.getResult(); result.remainingRects = remaining; } if (fully && result.remainingRects.size > 0) continue; if (result.outputRects.size == 0) continue; bestResult = getBest(bestResult, result); } return bestResult; }
public Array<Page> pack (Array<Rect> inputRects) { System.out.print("Packing"); int cellWidth = 0, cellHeight = 0; for (int i = 0, nn = inputRects.size; i < nn; i++) { Rect rect = inputRects.get(i); cellWidth = Math.max(cellWidth, rect.width); cellHeight = Math.max(cellHeight, rect.height); } cellWidth += settings.paddingX; cellHeight += settings.paddingY; inputRects.reverse(); Array<Page> pages = new Array(); while (inputRects.size > 0) { Page result = packPage(inputRects, cellWidth, cellHeight); pages.add(result); } return pages; }
/** The image will be kept in-memory during packing. * @see #addImage(File) */ public Rect addImage (BufferedImage image, String name) { Rect rect = processImage(image, name); if (rect == null) { System.out.println("Ignoring blank input image: " + name); return null; } if (settings.alias) { String crc = hash(rect.getImage(this)); Rect existing = crcs.get(crc); if (existing != null) { System.out.println(rect.name + " (alias of " + existing.name + ")"); existing.aliases.add(new Alias(rect)); return null; } crcs.put(crc, rect); } rects.add(rect); return rect; }
public void init (int width, int height) { binWidth = width; binHeight = height; usedRectangles.clear(); freeRectangles.clear(); Rect n = new Rect(); n.x = 0; n.y = 0; n.width = width; n.height = height; freeRectangles.add(n); }
/** Packs a single image. Order is defined externally. */ public Rect insert (Rect rect, FreeRectChoiceHeuristic method) { Rect newNode = scoreRect(rect, method); if (newNode.height == 0) return null; int numRectanglesToProcess = freeRectangles.size; for (int i = 0; i < numRectanglesToProcess; ++i) { if (splitFreeNode(freeRectangles.get(i), newNode)) { freeRectangles.removeIndex(i); --i; --numRectanglesToProcess; } } pruneFreeList(); Rect bestNode = new Rect(); bestNode.set(rect); bestNode.score1 = newNode.score1; bestNode.score2 = newNode.score2; bestNode.x = newNode.x; bestNode.y = newNode.y; bestNode.width = newNode.width; bestNode.height = newNode.height; bestNode.rotated = newNode.rotated; usedRectangles.add(bestNode); return bestNode; }
/** For each rectangle, packs each one then chooses the best and packs that. Slow! */ public Page pack (Array<Rect> rects, FreeRectChoiceHeuristic method) { rects = new Array(rects); while (rects.size > 0) { int bestRectIndex = -1; Rect bestNode = new Rect(); bestNode.score1 = Integer.MAX_VALUE; bestNode.score2 = Integer.MAX_VALUE; // Find the next rectangle that packs best. for (int i = 0; i < rects.size; i++) { Rect newNode = scoreRect(rects.get(i), method); if (newNode.score1 < bestNode.score1 || (newNode.score1 == bestNode.score1 && newNode.score2 < bestNode.score2)) { bestNode.set(rects.get(i)); bestNode.score1 = newNode.score1; bestNode.score2 = newNode.score2; bestNode.x = newNode.x; bestNode.y = newNode.y; bestNode.width = newNode.width; bestNode.height = newNode.height; bestNode.rotated = newNode.rotated; bestRectIndex = i; } } if (bestRectIndex == -1) break; placeRect(bestNode); rects.removeIndex(bestRectIndex); } Page result = getResult(); result.remainingRects = rects; return result; }
public Page getResult () { int w = 0, h = 0; for (int i = 0; i < usedRectangles.size; i++) { Rect rect = usedRectangles.get(i); w = Math.max(w, rect.x + rect.width); h = Math.max(h, rect.y + rect.height); } Page result = new Page(); result.outputRects = new Array(usedRectangles); result.occupancy = getOccupancy(); result.width = w; result.height = h; return result; }
private void placeRect (Rect node) { int numRectanglesToProcess = freeRectangles.size; for (int i = 0; i < numRectanglesToProcess; i++) { if (splitFreeNode(freeRectangles.get(i), node)) { freeRectangles.removeIndex(i); --i; --numRectanglesToProcess; } } pruneFreeList(); usedRectangles.add(node); }
private Rect scoreRect (Rect rect, FreeRectChoiceHeuristic method) { int width = rect.width; int height = rect.height; int rotatedWidth = height - settings.paddingY + settings.paddingX; int rotatedHeight = width - settings.paddingX + settings.paddingY; boolean rotate = rect.canRotate && settings.rotation; Rect newNode = null; switch (method) { case BestShortSideFit: newNode = findPositionForNewNodeBestShortSideFit(width, height, rotatedWidth, rotatedHeight, rotate); break; case BottomLeftRule: newNode = findPositionForNewNodeBottomLeft(width, height, rotatedWidth, rotatedHeight, rotate); break; case ContactPointRule: newNode = findPositionForNewNodeContactPoint(width, height, rotatedWidth, rotatedHeight, rotate); newNode.score1 = -newNode.score1; // Reverse since we are minimizing, but for contact point score bigger is better. break; case BestLongSideFit: newNode = findPositionForNewNodeBestLongSideFit(width, height, rotatedWidth, rotatedHeight, rotate); break; case BestAreaFit: newNode = findPositionForNewNodeBestAreaFit(width, height, rotatedWidth, rotatedHeight, rotate); break; } // Cannot fit the current rectangle. if (newNode.height == 0) { newNode.score1 = Integer.MAX_VALUE; newNode.score2 = Integer.MAX_VALUE; } return newNode; }
private void pruneFreeList () { /* * /// Would be nice to do something like this, to avoid a Theta(n^2) loop through each pair. /// But unfortunately it * doesn't quite cut it, since we also want to detect containment. /// Perhaps there's another way to do this faster than * Theta(n^2). * * if (freeRectangles.size > 0) clb::sort::QuickSort(&freeRectangles[0], freeRectangles.size, NodeSortCmp); * * for(int i = 0; i < freeRectangles.size-1; i++) if (freeRectangles[i].x == freeRectangles[i+1].x && freeRectangles[i].y * == freeRectangles[i+1].y && freeRectangles[i].width == freeRectangles[i+1].width && freeRectangles[i].height == * freeRectangles[i+1].height) { freeRectangles.erase(freeRectangles.begin() + i); --i; } */ // Go through each pair and remove any rectangle that is redundant. Array<Rect> freeRectangles = this.freeRectangles; for (int i = 0, n = freeRectangles.size; i < n; i++) for (int j = i + 1; j < n; ++j) { Rect rect1 = freeRectangles.get(i); Rect rect2 = freeRectangles.get(j); if (isContainedIn(rect1, rect2)) { freeRectangles.removeIndex(i); --i; --n; break; } if (isContainedIn(rect2, rect1)) { freeRectangles.removeIndex(j); --j; --n; } } }
/** * The image won't be kept in-memory during packing if {@link Settings#limitMemory} is true. * @param name will overwrite real file name (pass null to keep original name of a file). */ public Rect addImage (File file, String name) { BufferedImage image; try { image = ImageIO.read(file); } catch (IOException ex) { throw new RuntimeException("Error reading image: " + file, ex); } if (image == null) throw new RuntimeException("Unable to read image: " + file); if (name == null || name.trim().length() == 0) { name = file.getAbsolutePath().replace('\\', '/'); // Strip root dir off front of image path. if (rootPath != null) { if (!name.startsWith(rootPath)) throw new RuntimeException("Path '" + name + "' does not start with root: " + rootPath); name = name.substring(rootPath.length()); } // Strip extension. int dotIndex = name.lastIndexOf('.'); if (dotIndex != -1) name = name.substring(0, dotIndex); } Rect rect = addImage(image, name); if (rect != null && settings.limitMemory) rect.unloadImage(file); return rect; }
/** Precomputed ninepatch */ public Rect addImageNinePatch (File file, String name, int[] splits, int[] pads) { //TODO Add sanity checks. Probably do not allow "*.9" filenames. Rect rect = addImage(file, name); rect.programmaticPatch = true; rect.canRotate = false; rect.splits = splits; rect.pads = pads; return rect; }
public int compare (Rect o1, Rect o2) { return o2.width - o1.width; }
private Rect findPositionForNewNodeBestShortSideFit (int width, int height, int rotatedWidth, int rotatedHeight, boolean rotate) { Rect bestNode = new Rect(); bestNode.score1 = Integer.MAX_VALUE; for (int i = 0; i < freeRectangles.size; i++) { // Try to place the rectangle in upright (non-rotated) orientation. if (freeRectangles.get(i).width >= width && freeRectangles.get(i).height >= height) { int leftoverHoriz = Math.abs(freeRectangles.get(i).width - width); int leftoverVert = Math.abs(freeRectangles.get(i).height - height); int shortSideFit = Math.min(leftoverHoriz, leftoverVert); int longSideFit = Math.max(leftoverHoriz, leftoverVert); if (shortSideFit < bestNode.score1 || (shortSideFit == bestNode.score1 && longSideFit < bestNode.score2)) { bestNode.x = freeRectangles.get(i).x; bestNode.y = freeRectangles.get(i).y; bestNode.width = width; bestNode.height = height; bestNode.score1 = shortSideFit; bestNode.score2 = longSideFit; bestNode.rotated = false; } } if (rotate && freeRectangles.get(i).width >= rotatedWidth && freeRectangles.get(i).height >= rotatedHeight) { int flippedLeftoverHoriz = Math.abs(freeRectangles.get(i).width - rotatedWidth); int flippedLeftoverVert = Math.abs(freeRectangles.get(i).height - rotatedHeight); int flippedShortSideFit = Math.min(flippedLeftoverHoriz, flippedLeftoverVert); int flippedLongSideFit = Math.max(flippedLeftoverHoriz, flippedLeftoverVert); if (flippedShortSideFit < bestNode.score1 || (flippedShortSideFit == bestNode.score1 && flippedLongSideFit < bestNode.score2)) { bestNode.x = freeRectangles.get(i).x; bestNode.y = freeRectangles.get(i).y; bestNode.width = rotatedWidth; bestNode.height = rotatedHeight; bestNode.score1 = flippedShortSideFit; bestNode.score2 = flippedLongSideFit; bestNode.rotated = true; } } } return bestNode; }
