انباشتن سیلابی

انباشتن سیلابی یا انباشتن دانه‌ای (به انگلیسی: Flood fill) یک الگوریتم است که ناحیه متصل به یک رأس داده شده در یک آرایه چند بعدی را مشخص می‌کند. به‌طور مثال این الگوریتم در ابزار پر کردن ”سطل” در برنامه‌های نقاشی به منظور پر کردن ناحیه‌های متصل و هم‌رنگ با رنگی متفاوت با رنگ قبلی یا در بازی‌هایی مانند گو یا مین‌روب برای مشخص کردن تکه‌های پاک‌سازی شده به کار می‌رود. این الگوریتم اگر روی تصویری برای پر کردن ناحیه محدود و خاصی از آن اعمال شود، به عنوان انباشتن مرزی نیز شناخته می‌شود.

انباشتن سیلابی بازگشتی ۴ جهته

عملکرد

الگوریتم انباشتن سیلابی سه پارامتر را به عنوان ورودی می‌پذیرد: راس آغازین، رنگ هدف و رنگ جایگزین. این الگوریتم به دنبال تمامی راس‌هایی در آرایه می‌گردد که به وسیله مسیر به رنگ هدف به گره آغازین متصلند، سپس آن‌ها را با رنگ جایگزین عوض می‌کند. راه‌های بسیار زیادی برای بنا کردن الگوریتم انباشتن سیلابی وجود دارد، اما همه آن‌ها از ساختمان داده پشته یا صف به صراحت یا به‌طور ضمنی استفاده می‌کنند.

انباشتن سیلابی بازگشتی ۸ جهته

پیاده‌سازی بازگشتی مبتنی بر پشته (چهار جهته)

یک پیاده‌سازی انباشتن سیلابی، به‌طور ضمنی مبتنی بر پشته (بازگشتی) به شرح زیر است:

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. Add node to the end of Q.
 4. While Q is not empty:
 5.     Set n equal to the last element of Q.
 6.     Remove last element from Q.
 7.     If the color of n is equal to target-color:
 8.         Set the color of n to replacement-color.
 9.         Add west node to end of Q.
 10.        Add east node to end of Q.
 11.        Add north node to end of Q.
 12.        Add south node to end of Q.
 13. 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.         For each node n between w and e:
10.             Set the color of n to replacement-color.
11.             If the color of the node to the north of n is target-color, add that node to Q.
12.             If the color of the node to the south of n is target-color, add that node to Q.
13. Continue looping until Q is exhausted.
14. Return.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Flood fill». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۹ بهمن ۱۳۹۲.