- Start with the bounding box of the rectangle.
For each corner, move it clockwise until there is a black square.
public class Test {
String[][] squares = {
{
".........",
".X11111X.",
".1111111.",
".1111111.",
".X11111X.",
".........",
".........",
".........",
".........",},
{
".........",
"....X....",
"...111...",
"..X111X..",
"...111...",
"....X....",
".........",
".........",
".........",},
{
".........",
"..X11....",
"..11111X.",
"..111111.",
".1111111.",
".111111..",
".X11111..",
"....11X..",
".........",},
{
".........",
"....11X..",
"X111111..",
".111111..",
".1111111.",
"..111111.",
"..11111X.",
"..X11....",
".........",}};
private static final int WHITE = 0;
private static final int BLACK = 1;
class Point {
private final int x;
private final int y;
public Point(Point p) {
this.x = p.x;
this.y = p.y;
}
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "{" + x + "," + y + '}';
}
// What colour is there?
public int colour(int[][] bmp) {
// Make everything off-bmp black.
if (x < 0 || y < 0 || y >= bmp.length || x >= bmp[y].length) {
return BLACK;
}
return bmp[y][x];
}
private Point step(Point d) {
return new Point(x + d.x, y + d.y);
}
}
class Rectangle {
private final Point[] corners = new Point[4];
public Rectangle(Point[] corners) {
// Points are immutable but corners are not.
System.arraycopy(corners, 0, this.corners, 0, corners.length);
}
public Rectangle(Rectangle r) {
this(r.corners());
}
public Rectangle(Point a, Point b, Point c, Point d) {
corners[0] = a;
corners[1] = b;
corners[2] = c;
corners[3] = d;
}
private Rectangle(Point tl, Point br) {
this(tl, new Point(br.x, tl.y), br, new Point(tl.x, br.y));
}
public Point[] corners() {
return Arrays.copyOf(corners, corners.length);
}
@Override
public String toString() {
return Arrays.toString(corners);
}
}
private Rectangle getBoundingBox(int[][] bmp) {
int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE, maxX = 0, maxY = 0;
for (int r = 0; r < bmp.length; r++) {
for (int c = 0; c < bmp[r].length; c++) {
if (bmp[r][c] != WHITE) {
if (minX > c) {
minX = c;
}
if (minY > r) {
minY = r;
}
if (maxX < c) {
maxX = c;
}
if (maxY < r) {
maxY = r;
}
}
}
}
return new Rectangle(new Point(minX, minY), new Point(maxX, maxY));
}
Point[] clockwise = new Point[]{
new Point(1, 0),
new Point(0, 1),
new Point(-1, 0),
new Point(0, -1)};
private void test(int[][] bmp) {
// Find the bounding box.
Rectangle bBox = getBoundingBox(bmp);
System.out.println("bbox = " + bBox);
Point[] corners = bBox.corners();
// Move each corner clockwise until it is black.
for (int p = 0; p < corners.length; p++) {
while (corners[p].colour(bmp) == WHITE) {
corners[p] = corners[p].step(clockwise[p]);
}
}
System.out.println("rect = " + new Rectangle(corners));
}
private void test(String[] square) {
// Build the int[][].
// . -> White
// X/1 -> Black
int[][] bmp = new int[square.length][];
for (int r = 0; r < square.length; r++) {
bmp[r] = new int[square[r].length()];
for (int c = 0; c < bmp[r].length; c++) {
switch (square[r].charAt(c)) {
case '.':
bmp[r][c] = WHITE;
break;
case 'X':
case '1':
bmp[r][c] = BLACK;
break;
}
}
}
test(bmp);
}
public void test() {
for (String[] square : squares) {
test(square);
}
}
public static void main(String args[]) {
try {
new Test().test();
} catch (Throwable t) {
t.printStackTrace(System.err);
}
}
}
prints
bbox = [{1,1}, {7,1}, {7,4}, {1,4}]
rect = [{1,1}, {7,1}, {7,4}, {1,4}]
bbox = [{2,1}, {6,1}, {6,5}, {2,5}]
rect = [{4,1}, {6,3}, {4,5}, {2,3}]
bbox = [{1,1}, {7,1}, {7,7}, {1,7}]
rect = [{2,1}, {7,2}, {6,7}, {1,6}]
bbox = [{0,1}, {7,1}, {7,7}, {0,7}]
rect = [{4,1}, {7,4}, {4,7}, {0,2}]
Could be improved by looking for a run of black and choosing the middle of the run.
