الگوریتم رنگ کدن نواحی - گرافیک کامپیوتری

[devildarkness]

سلام

برای پروژه درس گرافیک 1 یه برنامه Paint نوشتم و یرای رنگ کردن نواحی از الگورینم نقطه میانی 4point استفاده کردم، اما این الگوریتم خیلی کنده و مثلا باری رنگ کردن یه مستطیل 600*400 چیزی حدود 25 الی 30 ثانیه زمان می بره !

میخواستم ببینم الگوریتم سریع تری برای اینکار وجود داره یا نه ؟ اگه هست ممنون میشم اون الگوریتم رو معرفی کنین...

با تشکر.

[whitehat]

من اطلاعاتی در مورد 4Point ندارم، اگه امکان داره در مورد آن کمی توضیح دهید.(البته اگه منظور تئوری 4 رنگ (http://en.wikipedia.org/wiki/Four-color_theorem) نباشه)
در مورد مشکل شما، چرا از الگوریتم Flood Fill (http://en.wikipedia.org/wiki/Flood_fill) استفاده نمی کنید؟

[mehrzad007]

تو برنامه paint.net رو نگاه کن . نمی دونم از این چیزی که آقای وایت هت گفتند استفاده کرده یا نه اما سرعت خوبی داره

[devildarkness]

این الگوریتم برای رنگ کردن نواحی بسته بکار میره و کارش اینه که نقطه ای رو میگیره و اونو رنگ میکنه و داخل یک stack میریزه بعد چهار نقطه بالا و پایین و چپ و راست اونو گرفته و با رنگ پس زمینه ای که از نقطه اصلی گرفته مقایسه میکنه و در صورت تطابق اونا رو رنگ کرده و به stack میریزه و در مرحله بعد یه نقطه رو pop کرده و این عمل رو تا خالی شدن پشته ادامه میده.

این توضیح الگوریتم بود اما وقتی من توی #C اونو پیاده کردم خیلی کند رنگ میزنه !!! میشه در مورد الگوریتم flood fill راهنماییم کنید ؟!!

[saeid5977]

سلام
این کاری که شما میکنی همون flood fill هستش.
یه سوال! هر نقطه رو که رنگ میزنی روی صفحه نشونش میدی یا وقتی کار رنگ زدن تموم شد کل تصویر رو refresh میکنی؟ اگه جواب مثبته با استفاده از رنگ آمیزی بافر در حافظه و نمایش اون بعد از اتمام سرعتت میتونه بیشتر بشه.

[devildarkness]

سلام
این کاری که شما میکنی همون flood fill هستش.
یه سوال! هر نقطه رو که رنگ میزنی روی صفحه نشونش میدی یا وقتی کار رنگ زدن تموم شد کل تصویر رو refresh میکنی؟ اگه جواب مثبته با استفاده از رنگ آمیزی بافر در حافظه و نمایش اون بعد از اتمام سرعتت میتونه بیشتر بشه.

سلام
اوت ممنون از راهنماییتون
من اول bitmapی که در اختیار دارم رو رنگ میکنم بعد در انتهای الگوریتم کل صفحه رو refresh میکنم. اما بازهم وحشتناک برنامم برای رنگ زدن کنده !!!

[بمب منطقی]

این الگوریتم باید هم کند باشه.چون نقاط زیادی رو مکررا چک میکنه(در صورتی که قبلا چک شده و در نتیجه بررسی ،رنگ شده و یا رنگ نشده) من قبلا این الگوریتم رو استفاده کردم.
برای اینکه از تکرار چک کردن نقاط جلوگیری بشه باید چک کردن نقاط رو بصورت سطری انجام بدی.یعنی نقاط بالائی و پائینی نقطه ای که برای شروع رنگ آمیزی،انتخاب شده رو باید به صورت سطری چک کنی(همزمان در دو جهت بالا و پائین و در هر سطر در دو جهت مخالف).البته به همین راحتی ها هم نیست.در مورد اشکال نا منظم قضیه خیلی سختر میشه و تکرار چک کردن سطر هم وجود داره. توضیحش از حوصله من یکی خارجه.
البته در الگوریتم (flood fill(4point اگه از یک گراف برای نگه داشتن سابقه ،به همراه الگوریتم Graph-search (برای حذف تکرار) استفاده کنی میتونی سرعت رو خیلی افزایش بدی.
در کل:
در اشکال منظم -> رنگ آمیزی سطری دو جهته
در اشکال نا منظم -> رنگ آمیزی به روش flood fill به همراه graph و استفاده از الگوریتم graph-search

[devildarkness]

سلام
ممنون از راهنماییتون.
یه الگوریتم دیگه که بهش برخوردم scanline بود که کارش به این صورت بود که سطر به سطر یک خط افقی رسم میکرد و با محاسبه نقاط تلاقی با شکل مورد نظر و تعداد اونها ناحیه مورد نظر رو رنگ میکرد.

البته نتونستم اونو پیاده سازی کنم !!!
بازم ممنون از راهنمایی هایی که داشتین ...

[بمب منطقی]

یه الگوریتم دیگه که بهش برخوردم scanline بود

اینی که شما فرمودین دقیقا همون رنگ آمیزی سطری دو جهته هست.

موفق باشی

[kija_gtc]

الگوريتم (http://www.google.com/custom?hl=fa&client=google-coop&cof=FORID:13%3BAH:left%3BCX:%25D8%25A8%25D8%25B1%2 5D9%2586%25D8%25A7%25D9%2585%25D9%2587%2520%25D9%2 586%25D9%2588%25DB%258C%25D8%25B3%3BL:http://www.google.com/coop/intl/fa-US/images/custom_search_sm.gif%3BLH:65%3BLP:1%3BVLC:%23551a8 b%3BGFNT:%23666666%3BDIV:%23cccccc%3B&cx=010277259273172057471:gbud9yj2nhi&adkw=AELymgWo7_F8u16nOjvrvA5IGnOadCL1_EQIq9pT75KJp NF9e9WkRNZNU8XqbsDUIyQxB__aQdI9T01sAXu_shUfGcqpfMN P_vf1g7zCzXZrKJZ_BJAss_WdpW_AlhZ0O2v_UMqyC6ay&boostcse=0&ei=lTH9SaPnHZaLsAbi98TDBA&sa=X&oi=spell&resnum=0&ct=result&cd=1&q=%D8%A7%D9%84%DA%AF%D9%88%D8%B1%D9%8A%D8%AA%D9%85&spell=1) scanline براي اينكه شكل هاي غير محدب را هم رنگ آمیزی كنى بايد چه جوري نوشته بشود؟

[p_mcse_it]

سلام ....سوالي داشتم...كتاب يا pdf هست كه انواع الگلوريتم هاي گرافيك را آموزش بده؟ مثل الگوريتم رنگ كردن و ...

[mms_4004]

درسته دیگه دیر شده اما شاید به درد بقیه دوستان بخوره.

آره هست، من خودم دارم، اما نمی دونم اگه بزارمش شامل قانون کپی رایت میشه یا نه....اما اسمش اینه

COMPUTER GRAPHICS C version: DONALD HEARN - M.PAULINE BAKER

ای بوکش رو دارم، حتماً هست، اگه جستجو کنید حتماً پیداش میکنید.