Re: [問題] 遞迴與堆疊-Connected Component label

看板C_and_CPP (C/C++)作者yauhh (喲)時間15年前 (2010/09/02 05:13)推噓3(3推 0噓 15→)

留言18則, 4人參與討論串2/2 (看更多)

※ 引述《MaconChou (得罪了方丈還想走)》之銘言： : 程式說明： : 此function為要在圖片上找尋是否有255的光點如有的話 : ，進行connected component label由1～n，圖片大小目前為640*480。 : 4.是否有撰寫遞迴時須注意的小地方！？ : 5.或許除了使用遞迴之外是否有比較理想的方式！？你的程式使用漣漪式的搜尋,有很多重覆的檢查,並且可能因為遞迴使Stack overflow. 既然目的是要找connected component,程式可以分二個階段,第一個階段是掃描圖檔找出全部的光點,傳回光點位置的陣列. 第二階段是在位置陣列中將鄰接項目整理成同一個component. 資料順序一定是先碰到component左上角,於是,可對每一筆資料,在後續陣列中尋找右/下/左下/右下相鄰的光點位置,都可以列為同一個component. ---------------------------- 遞迴方面: 起碼朝左/左上/上/右上的檢查可以刪掉,那些在之前都已經做過了. 左下/右下也可以刪掉,因為往下走一行的時候,遲早會檢查現在左下和右下的項目. 或者是,目前你用ConnectedComponent和FindPixels二個函數共用,有迴圈也有遞迴, 其實這樣重覆掃了同一個格子好幾次. 你可以改設計成全遞迴搜尋,則block狀態要怎麼改,則要運用一下智慧. ------------------ 另外,你的工作需求是不管多大的component都必須能找完. 而衝突的因素是,在遞迴搜尋中,遇到格點太多的component就會Stack overflow. 那麼,解決辦法可以是設定一個遞迴的中斷點,是一個遞迴總數的計數器,這是個跨遞迴instances的狀態變數. 因你的問題叫做connected component,在遞迴次數在可容許的數目之前,結束這次遞迴,必須要將接下來要做卻沒做的工作接續下去. 也就是你要從這次遞迴中,傳回一些資訊告知主控端ConnectedComponent,要開另外一些遞迴呼叫,從這次遞迴的結束點開始繼續做. 這個意思就是要把目前發生遞迴中斷的位置放在某個變數中, 可能是指定為函數的傳回值,或者是在遞迴函數的參數列多加幾個狀態變數(然而這樣的動作會增加遞迴的Stack負擔). 主控端收到遞迴要繼續的信號,就可以從遞迴中斷位置再開啟一個新的遞迴呼叫. 這樣環環相扣可以保持你的程式不會意外中斷. -- 補充: 至於推文說遞迴多可怕多濫用的... 資訊領域不欠這一類廢話. 一個東西你想用就用,不用就不要用. 能用的時候自己知道善用就好了. 不要盲目說"那個東西會怎樣"於是就永遠不用. 不要用一種很瞎的方式,不經討論就徹底說它壞. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.112.225.35 ※ 編輯: yauhh 來自: 59.112.225.35 (09/02 07:10)

推

ledia

09/02 10:34, , 1^F

09/02 10:34, 1^F

→

yauhh

09/02 10:41, , 2^F

09/02 10:41, 2^F

→

yauhh

09/02 10:41, , 3^F

09/02 10:41, 3^F