算法找到矩形

Question

我有以下代碼：

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

即時尋找一個算法，將提取，我們有一個1

所以從這個數據中我們會得到矩形 範圍（0 ，0,2,2）， （8,1,2,2）， （3,2,3,3）， （7,5,2,2） 矩形的順序並不重要！

但我不知道如何做到這一點任何人有任何指針？

閱讀生鏽韋伯的回答後，我想出了以下內容：

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 ::這可能會幫助我回答你的問題，如果你有更好的座標來定義。 （0,0,2,2）並不完全是笛卡兒，它可能需要一些解釋。這是左上角後跟寬度嗎？

好的。至少在我看來，最簡單的編程方式是從圖中提取所有可能的矩形，就是有一個遞歸定義的方法，在特定的方向搜索對稱矩形模式。然而，這可能最終會變得非常緩慢，所以我希望速度不是對你的限制。看看代碼的風格，我會說這是一個遞歸或動態編程的學校作業。

東西沿着以下僞

`

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

`

我知道這個代碼可以是非常混亂的線，但是這是你所需要的遞歸要點元件。 我也會注意到，我已經可以在這段代碼中看到一些錯誤，但是我已經用完了15分鐘，我說我將花費在這篇文章上，所以你可能必須自己挑選它們。

Answer 2

從問題中不清楚您是否真的想要覆蓋1的矩形，或者如果您想要包含零的邊界體積，但會覆蓋所有1，並且只包含相當少量的矩形。

假設你想要矩形覆蓋1的，而你並不需要一個完美的解決方案：

1. 使數組的臨時副本。
2. 遍歷臨時找1的
3. 當你打一個1，開始一個新的rectagle啓動爲1x1的，偏移到該位置（如僅涉及：1）
4. 展開矩形向右只要有是下一個單元格中的1
5. 只要下面的行的1與當前矩形的寬度 相匹配，就將該矩形向下展開。
6. 一旦你不能向下展開更多的，發射出recgantle，並清除所有從臨時
7. 由矩形覆蓋1的繼續掃描1的開始與細胞當前矩形的右上角後直接。

這將產生一個像樣的覆蓋 - 但絕不是理想的。如果你需要一個完美的覆蓋物 - 例如保證最小數量的矩形然後它是困難的。

Answer 3

這給了你，你正在尋找相同的結果：

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

我做了即席矩形結構，因爲我沒有引用System.Drawing中，但你可以通過一個System.Drawing.Point來System.Drawing.Rectangle.Contains（）並獲得相同的結果。

此外，請注意您的陣列的寬度實際上應該是10，你的索引數學是錯誤的。你應該乘以y的寬度，而不是高度。