السلام عليكم
الهدف من المقال :
في أي برنامج أو مكتبة رسومية ستجد أن امكانية تعبئة صورة معينة بلون معين ، وستجد السطل .. سطل الطلاء أمامك ، لتصبغ به الصورة ، تضعه على بيكسل معين ، ليقوم بصبغ ماحوله من بكسلات حتى يقف عن حد معين ، اما حد الصورة الخارجي أو بيكسل داخلي ذون لون مختلف ، مثال :
هذه المقالة تركز على خوارزميات أساسية بسيطة ، وليس على خوارزميات فعّالة وسريعة ، سيكون هناك تطبيق ، باستخدام لغة برمجية معينة مثل السي بلس بلس و مكتبة رسومية معينة مثل OpenGL .
خوارزمية Fill Flood :
صورة من الويكي.
تعتمد الخوارزمية على فكرة بسيطة ، وهي التعبئة باستخدام مفهوم الفيضان Flood ، ببساطة ، تلوين بكسل معين ، ثم الانتقال إلى كل بكسل مجاور له ، وهنا لدينا طريقتين في توضيع مفهوم التجاور ، اما باستخدام مفهوم 4-connected أو 8-connected .
4-connected : عملية تلوين أربع بكسلات مجاورة للبكسل الحالي ان امكن وفق الجهات التالية :
left - right - top - bottom ( طبعا بدون ترتيب ) .
صورة توضيحية :
8-connected : عملية تلوين ثمان بكسلات مجاورة للبكسل الحالي ان امكن وفق الجهات التالية :
left - right - top - bottom - upper left - upper right - lower left - lower right
صورة توضيحية :
الخوارزمية :
خوارزمية Flood Filling هي كالتالي :
void floodFill(int x,int y,int oldColor,int newColor)
{
// 4-connected version ( left right top bottom )
// you can apply another version such as :
// 8-connected version ( left , left-top , right ,top, right-top , bottom , right-bottom , left-bottom )
if( getPixelColor(x,y) == oldColor)// هل البكسل الحالي هو البكسل المطلوب تغييره
{
setPixelColor(x,y,newColor); // غير لونه
// الان .. انتقل الى البكسلات المجاورة لتطبيق نفس الفكرة
floodFill(x - 1 , y , oldColor,newColor); // left
floodFill(x + 1 , y , oldColor,newColor); // right
floodFill(x , y + 1 , oldColor,newColor); // top
floodFill(x , y - 1 , oldColor,newColor); // bottom
}
}
سيناريو :
لنفرض أن لدينا الصورة التالية :
ونريد تلوين بكسل معين وفق المعلومات التالية :
1- البكسل الذي سننطلق منه هو البكسل الذي سيختاره المستخدم بالنقر عليه بالفأرة مثلاً ، ونسمية البذرة seed .
2- لون البكسل البذرة هو اللون الأبيض .
3- اللون الجديد هو اللون الذي سيختاره المستخدم وليكن الأخضر .
4- الخوارزمية تعمل بنسخة 4-connected .
5- الخوارزمية ستتوقف اذا وصلت الى بكسل لايحمل اللون الأبيض .
وفق المعلومات السابقة ، ستبدو البكسلات بهذا الشكل :
والذي حدث هو التالي :
بدأت الخوارزمية بالبكسل رقم 1 ( البذرة ) ، وجدت أن لونه هو لون أبيض ، وبالتالي صار اللون الذي يجب تغييره في المراحل القادمة هو اللون الأبيض ، لونت البكسل باللون الاخضر ، اللون الجديد ، الان في البكسل 2 ، لكن لاحظ أن البسكل رقم 1 ، لم يفحص كل الجهات ، حيث تبقى البكسل العلوي + الأيمن + الأسفل .
توجهت إلى اليسار لتعيد نفسها مرة أخرى ، حيث اللون هو اللون الأبيض ، تصبغ الخوارزمية البكسل باللون الأخضر ، ثم تنتقل إلى الأعلى ، وستجد أن اللون ليس أبيض ، ثم الى اليمين ، ستجد أن اللون ليس أبيض ثم إلى الأسفل ، ستجد اللون أبيض ، وتلون البكسل رقم 3 باللون الاخضر ، جميع الجهات فحصت بالنسبة للبكسل الثاني .
الان من البكسل رقم 3 ، ستعيد تطبيق نفسها ، الى اليسار ، ثم الاعلى وكلاهما لايحملان اللون الابيض ، ثم الى اليمين ، لتلونه باللون الاخضر وتنتقل الى البكسل رقم 4 ، لاحظ أنه بقي الجهة السفلى سنرجه لها لاحقا .
الان البكسل 4 ، ستفحص الخوارزمية جميع الجهات ثم لاتجد بكسل باللون الابيض .. بالتالي لاتنتقل الى أي بكسل مجاور ..
تعود الى البكسل السابق - رقم 3 - ..تجد أن اخر جهة لم تفحصها هي الجهة السفلى .. وبعد فحصها تجد أن اللون ليس أبيض .
تعود للبكسل رقم 2 ، وتجد أن جميع الجهات تم فحصها .
تعد للبكسل رقم 1 ، ونجد اخر جهة لم تفحص هي الجهة العلوية .. نفحصها ، وتجد أنها لاتحمل اللون الابيض ، تتجاهلها .. ثم تفحص البكسل الأيمن الأبيض ذو الرقم 5، قتلونه بالاخضر ، ثم تنتقل اليه ، لاحظ أنه بقي الجهة السفلية ستعود لها لاحقا .
البكسل 5 : لايوجد يساره بكسل أبيض ، ثم الى الاعلى تجد بكسل أبيض ذو رقم 6 ، تلونه بالاخضر تنتقل اليه ( بقي الجهة اليمنى والسفلى ستعود لها ) .
البسكل 6 : بعد فحص جميع الجهات لاتجد بكسل أبيض اللون .
تعود إلى البكسل 5 : بعد فحص الجهات المتبقية ، لاتجد شيء .
تعود للبكسل 1 : بعد فحص جميع الجهات لاتجد بكسل أبيض اللون .
تنتهي الخوارزمية .
محاكاة الخوارزمية - تطبيق :
ملاحظة : البرنامج قيد التطوير ، وسيتم اضافة مزيد من المزايا ، بحيث تشاهد ترتيب كل بكسل تم تلوينه بشكل واضح ، ليسهل تتبع الخوارزمية .
قمت بكتابة برنامج يحاكي هذه الخوارزمية البسيطة ، حيث يمكنك تصميم الصورة التي تريد ، باللون الذي تريد من القائمة المنبثقة عند النقر على الزر الايمن ، ثم اذا انتهيت تختار الخيار Test Mode ، لتجرب الخوارزمية بشكل مرئي ، طبعا تختار البكسل البذرة الذي ستنطلق منه بالنقر عليه ، بعد اختيار اللون الذي تريد .
البرنامج بسيط وسهل ، وهو لتفهم الخوارزمية فقط ، وليس لشيء اخر ، حيث الكود لايفيدك بشيء .
كتابة الكود بسيط :
لكتابة الكود يمكن استخدام مبدأ Recursion أو Stack أو اي طريقة أخرى مناسبة ، في المرفقات مثال على هذه الخوارزمية ، المثال مكتوب بلغة السي بلس وباستخدام OpenGL/GLUT .
في المرفقات المثال - أرجو تحميل الملف الموجود باسم new and simple حيث هو أفضل من الملف القديم ، انظر للمشاركة رقم 12 لتعرف السبب
الخوارزمية التالية ستكون Boundary Fill ان شاء الله .
يتبع ...
