執行paintFill函數

我有幾個關於從McDowell執行paintFill函數（類似於圖像編輯程序）的代碼的問題。執行paintFill函數

1-爲什麼我們使用排序屏幕[y] [x]而不是屏幕[x] [y]？作者說這是圖形問題的特徵，但爲什麼？

2-作者將此方法與深度優先方法進行比較，並表示它可能會很快溢出堆棧。另一種選擇是實施廣度優先搜索的變體。它不是已經是BFS的方法嗎？由於對於每個像素，我們在向外看像素之前先着色相鄰像素？如果不是，那麼bfs方法的想法是什麼？爲什麼它不會溢出？

enum Color{ 
    Black, White, Red, Yellow, Green 
    } 

    boolean paintFill(Color[][] screen, int x, int y, Color ocolor, Color ncolor){ 
    if (x < 0 || x >= screen[0].length|| 
      y < 0 || y >= screen.length){ 
     return false; 
    } 

    if (screen[y][x] == ocolor){ 
     screen[y][x] = ncolor; 
     paintFill(screen, x-1, y, ocolor, ncolor); 
     paintFill(screen, x+1, y, ocolor, ncolor); 
     paintFill(screen, x, y-1, ocolor, ncolor); 
     paintFill(screen, x, y+1, ocolor, ncolor); 
    } 
    return true; 
    } 

    boolean paintFill(Color[][] screen, int x, int y, Color ncolor){ 
    if (screen[y][x] == ncolor){ 
     return false; 
    } 
    return paintFill(screen, x, y, screen[y][x], ncolor); 
    }

來源

2015-02-04 giulio

1-爲什麼我們使用排序屏幕[Y] [X]，而不是畫面[X] [Y]？作者說這是圖形問題的特徵，但爲什麼？

我猜測y表示在垂直軸上的位置。在這種情況下，您不能使用screen[x][y]，因爲第一個維度與縱軸相關。因此，它必須與y索引。

2-筆者比較了這種方式，以深度優先的做法，並表示它可能很快使棧溢出。另一種選擇是實施廣度優先搜索的變體。它不是已經是BFS的方法嗎？由於對於每個像素，我們在向外看像素之前先着色相鄰像素？如果不是，那麼bfs方法的想法是什麼？爲什麼它不會溢出？

這不是BFS因爲你的電話是遞歸的深度優先調用。這意味着，你不色的所有相鄰像素，顏色一（左一個在你的情況下），通過遞歸調用：

paintFill(screen, x-1, y, ocolor, ncolor);

然後你的顏色這一項的左鄰（由於同種遞歸調用），然後是那個左邊的鄰居等，直到你到達沒有左邊鄰居的屏幕邊緣的一個像素。然後你原路返回至最後像素您着色，做從那裏第二遞歸調用：

paintFill(screen, x+1, y, ocolor, ncolor);

着色右相鄰（這已經因爲你從右邊傳來可能已經被着色，所以這將返回快這個案例）。這繼續下去，直到所有東西都被着色。

正如您所看到的，它是深度優先，因爲您沿某個方向移動，直到出於某種原因您不能再朝那個方向移動。首先，您必須使用FIFO隊列：在隊列中插入一個像素位置併爲其着色。然後在隊列中存在元素的情況下重複：從隊列中移除第一個元素，爲其鄰居着色並在隊列中插入其鄰居。

這樣可以避免遞歸調用，並且會產生類似於如果在地板上放下油漆罐時發生的情況的效果：顏色將從一個點向外均勻擴展。

深度優先將看起來類似於如果您嘗試在限制條件下對一張紙進行着色時發生的情況，那麼您應該只在不這樣做時更改您的手移動的方向會導致您打破紙張邊界。目前的算法是DFS。

來源

2015-02-04 22:23:01 IVlad

圖像格式和屏幕設備使用水平掃描線，所以垂直陣列的水平線。所以[y][x]。請參閱模擬電視信號，BMP格式。
DFS的可視化將是雷擊，而BFS將在培養皿中生長細菌菌落。由於任何搜索都不是定向的，因此DFS具有許多部分候選路徑，它們沿任何方向捲曲，因此更長。 BFS更自然。就像你會保持生長的外輪廓一樣。另一種觀點認爲：BFS受外部邊界的限制，而DFS始於無限制的捲曲路徑。這些路徑更長，可能指數更低效。最大路徑長度B * W將是遞歸深度。在C中可以定義一個小堆棧，但堆棧溢出看起來有點過頭了。

來源

2015-02-04 22:29:09

執行paintFill函數

回答

相關問題