我想洪水填充沒有堆棧和沒有遞歸

我想知道如何應用洪水填充陣列，我的數組是二維的，它包含時間新的羅馬字體類型字母邊界。邊界線包含1，內部和外部全部爲0。我想填充所有的1，而不是0在裏面。但我需要一個不需要更多內存的邏輯。因此要避免遞歸和堆棧或排隊我想洪水填充沒有堆棧和沒有遞歸

來源

2010-10-23 Swapnil

功課？....... – 2010-10-23 06:58:51

您可以添加數組_before_和_after_的示例嗎？ – atomizer 2010-10-23 07:00:54

你打算如何指定一個絕對是大綱內部（或外部）的點？（想象一個網格作爲輸入 - 哪些方塊被填充，哪些不是？）這對於斷開連接的字形（如「：」）和輪廓接觸邊界的任何字形都是必需的。 – 2010-10-23 09:17:48

我通常不爲其他人做功課，但我喜歡挑戰：

int c = -1; 
while (c < 0) 
{  
    /* Store breadcrumb trail, look to carry on */ 
    a[x][y] = c--; 
    if (!hunt(0)) 
    { 
     /* Nowhere to go, so back-track by looking for breadcrumb */ 
     a[x][y] = 1; 
     c += 2; 
     hunt(c); 
    } 
} 

bool_t hunt(int v) 
{ 
    if (a[x-1][y] == v) { x--; return TRUE; } 
    if (a[x+1][y] == v) { x++; return TRUE; } 
    if (a[x][y-1] == v) { y--; return TRUE; } 
    if (a[x][y+1] == v) { y++; return TRUE; } 
    return FALSE; 
}

注意，這不檢查擊中陣列邊緣。另外，它假定你的數組元素是例如int s，並且您只在圖像中使用值0和1。

來源

2010-10-23 09:02:09

你好，真棒。 :) – 2014-05-14 19:50:23

-1

你基本上不行。您必須將此信息存儲在某處，因爲在完成當前部分後，您必須知道還有哪些地方可以開始填充。遞歸讓你可以隱式執行它。保持自己的堆棧可以讓你明確地做到這一點，可能會節省一些。奧利查爾斯沃斯通過保持與圖片大小相同的數組來做一件可愛的事情，但它比遞歸更多地使用內存或保留一堆位置。

來源

2010-10-23 09:18:30 wnoise

我不使用單獨的數組，'a [] []'是圖像數組。 – 2010-10-23 09:21:42

@Oli Charlesworth：聰明，但爲了避免這種情況發生，你需要避免跟蹤使用的顏色。據推測，你認爲負數不能在圖像中。如果是這樣，那意味着圖像比正在使用的圖像具有更多的比特... – wnoise 2010-10-23 09:24:43

確實！但沒有指定約束，所以我採取了自由... – 2010-10-23 09:25:47

你的任務沒有多大意義。如果你有一個字體，你不想用填充填充它，而是直接渲染成填充多邊形。確定哪些部分進出字體，特別是對於襯線字體，如果不能可靠地給出好的結果。

的典型示意性算法用於填充多邊形是這樣的（沒有疊層或需要遞歸），並且它可以被應用到一個位圖，以及在一定條件下（I會得出這樣）：

對於每行（或列，無論哪種數據結構更適合），在您要跟隨的虛擬線和所有多邊形線（邊界）的每個交點處切換填充。

假設這個（可能是一個O字中間線）：

00010010001001000 
^^ ^^ 
    | | | stop 
    | | start 
    | stop 
    start

結果：

00011110001111000

這適用於位圖，以及，但只有如果你確實總是有兩個邊界的開始和停止。

來源

2010-10-23 09:27:54 Lucero

function LowMemFloodFill(pixel) 
    FillPixel(pixel) 
    Do 
    didFill = false 
    For each pixel 
     If current pixel has been filled 
     For each adjacent pixel 
      If adjacent has not been filled 
      FillPixel(adjacent) 
      didFill = true 
      End 
     End 
     End 
    End 
    While didFill 
End

問題是，您必須能夠判斷像素是否已填充（填充未使用的顏色）。此外，這將非常緩慢。

來源

2011-02-06 01:20:43 Fantius

RegularFloodFill是LowMemFloodFill因爲QuickSort是BubbleSort。 – Fantius 2011-02-06 01:20:56

我想洪水填充沒有堆棧和沒有遞歸

回答

相關問題