Algorithm to find rectangles

Question

I have the following code:

int width = 10;
int height = 7;
bool[,] array1 = new bool[width, height];


string values = 
    "1100000000" +
    "1100000011" +
    "0001100011" +
    "0001100000" +
    "0001110000" +
    "0000000110" +
    "0000000110";

for (int x = 0; x < width; x++)
{
    for (int y = 0; y < height; y++)
    {
        array1[x, y] = (values[x + y * width] == '1');
    }
}

im looking for a algorithm that would extract Ranges where we have a 1.

so from this data we would get rectangles (0,0,2,2), (8,1,2,2), (3,2,3,3), (7,5,2,2) the order of the rectangles do not matter!

But i have no idea how to do this any one got any pointers?

After reading Rusty Weber answer i came up with the following:

private static List<Rectangle> GetRectangles(bool[,] array)
{
    List<Rectangle> rectangles = new List<Rectangle>();
    for (int x = 0; x < array.GetLength(0); x++)
    {
        for (int y = 0; y < array.GetLength(1); y++)
        {
            if (array[x, y])
            {
                rectangles.Add(GetRectangle(array, new Point(x, y)));
            }
        }
    }
    return rectangles;
}



static Rectangle GetRectangle(bool[,] array, Point startLocation)
{
    int maxX = int.MinValue;
    int minX = int.MaxValue;
    int maxY = int.MinValue;
    int minY = int.MaxValue;
    HashSet<Point> visitedLocations = new HashSet<Point>();
    Stack<Point> pointsToGo = new Stack<Point>();
    Point location;
    pointsToGo.Push(startLocation);
    while (pointsToGo.Count > 0)
    {
        location = pointsToGo.Pop();

        if (!location.X.IsBetween(0, array.GetLength(0) - 1))
            continue;
        if (!location.Y.IsBetween(0, array.GetLength(1) - 1))
            continue;
        if (!array[location.X, location.Y])
            continue;
        if (visitedLocations.Contains(location))
            continue;
        visitedLocations.Add(location);

        pointsToGo.Push(new Point(location.X + 1, location.Y));
        pointsToGo.Push(new Point(location.X, location.Y + 1));
        pointsToGo.Push(new Point(location.X - 1, location.Y));
        pointsToGo.Push(new Point(location.X, location.Y - 1));
    }

    foreach (Point location2 in visitedLocations)
    {
        array[location2.X, location2.Y] = false;
        if (location2.X > maxX)
            maxX = location2.X;
        if (location2.X < minX)
            minX = location2.X;
        if (location2.Y > maxY)
            maxY = location2.Y;
        if (location2.Y < minY)
            minY = location2.Y;
    }

    return new Rectangle(minX, minY, maxX - minX + 1, maxY - minY + 1);
}

public static bool IsBetween<T>(this T item, T start, T end)
{
    return Comparer<T>.Default.Compare(item, start) >= 0
        && Comparer<T>.Default.Compare(item, end) <= 0;
}

Answer 1

COMMENT :: It might help me to answer your question if you have better defined coordinates. (0,0,2,2) isn't exactly Cartesian and it may need some explaining. Is this the top left corner followed by the widths?

Ok. The easiest to program way, in my opinion at least, to extract all possible rectangles from the graph is to have a recursively defined method that searches in a specific direction for the symmetric rectangle pattern. This however could end up being really slow so I hope that speed isn't a constraint for you. Looking at the style of code, I would say that this is a school assignment for either recursion or dynamic programming.

something along the lines of the following pseudocode

`

for i in width  
{  
for j in height  
{  
if(point[i,j] == 1)  
{  
       potentials = searh_in_direction(i,j,graph,width,height,RIGHT,[[i,j]] )  
     listOfAllRects.append(potentials)  
}  
}  
}
list_of_rectangle searh_in_direction(i,j,graph,width,height,direction, listofpoints )  
{  
  nextdirection = direction.nextdirection; //Right -> down -> left-> up 


  //DEVELOP METHOD FOR RECURSION HERE THAT RETURNS ALL SETS OF 4 POINTS THAT
  for every point in the direction of travel
  if the point is the origional point and we have 4 points including the point we are looking at, we have a rectangle and we need to return
  if point on direction of travel is a one travel on the next direction
  posiblerects.append(searh_in_direction(i,j,graph,width,height,nextdirection , listofpoints.append(currentpoint)))

//after all points in direction have bee searched
return posiblerects.
}  

`

I know that this code could be very confusing but that is the gist of what you need as a recursive element. I will also note that I can already see several bugs in this code but I have run out of the 15 minutes that I said that I was going to spend on this post so you might have to pick them out yourself.