الگوریتم Flood Filll - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

وبـــلاگ هــفت خــط کــد


آموزش های برنامه نویسی
۱۲۰ نفر آنلاین
۲ عضو و ۱۱۸ مهمان در سایت حاضرند

الگوریتم Flood Filll

+2 امتیاز
401 بازدید

من  یک گرید 2 بعدی دارم و می خوام  قسمت های بسته را رنگ کنم . یک راه استفاده از الگوریتم FloodFill هستش ولی من متوجه نشدم چطور باید این کارو انجام داد .

ممنون میشم کمک کنید 

 

گراف, گرید, dfs, flood fill, bfs, الگوریتم

سوال شده آذر 16, 1393  بوسیله ی PSPCoder (امتیاز 1,411)   2 12 47

3 پاسخ

+1 امتیاز
الگوریتم flood fill  در 2 حالت باینری و gray scale عمل می کنه  تابع flood fill ویندوز از نوع باینری بوده و اعصای جادویی فتوشاپ از نوع grayscale .

عملکرد این الگوریتم به صورت بازگشتی هستش که روش هایی هم وجود داره که از حالت بازگشتی درش بیارین یعنی خودتون شبیه سازی کنید که در این حالت می تونید از queue یا stack استفاده کنید که من queue رو پیشنهاد می دم چون زمان اجرای اون در تصاویر با پیچیدگی بالا کمتره. در این روش صفحه را پیمایش می کنند تا به اولین نقطه غیر صفر (در تصاویر خاکستری هم اگر نقطه مورد نظر در بازه باشه یا اختلاف شدت نور کمتر از آستانه در نظر گرفته شده باشه )برسه سپس نقطه را ثبت می کنه و تمام همسایه ها شو در queue قرار میده سپس یه مقدار دیگه از صف بر میداره و همین کارو تا آخر انجام میده به طوریکه صف خالی شه.

برای انتخاب همسایه ها هم می تونید از 4 یا 8 همسایگی استفاده  کنید .

زمانیکه مایل نیستید 2 تا Blob از طریق یه خط اریب به هم  متصل باشند  در این موارد بایستی از همسایگی 4 استفاده کنید.

در شکل بالا اگر مرکز یا یک نقطه در داخل شکل مورد نظر را داشته باشید floodfill روی پیکسل ها مجاور با مقدار 255 بایستی عمل کنه و پارامتر همسایگی هم فرقی نداره که چی باشه.
پاسخ داده شده آذر 18, 1393 بوسیله ی مصطفی ساتکی (امتیاز 16,777)   17 25 66
+1 امتیاز

برای نوشتن FloodFill کافی هست که  الگوریتم DFS  رو انجام بدید و زمانی که از یک پیکسل عبور می کنید رنگ اون پیکسل رو عوض کنید . و در صورتی که به پیکسلی که قبلا رنگ آمیزی شده بود یا رنگ غیر مشابه داشت رسیدید DFS رو متوقف کنید .

شبه کد :

int xdir=[0,0,1,-1]
int ydir=[1,-1,0,0]
FloodFill (pixel, req-color, replace-color):
    //agar be rang motefavet residim ya az ghabl rang shode bood
    If pixel.color != req-color Or  pixel.colored
        return.
     pixel.color=replace-color
     pixel.colored=true
     for i=0 to 4
          FloodFill  (Pixel(pixel.x+xdir[i],pixel.y+ydir[i],req-color, replace-color).

البته میتونید ازروش غیر بازگشتی الگوریتم dfs هم با استفاده از صف استفاده کنید که داخل پاسخ بالا و همین طور این لینک توضیح داده شده .

برای شکل بالا هم یا می تونید یک بار FloodFill رو از وسط آرایه با رنگ  سیاه انجام بدید

یا یک آرایه Colors رو بترتیب رنگ سفید و سیاه و سیاه بزارید و از گوشه بالا یک بار FloodFill رو به ازای همه ی پیکسل ها و با رنگ های داخل آرایه  انجام بدید.

پاسخ داده شده آذر 22, 1393 بوسیله ی BlueBlade (امتیاز 15,712)   13 16 85
0 امتیاز

اگه قرار بود در سطح پایین این مسئلرو حل کنیم میتونستیم

اول مختصات نقاط سیاه رو بزاریم توی یه آرایه بعد ماگزیموم و مینیموم  طول و عرضش رو بحسابیم بعدشم ناحیرو کاهش میدیم

حالا با قضیه جردن و خم ها و روش مثلثی در پیدا کردن اینکه یک نقطه درون خم هست یا نه اونجاهایی که درون خم هست رو سیاه کنیم

!!!!

Fire360Boy

Always & Everywhere

پاسخ داده شده آذر 22, 1393 بوسیله ی Fire360Boy (امتیاز 3,342)   2 16 42
البته روش مثلثی همیشه جواب نمیده ولی روش های دیگه زیاده
...