ملء فيضاني

خوارزمية الملء الفيضاني (بالإنجليزية: Flood fill)‏ أو خوارزمية ملء البذور (بالإنجليزية: seed fill)‏ هي خوارزمية في الرسوميات الحاسوبية تحدد المناطق المترابطة بالنسبة لنقطة معينة ضمنمصفوفة متعدد الأبعاد.^[1] تستخدم هذه الخوارزمية في عملية «الطلاء» "bucket" التي تحويها برامج الرسم بالحاسوب من أجل تحديد أي المناطق من الصورة النقطية تكون متصلة وبالتالي يمكن طلائها بلون معين. كما تستخدم في ألعاب الأحاجي مثل كانسة الألغام وغيرها من أجل تحديد أي القطع تم حلها.

الخوارزمية

تعمل خوارزمية الملء الفيضاني على ثلاثة متحولات: نقطة البداية، اللون المستهدف، ولون الاستبدال. تفحص الخوارزمية كامل النقاط في المصفوفة التي تكون متصلة مع نقطة البداية بطريق من نقاط لها اللون المستهدف وتغير لونها إلى لون الاستبدال. هناك عدة طرق لهيكلة خوارزمية الملء الفيضاني ولكن معظمها يستخدم هياكل بيانات الطابور أو مكدس.

أحد الخوارزميات التكرارية التي تعمل على المكدس تكون خطواتها على النحو التالي:

ملء فيضاني (نقطة، اللون المستهدف، اللون البديل)
1.إذا كان لون النقطة هو ذاته اللون مستهدف، عودة.
2.إذا كان لون النقطة هو ذاته اللون البديل، عودة.
3.غير لون النقطة إلى اللون المستهدف.
4.إبدأ ملء فيضاني (نقطة إلى يمين النقطة الحالية، اللون المستهدف، اللون البديل)
إبدأ ملء فيضاني (نقطة إلى يسار النقطة الحالية، اللون المستهدف، اللون البديل)
إبدأ ملء فيضاني (نقطة إلى أعلى النقطة الحالية، اللون المستهدف، اللون البديل)
إبدأ ملء فيضاني (نقطة إلى أسفل النقطة الحالية، اللون المستهدف، اللون البديل)
5.عودة.

مراجع

^ Torbert، Shane (2016). Applied Computer Science (ط. 2nd). Springer (نُشِر في 1 يونيو 2016). ص. 158. DOI:10.1007/978-3-319-30866-1. ISBN:978-3-319-30864-7. LCCN:2016936660. مؤرشف من الأصل في 2020-05-17.

وصلات خارجية

أحد تطبيقات خوارزمية الملء الفيضاني (لغة إنكليزية)

هذه بذرة مقالة عن الحاسوب أو العاملين في هذا المجال، بحاجة للتوسيع. فضلًا شارك في تحريرها.

[1] Torbert، Shane (2016). Applied Computer Science (ط. 2nd). Springer (نُشِر في 1 يونيو 2016). ص. 158. DOI:10.1007/978-3-319-30866-1. ISBN:978-3-319-30864-7. LCCN:2016936660. مؤرشف من الأصل في 2020-05-17.

[1]