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;
}

Your values looks a little off. To get 3,2,3,3 I think you need 1's at 5,2 and 5,3. I'll see what I can come up with for an algorithm. — itsme86
– itsme86, Commented Jun 26, 2012 at 17:01
What did you try? When you found a block (= 0->1 or 1->0 transition) you simply check that indices match for the next line. When they match do nothing, when do not match pop the beginning of the rectangle for top left and the latest line for bottom right... — Adriano Repetti
– Adriano Repetti, Commented Jun 26, 2012 at 17:04
@itsme86 and kenny that was on purpose i want to include those two zeros in the rectange... — Peter
– Peter, Commented Jun 26, 2012 at 17:06
@RustyWeber (who probably has insufficient points to comment) asks "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?" — hatchet - done with SOverflow
– hatchet - done with SOverflow, Commented Jun 26, 2012 at 17:10

Rusty Weber · Accepted Answer · 2012-06-26 18:16:02Z

2

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.

edited Jun 26, 2012 at 18:16

answered Jun 26, 2012 at 17:06

Rusty Weber

1,5933 gold badges19 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Peter Over a year ago

sorry, (x,y,width,height) and the array is 0 based!

hatchet - done with SOverflow Over a year ago

I've made your answer a comment on the main question for you. You may want to delete this answer before you harvest a bunch of downvotes.

itsme86 · Accepted Answer · 2012-06-26 20:15:31Z

This gives you the same results you're looking for:

static void Main(string[] args)
{
    string values =
        "1100000000" +
        "1100000011" +
        "0001100011" +
        "0001100000" +
        "0001110000" +
        "0000000110" +
        "0000000110";

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

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

    List<Rectangle> rectangles = new List<Rectangle>();

    for (int x = 0; x < width; ++x)
    {
        for (int y = 0; y < height; ++y)
        {
            if (array[x, y] && !Used(rectangles, x, y))
            {
                int rHeight = 1;
                for (int rX = x + 1; rX < width && array[rX, y] && !Used(rectangles, rX, y); ++rX)
                    for (int rY = y + 1; rY < height && array[rX, rY] && !Used(rectangles, rX, rY); ++rY)
                        if (rY - y >= rHeight)
                            rHeight = rY - y + 1;

                int rWidth = 1;
                for (int rY = y + 1; rY < height && rY - y <= rHeight && array[x, rY] && !Used(rectangles, x, rY); ++rY)
                    for (int rX = x + 1; rX < width && array[rX, rY] && !Used(rectangles, rX, rY); ++rX)
                        if (rX - x >= rWidth)
                            rWidth = rX - x + 1;

                rectangles.Add(new Rectangle(x, y, rWidth, rHeight));
            }
        }
    }

    foreach (Rectangle rect in rectangles)
        Console.WriteLine(rect);
}

private static bool Used(IEnumerable<Rectangle> rectangles, int x, int y)
{
    return rectangles.Any(r => r.Contains(x, y));
}

I made an adhoc Rectangle struct since I didn't reference System.Drawing, but you can pass a System.Drawing.Point to the System.Drawing.Rectangle.Contains() and get the same results.

Also, notice that the width of your array should actually be 10 and your indexing math was wrong. You should be multiplying y by the width, not the height.

Thanks for your work, but i managed to find those bugs and i also managed to solve the problem but thanks a lot!!!

Rafael Baptista · Accepted Answer · 2012-06-26 18:01:44Z

1

It is not clear from the question if you really want rectangles that cover the 1's exactly, or if you want bounding volumes that can contain zeroes, but will cover all the 1's with a reasonably small number of rectangles.

Assuming you want rectangles to cover the 1's, and you don't need a perfect solution:

Make a temporary copy of the array.
Iterate over the temporary looking for 1's
When you hit a 1, begin a new rectagle that starts as 1x1, offset to that location ( e.g. covers just that 1 )
Expand that rectangle rightward so long as there is a 1 in the next cell
Expand that rectangle downards so long as the row below has 1's matching the width of the current rectangle.
ONce you can't expand down any more, emit that recgantle, and clear all the 1's covered by that rectangle from the temporary
continue scanning for 1's starting with the cell directly after the top right corner of the current rectangle.

This will produce a decent covering - but by no means ideal. If you need a perfect covering - e.g. the guaranteed minimum number of rectangles then it is harder.

answered Jun 26, 2012 at 18:01

Rafael Baptista

11.6k5 gold badges43 silver badges61 bronze badges

1 Comment

user555045 Over a year ago

I think if you iterate steps 4 and 5 one by one instead of maximally all in one go, you might get a slightly better result

Collectives™ on Stack Overflow

Algorithm to find rectangles

3 Answers 3

2 Comments

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related