الگوریتم پرکردن طوفانی
این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |
الگوریتم پرکردن طوفانی، که به نام دانه پر هم ترجمه شده، الگوریتم برای تعیین منطقهٔ متّصل به یک گره داده شده در یک آرایه چند بعدی است. این الگوریتم در برنامه‌هایی مانند نقاشی برای پر کردن نقاط بیت مپ و همچنین در بازی‌های مانند مین سوپر و ... برای پیده کردن قطعات کاربرد دارد. هنگامی که در یک تصویر برای پر کردن منطقه خاص محدود با یک رنگ استفاده شود، آن را نیز به عنوان مرز شناخته شده را پر می‌کند.
الگوریتم پرکردن طوفانی ویرایش
الگوریتم پر کردن طوفانی سه پارامتر می‌گیرد : یک گره شروع، یک رنگ هدف، و رنگ‌های جایگزین. این الگوریتم به نظر می‌رسد که برای تمام گره‌ها در آرایه از گره شروع، شروع به پیمایش مسیر با رنگ مورد نظر می‌کند و با رنگ دومی جایگرین می‌کند. الگوریتم پر کردن طوفانی الگوریتم را می‌توان با استفاده از ساختارهای یک صف یا پشته پیاده‌سازی کرد. یکی به‌طور ضمنی مبتنی بر پشته(بازگشتی(برای یک آرایه دو بعدیبه کار میرود به شرح زیر : و<alighn=right Flood-fill (node، target-color، replacement-color):
1. If the color of node is not equal to target-color, return. 2. Set the color of node to replacement-color. 3. Perform Flood-fill (one step to the west of node, target-color, replacement-color). Perform Flood-fill (one step to the east of node, target-color, replacement-color). Perform Flood-fill (one step to the north of node, target-color, replacement-color). Perform Flood-fill (one step to the south of node, target-color, replacement-color). 4. Return.
/> روش دوم برای پیاده سازی اگر چه روش بالا به راحتی قابل درک است ولی در بعضی از زبانها به علت کمبود فضای پشته قابل پیاه‌سازی نیست (مثلاً جاوا اپلتها).
پیاده‌سازی صف صراحتاً مبتنی بر این است که در شبه کد زیر نشان داده شده‌است. این اجرا بسیار مؤثر است، اما می‌تواند به سرعت کد، یک پشته نباشد، ولی از آن آسانتر است.به شکل زیر :
Flood-fill (node، target-color، replacement-color):
1. Set Q to the empty queue. 2. If the color of node is not equal to target-color, return. 3. Add node to the end of Q. 4. While Q is not empty: 5. Set n equal to the first element of Q 6. If the color of n is equal to target-color, set the color of n to replacement-color. 7. Remove first element from Q 8. If the color of the node to the west of n is target-color: 9. Add that node to the end of Q
۱۰. If the color of the node to the east of n is target-color: ۱۱. Add that node to the end of Q ۱۲. If the color of the node to the north of n is target-color: ۱۳. Add that node to the end of Q ۱۴. If the color of the node to the south of n is target-color: ۱۵. Add that node to the end of Q ۱۶. Return. بیشتر پیاده‌سازی با استفاده از یک حلقه در جهت‌های شرق و غرب به عنوان بهینه سازی برای جلوگیری از سربار از پشته یا مدیریت صف استفاده مشود :
Flood-fill (node، target-color، replacement-color):
1. Set Q to the empty queue. 2. If the color of node is not equal to target-color, return. 3. Add node to Q. 4. For each element n of Q: 5. If the color of n is equal to target-color: 6. Set w and e equal to n. 7. Move w to the west until the color of the node to the west of w no longer matches target-color. 8. Move e to the east until the color of the node to the east of e no longer matches target-color. 9. Set the color of nodes between w and e to replacement-color.
۱۰. For each node n between w and e: ۱۱. If the color of the node to the north of n is target-color، add that node to Q. ۱۲. If the color of the node to the south of n is target-color، add that node to Q. ۱۳. Continue looping until Q is exhausted. ۱۴. Return. در این الگوریتم جهت تطابق لبه‌ها می‌توان از یک آرایه برای ذخیره لبه‌ها استفاده کرد که در پیمایش هنگام رسیدن به آن حد آستانه جهت ایجاد تفاوت لبه‌ها استفاده کرد. با استفاده از این آرایه‌های اضافی به عنوان یک کانال آلفا اجازه می‌دهد تا لبه‌های منطقه تا حدودی پر شده را به مخلوط یکنواخت با منطقه پر نشده در آورد.
روش حافظه ثابت(روش پرکردن دست راست) در این روش حافظه‌ای برای ذخیره مرزهای پیکسل در نظر گرفته نمی‌شود بلکه در پیمایش، هر چهار پیکسل اطراف پیکسل جاری پیمایش می‌شود . موقعیت پیکسلها می‌تواند به یکی از اشکال زیر باشد:
هر چهار پیکسل مرز هستند پر شده‌است. سه تا از پیکسلها مرز هستند پر شده‌است. دو تا از پیکسلها مرز هستند پر شده‌است. یکی از پیکسلها مرز پر شده‌است. صفر پیکسل مرز هستند پر شده‌است.
با فرض اینکه یک نقاش بخواهد آن شکل را رنگ کند به این صورت عمل می‌کند: نقاش پس از منطقه با قرار دادن دست راست خود را بر روی دیوار (مرز در منطقه) و پیشرفت در کنار لبه‌های منطقه بدون برداشتن دست خود کار را انجام می‌دهد.
برای حالت اول :نقاش برای نقاشی(پر کردن) پیکسل ایستاده است و بر اساس الگوریتم متوقف می‌شود.
برای حالت دوم : مسیر منتهی به خارج از منطقه وجود دارد. رنگ پیکسل نقاش ایستاده است و به حرکت در جهت راه باز ادامه می‌دهد.
برای حالت ۳ : اگر به پیکسل مرز بریسم از روش دست راست استفاده می‌کنیم.
برای حالت ۴: ما نیاز به بررسی در مقابل ۸ گوشه متصل بهم داریم که آن‌ها هم پر است یا نه. اگر هر دو یا هر دو پر است، پس این یک تقاطع چند مسیر است و نمی‌تواند پر شود. اگر هر دو خالی است، و سپس پیکسل جاری می‌تواند رنگ و نقاش می‌تواند پس از قانون دست راست حرکت می‌کند.
الگوریتم معاملات هم برای حافظه است. برای اشکال ساده آن بسیار مؤثر است. با این حال، اگر به شکل پیچیده است با ویژگی‌های بسیاری، از الگوریتم صرف مقدار زیادی از زمان ردیابی لبه‌های منطقه تلاش می‌کند تا اطمینان حاصل شود که همه نقاشی شده‌است.
این الگوریتم برای اولین بار در سال ۱۹۸۱ در ویکام برای سیستم پردازش تصویر تولید شده توسط سیستم ویکام در دسترس قرار گرفت . پر کردن سکیلینگ الگوریتم می‌تواند با خطوط پر سرعت. به بررسی اطراف هر پیکسل با استفاده از پشته، آن را بازرسی کرده و خطوط همسایه (قبل و بعد( را برای پیدا کردن بخش‌های مجاور که ممکن است در پیمایش پر از استفاده کنیم. بهره وری : هر پیکسل یک بار چک می‌شود.
رفتار کردن با مقیاس بزرگ ویرایش
روش اصلی مورد استفاده برای کنترل پر کردن طوفان یا داده محور یا فرایند محور می‌باشد. در روش داده محور می‌تواند هر دو پشته یا صف به پیمایش نقاط مورد نظر بپردازد. برای الگوریتم فرایند محور، لزوماً باید از یک پشته استفاده کنید.
الگوریتم پر کردن طوفانی با یک چهار راه به صورت لوزی شکل را پر کنید.
کارایی : برای هر پیکسل ۴ پیسکل بررسی می‌شود.
طبق شکل الگوریتم به صورت خطی بررسی می‌کند مانند کامپیوترهای قدیمی تر بازی‌های ۸ بیتی است.
کارایی : ۴ برای هر پیکسل ،۸پیکسل بررسی می‌شود.