@Test public final void runTestCase() throws IOException { BufferedImage imgIn = ImageIO.read(new File("test.png")); short[][] matrix = new short[imgIn.getWidth()][imgIn.getHeight()]; for (int x = 0; x < imgIn.getWidth(); x++) { for (int y = 0; y < imgIn.getHeight(); y++) { matrix[x][y] = (short) (imgIn.getRGB(x,y) != -1 ? 1 : 0); } } Rectangle rect = MaxRectFinder.maximalRectangle(matrix); System.out.println(rect); }
public static Rectangle maximalRectangle(short[][] matrix) { short lenX = (short) matrix.length; short lenY = (short) matrix[0].length; short previous; for (short x = 0; x < lenX; x++) { previous = matrix[x][0]; for (short y = 1; y < lenY; y++) { if (matrix[x][y] == 1) { previous++; matrix[x][y] = previous; } else { previous = 0; } } } LinkedList<short[]> stack = new LinkedList<short[]>(); short[] info; int size = 0; Rectangle result = null; short nHeight; for (short y = 0; y < lenY; y++) { short height = 0; for (short x = 0; x < lenX; x++) { nHeight = matrix[x][y]; if (height < nHeight) { while (height < nHeight) { height++; stack.push(new short[]{x, height}); } } else if (height > nHeight) { height = nHeight; do { info = stack.pop(); if (info[1] > height) { int sizeTmp = getSize((short) (x - info[0]), info[1]); if (sizeTmp > size) { result = new Rectangle(info[0], y - info[1] + 1, x - info[0], info[1]); size = sizeTmp; } } } while (!stack.isEmpty() && info[1] > height); if (!(info[1] > height)) { stack.push(info); } } } while (!stack.isEmpty()) { info = stack.pop(); int sizeTmp = getSize((short) (lenX - info[0]), info[1]); if (sizeTmp > size) { result = new Rectangle(info[0], y - info[1] + 1, lenX - info[0], info[1]); size = sizeTmp; } } } return result; }
MaxRectFinder { public static Rectangle maximalRectangle(short[][] matrix) { short lenX = (short) matrix.length; short lenY = (short) matrix[0].length; short previous; for (short x = 0; x < lenX; x++) { previous = matrix[x][0]; for (short y = 1; y < lenY; y++) { if (matrix[x][y] == 1) { previous++; matrix[x][y] = previous; } else { previous = 0; } } } LinkedList<short[]> stack = new LinkedList<short[]>(); short[] info; int size = 0; Rectangle result = null; short nHeight; for (short y = 0; y < lenY; y++) { short height = 0; for (short x = 0; x < lenX; x++) { nHeight = matrix[x][y]; if (height < nHeight) { while (height < nHeight) { height++; stack.push(new short[]{x, height}); } } else if (height > nHeight) { height = nHeight; do { info = stack.pop(); if (info[1] > height) { int sizeTmp = getSize((short) (x - info[0]), info[1]); if (sizeTmp > size) { result = new Rectangle(info[0], y - info[1] + 1, x - info[0], info[1]); size = sizeTmp; } } } while (!stack.isEmpty() && info[1] > height); if (!(info[1] > height)) { stack.push(info); } } } while (!stack.isEmpty()) { info = stack.pop(); int sizeTmp = getSize((short) (lenX - info[0]), info[1]); if (sizeTmp > size) { result = new Rectangle(info[0], y - info[1] + 1, lenX - info[0], info[1]); size = sizeTmp; } } } return result; } }
MaxRectFinder { public static Rectangle maximalRectangle(short[][] matrix) { short lenX = (short) matrix.length; short lenY = (short) matrix[0].length; short previous; for (short x = 0; x < lenX; x++) { previous = matrix[x][0]; for (short y = 1; y < lenY; y++) { if (matrix[x][y] == 1) { previous++; matrix[x][y] = previous; } else { previous = 0; } } } LinkedList<short[]> stack = new LinkedList<short[]>(); short[] info; int size = 0; Rectangle result = null; short nHeight; for (short y = 0; y < lenY; y++) { short height = 0; for (short x = 0; x < lenX; x++) { nHeight = matrix[x][y]; if (height < nHeight) { while (height < nHeight) { height++; stack.push(new short[]{x, height}); } } else if (height > nHeight) { height = nHeight; do { info = stack.pop(); if (info[1] > height) { int sizeTmp = getSize((short) (x - info[0]), info[1]); if (sizeTmp > size) { result = new Rectangle(info[0], y - info[1] + 1, x - info[0], info[1]); size = sizeTmp; } } } while (!stack.isEmpty() && info[1] > height); if (!(info[1] > height)) { stack.push(info); } } } while (!stack.isEmpty()) { info = stack.pop(); int sizeTmp = getSize((short) (lenX - info[0]), info[1]); if (sizeTmp > size) { result = new Rectangle(info[0], y - info[1] + 1, lenX - info[0], info[1]); size = sizeTmp; } } } return result; }  }
MaxRectFinder { public static Rectangle maximalRectangle(short[][] matrix) { short lenX = (short) matrix.length; short lenY = (short) matrix[0].length; short previous; for (short x = 0; x < lenX; x++) { previous = matrix[x][0]; for (short y = 1; y < lenY; y++) { if (matrix[x][y] == 1) { previous++; matrix[x][y] = previous; } else { previous = 0; } } } LinkedList<short[]> stack = new LinkedList<short[]>(); short[] info; int size = 0; Rectangle result = null; short nHeight; for (short y = 0; y < lenY; y++) { short height = 0; for (short x = 0; x < lenX; x++) { nHeight = matrix[x][y]; if (height < nHeight) { while (height < nHeight) { height++; stack.push(new short[]{x, height}); } } else if (height > nHeight) { height = nHeight; do { info = stack.pop(); if (info[1] > height) { int sizeTmp = getSize((short) (x - info[0]), info[1]); if (sizeTmp > size) { result = new Rectangle(info[0], y - info[1] + 1, x - info[0], info[1]); size = sizeTmp; } } } while (!stack.isEmpty() && info[1] > height); if (!(info[1] > height)) { stack.push(info); } } } while (!stack.isEmpty()) { info = stack.pop(); int sizeTmp = getSize((short) (lenX - info[0]), info[1]); if (sizeTmp > size) { result = new Rectangle(info[0], y - info[1] + 1, lenX - info[0], info[1]); size = sizeTmp; } } } return result; }  static Rectangle maximalRectangle(short[][] matrix); }
MaxRectFinder { public static Rectangle maximalRectangle(short[][] matrix) { short lenX = (short) matrix.length; short lenY = (short) matrix[0].length; short previous; for (short x = 0; x < lenX; x++) { previous = matrix[x][0]; for (short y = 1; y < lenY; y++) { if (matrix[x][y] == 1) { previous++; matrix[x][y] = previous; } else { previous = 0; } } } LinkedList<short[]> stack = new LinkedList<short[]>(); short[] info; int size = 0; Rectangle result = null; short nHeight; for (short y = 0; y < lenY; y++) { short height = 0; for (short x = 0; x < lenX; x++) { nHeight = matrix[x][y]; if (height < nHeight) { while (height < nHeight) { height++; stack.push(new short[]{x, height}); } } else if (height > nHeight) { height = nHeight; do { info = stack.pop(); if (info[1] > height) { int sizeTmp = getSize((short) (x - info[0]), info[1]); if (sizeTmp > size) { result = new Rectangle(info[0], y - info[1] + 1, x - info[0], info[1]); size = sizeTmp; } } } while (!stack.isEmpty() && info[1] > height); if (!(info[1] > height)) { stack.push(info); } } } while (!stack.isEmpty()) { info = stack.pop(); int sizeTmp = getSize((short) (lenX - info[0]), info[1]); if (sizeTmp > size) { result = new Rectangle(info[0], y - info[1] + 1, lenX - info[0], info[1]); size = sizeTmp; } } } return result; }  static Rectangle maximalRectangle(short[][] matrix);  }