title: Algorithm to find rectangles
body: <p>I have the following code:</p>
  
  <pre><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 &lt; width; x++)
  {
      for (int y = 0; y &lt; height; y++)
      {
          array1[x, y] = (values[x + y * width] == '1');
      }
  }
  </code></pre>
  
  <p>im looking for a algorithm that would extract Ranges where we have a 1.</p>
  
  <p>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!</p>
  
  <p>But i have no idea how to do this any one got any pointers?</p>
  
  <p>After reading Rusty Weber answer i came up with the following:</p>
  
  <pre><code>private static List&lt;Rectangle&gt; GetRectangles(bool[,] array)
  {
      List&lt;Rectangle&gt; rectangles = new List&lt;Rectangle&gt;();
      for (int x = 0; x &lt; array.GetLength(0); x++)
      {
          for (int y = 0; y &lt; 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&lt;Point&gt; visitedLocations = new HashSet&lt;Point&gt;();
      Stack&lt;Point&gt; pointsToGo = new Stack&lt;Point&gt;();
      Point location;
      pointsToGo.Push(startLocation);
      while (pointsToGo.Count &gt; 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 &gt; maxX)
              maxX = location2.X;
          if (location2.X &lt; minX)
              minX = location2.X;
          if (location2.Y &gt; maxY)
              maxY = location2.Y;
          if (location2.Y &lt; minY)
              minY = location2.Y;
      }
  
      return new Rectangle(minX, minY, maxX - minX + 1, maxY - minY + 1);
  }
  
  public static bool IsBetween&lt;T&gt;(this T item, T start, T end)
  {
      return Comparer&lt;T&gt;.Default.Compare(item, start) &gt;= 0
          &amp;&amp; Comparer&lt;T&gt;.Default.Compare(item, end) &lt;= 0;
  }
  </code></pre>