找到具有特定屬性的所有矩形區域以矩陣

給出的n * m個矩陣的1，2中的可能的值和空：我尋找所有塊B（含有之間的所有值找到具有特定屬性的所有矩形區域以矩陣

. . . . . 1 . . 
    . 1 . . . . . 1 
    . . . 2 . . . . 
    . . . . 2 . . . 
    1 . . . . . 1 . 
    . . . . . . . . 
    . . 1 . . 2 . . 
    2 . . . . . . 1

（ X0，Y0）和（X1，Y1）），其：

包含至少一個 '1'
不含 '2'
不是另一個塊的與上述特性

實施例：

blocks

的紅色，綠色和藍色區域中的所有包含一個 '1'，沒有 '2'，而不是一個較大區域的一部分。這張照片當然有3個以上的這種方塊。我想找到所有這些塊。

什麼是快速找到所有這些區域的方法？

我有一個工作蠻力的解決方案，遍歷所有可能的矩形，檢查它們是否滿足前兩個條件;然後遍歷所有找到的矩形，移除包含在另一個矩形中的所有矩形;我可以通過首先刪除連續的相同行和列來加快速度。但我相當確定有一個更快的方法。

來源

2012-06-12 HugoRune

這些塊的所有邊將位於圖的邊緣或與「2」相鄰。也許你可以做些什麼。 – robert

如果你在這裏沒有得到很好的答案，你也可以在http://cs.stackexchange.com上提問。 –

我終於找到了一個幾乎在線性時間內工作的解決方案（根據找到的區域數量有一個小的因子）。我認爲這是最快的解決方案。

通過這個答案的啓發：https://stackoverflow.com/a/7353193/145999

第一（圖片也是從那裏取），我去trought矩陣的列，創建一個新的矩陣M1測量的步驟到最後的「1」的數量和矩陣M2測量的步驟，以最後的數字「2」 M1 & M2

在任何灰色塊的想象一個「1」或「2」在上述圖象

到底我有M1和M2尋找像這樣：

enter image description here

沒有經過M1和M2在倒車時，按行：

enter image description here

我執行下面的算法：

foundAreas = new list() 

For each row y backwards: 
    potentialAreas = new List() 
    for each column x: 
     if M2[x,y]>M2[x-1,y]: 
      add to potentialAreas: 
       new Area(left=x,height=M2[x,y],hasOne=M1[x,y],hasTop=false) 
     if M2[x,y]<M2[x-1,y]: 
      for each area in potentialAreas: 
       if area.hasTop and area.hasOne<area.height: 
         add to foundAreas: 
          new Box(Area.left,y-area.height,x,y) 
      if M2[x,y]==0: delete all potentialAreas 
      else: 
       find the area in potentialAreas with height=M2[x,y] 
       or the one with the closest bigger height: set its height to M2[x,y] 
       delete all potentialAreas with a bigger height 

      for each area in potentialAreas: 
       if area.hasOne>M1[x,y]: area.hasOne=M1[x,y] 
       if M2[x,y+1]==0: area.hasTop=true

現在foundAreas包含了所需的性能所有的矩形。

來源

2012-06-14 19:24:28 HugoRune

你可以在考慮每個矩形和一個合適的解決方案之間找到一個位置。

例如，從每個1開始，您可以創建一個矩形，並逐漸向四個方向擴展其邊緣。如果（a）你不得不在所有4個方向上停下來，並且（b）你以前沒有看過這個矩形，記錄下這個矩形。

然後回溯：您需要能夠從左上角附近的1開始生成紅色矩形和綠色矩形。

雖然這種算法有一些非常糟糕的最壞情況。包含所有1的輸入值得一提。所以它需要與其他一些聰明或者對輸入的一些限制相結合。

來源

2012-06-12 18:16:23

該解決方案比OP的樸素算法差很多。 – Thomash

@Thomash：它不是嚴重的糟糕，例如它比HugoRune的任何輸入都沒有'1'的速度快得多。所以問題是，我想是否有可能確定好的情況，並有條件地使用它。 –

當然不是，有一些特定情況下你的算法更好。 – Thomash

考慮簡單的一維問題：

找到.2.1.1...12....2..1.1..2.1..2包含至少一個1並沒有2並沒有這樣的字符串的子字符串的所有子。這可以在線性時間內解決，您只需檢查兩個2之間是否存在1。

現在可以將這個算法很容易適應兩個維度問題：

對於1≤i≤j≤n總和從i到j使用下列法律的所有行：.+.=.，.+1=1，.+2=2，1+1=1，1+2=2，2+2=2並應用一個維度算法到結果行。

複雜性：O（n 2m）。

來源

2012-06-12 18:35:21 Thomash

感謝您的建議。我不確定，但我認爲這是O（n³m），因爲對於給定的i和j，它已經是O（nm）。儘管如此，仍然最有可能比蠻力更快。 – HugoRune

@HugoRune不，對於給定的i和j，它是O（m），因爲它是一維問題。你可能會說它是O（nm），因爲你必須計算從i到j的「總和」，但事實並非如此，因爲你可以重複使用i，j-1的結果。 – Thomash

找到具有特定屬性的所有矩形區域以矩陣

回答

相關問題