الگوریتم برزنهام برای رسم خط

bresenham-algorithmا

کنون نحوه رسم خط با قرار دادن پیکسل ها بر روی صفحه نمایش را بحث می کنیم. اگرچه در جاوا به سادگی می توانیم از متد drawLine بدون توجه به پیکسل ها انجام دهیم ، ارضا کننده نخواهد بود اگر ندانیم این عمل چگونه انجام می شود. ما از مختصات صحیح استفاده می کنیم ولی وقتی که در مورد شیب یک خط بحث می کنیم خیلی جالب نیست که محور y به سمت پایین باشد ، که سیستم مختصات جاوا است. بنابراین در مختصات با کاربرد ریاضی از محور y با جهت مثبت رو به بالا در بحث استفاده می کنیم.

متاسفانه جاوا دارای متدی که تنها به منظور قرار دادن یک پیکسل بر روی صفحه نمایش باشد نیست ، بنابراین متد نسبتا عجیب زیر برای این کار تعریف می کنیم :

{ g.drawLine(x, y, x, y); }
اکنون متد drawLine به فرم

{ … }
که از متد putPixel بالا برای خروجی واقعی گرافیک استفاده می کند.

تصویر ۴.۱ یک پاره خط با نقاط انتهایی P(1, 1) و Q(12, 5) و همچنین پیکسل هایی را که می خواهیم محاسبه کنیم تا این خط را تقریب بزند نشان می دهد.

برای خط در تصویر ۴.۱ ، می نویسیم :

بیایید ابتدا مسأله را برای وضعیت مانند تصویر ۴.۱ که خط \lr{Q} در سمت راست قرار می گیرد و پایین تر از \lr{P} نیست حل کنیم. به صورت دقیق تر با حات خاص \begin{flalign} x_P < x_Q \nonumber\\ y_P \leq y_Q\nonumber\\ y_Q – y_P \leq x_Q – x_P \label{4.1} \end{flalign} \begin{figure} \caption{\label{fig:4-1_0}} \beginL{}\includegraphics[width=1\textwidth]{images/fig4-1_0}\endL{} \end{figure} روبرو هستیم که شرط آخر نشان می دهد خط \lr{PQ} با زاویه ای بیشتر از $۴۵\,^{\circ}$ قرار ندارد. پس می خواهیم یک مقدار صحیح \lr{y} برای هر کدام از مقادیر صحیح \begin{LTR} $x_p, x_{P+1}, x_{P+2}, \ldots , x_Q$ \end{LTR} پیدا کنیم. به جز اولین و آخزین تقطه ( که به صورت \lr{$y_P$} و \lr{$yQ$} داده شده اند ) سر راست تر ین راه برای محاسبه مختصات \lr{y} این نقاط با استفاده از شیب \begin{equation} m = \frac{y_Q – y_P}{x_Q -x_P} \label{4.2} \end{equation} است. بنابراین برای هر مختصات صحیح \textbackslash{}lr\{x\} ، می خواهیم مختصات \textbackslash{}lr\{y\} مطلوب را با گرد کردن مقدار \begin{LTR} $y_exact = y_P + m(x – x_P)$ \end{LTR} به نزدیکترین عدد صحیح به دست آوریم. چون دو مختصات \lr{x} پشت سر هم با اندازه واحد با هم اختلاف دارند ، اختلاف بین دو مقدار \lr{$y_exact$} برابر \lr{m} است. تصویر ۴.۲ این تفسیر از \lr{m} را نشان می دهد ، همین طور خطای \begin{equation} d = y_exact -y \label{4.3} \end{equation} از آنجا که \lr{d} خطایی است که با گرد کردن \lr{$y_exact$} به نزدیک ترین عدد صحیح انجام می دهیم ، نیاز است که \lr{d} شرط زیر را ارضاء کند : \begin{equation} -0/5 \leq d \leq +0/5 \label{4.4} \end{equation} نسخه اول از متد \lr{drawLine} بر اساس این مشاهده است : \begin{LTR} \codefont \begin{lstlisting} void drawLine1(Graphics g, int xP, int yP, int xQ, int yQ) { int x = xP, y = yP; float d = 0, m = (float)(yQ – yP)/(float)(xQ – xP); for(;;) { putPixel(g, x, y); if (x == xQ) break; x++ d += 0.5; if (d >= 0.5){y++; d–;} } }
این نسخه در صورتی که به تصویر ۴.۲ نگاه کنیم به سادگی قابل فهمیدن است. از آنجا که اولین فراخوانی putPixel بر روی نقطه ی P اجرا می شود ، با خطای d=0 شروع می کنیم. در هر گام حلقه x به اندازه ی یک واحد افزایش می یابد. لحظه ای فرض کنیم y تغییر نمی کند ، از معادله (??) نتیجه می شود رشد d به همان اندازه ی yexact است ، که توضیح می دهد چرا d به اندازه ی m رشد می کند. سپس درستی فرض را در عبارت if بعد از آن بررسی می کنیم. اگر d از ۰/۵ کوچکتر نبود از معادله (??) تخطی می کند ، بنابراین تصحیح را اعمال می کنیم که شامل افزایش y به اندازه ۱ و کاهش d به اندازه ۱ است. عمل آخر معادله ی (??) را دوباره صحیح می کند. با انجام این دو عمل در یک زمان معادله ی (??) نیز صحیح باقی می ماند.

ما از متد drawLile1 به عنوان اساس برای نوشتن نسخه سریعتر استفاده می کنیم ، که دیگر از نوع float استفاده نمی کند. این امکان پذیر است زیرا متغیر m یک عدد ترتیبی است که یک عدد صحیح بر یک عدد صحیح دیگر تقسیم شده است ، همان طور که معادله ی (??) نشان می دهد. از آنجا که عدد اعشاری دیگر ، d از صفر شروع و تنها هنگامی تغییر می کند که m یا ۱- به آن اضافه شود ، آن هم عدد ترتیبی است. با در نظر گرفتن هر دو صورت ، xQ − xP این اعداد ترتیبی و مقدار ثابت ۰/۵ استفاده شده در عبارت if ، از ضریب تناسب زیر

c = 2(xQ − xP)

برای m ، d و ثابت ۰/۵ استفاده می کنیم و متغیر های صحیح M و D را به جای متغیر های اعشاری m و d معرفی می کنیم. همچنین از Δ x به جای ثابت ۰/۵ استفاده می کنیم.

Figure 4.1:

این مقادیر جدید M ، D و Δ x به ترتیب به اندازه ی c برابر بزرگتر از m ، d و ۰/۵ هستند :

M = cm = 2(yQ − yP)
D = cd
Δ x = xQ − xP = c × ۰٫۵

در این راه به نسخه صحیح زیر دست پیدا می کنیم ، که بسیار شبیه قبلی و معادل آن است ولی سریعتر است. در راستای روش نامگذاری جاوا ، m و d را دوباره به جای M و D و dx را به جای Δ x نوشتیم :

{ int x = xP, y = yP; d = 0, dx = xQ – xP, c = 2 *dx, m = 2 * (yQ – yP); for(;;) { putPixel(g, x, y); if (x == xQ) break; x++ d += 0.5; if (d >= dx){y++; d -= c;} } }
با انجام این حالت خاص ، با نقطه P و Q ارضاء کننده معادله ی (??) ، اکنون به حالت بدون محدودیت نسبت به وضعیت نسبی P و Q بر می گردیم. برای حل این حالت های تقارن زیادی هستند که باید در نظر بگیریم. تا زمانی که

|yQ − yP| ≤ |xQ − xP|

باشد می توانیم دوباره از x به عنوان متغیر مستقل استفاده کنیم ، که به این معنی است که می توانیم این متغیر را به اندازه ی یک واحد در حلقه افزایش یا کاهش دهیم. در حالت عکس که خط های با زاویه ی بیس از ۴۵ ∘ هستند باید نقش x و y را عوض کنیم تا از قرار گرفتن نقاط انتخاب شده بسیار دور از هم جلوگیری کنیم. تمام اینها در متد عمومی رسم خط زیر قابل درک است. به سادگی می توانیم بررسی کنسم که این نسخه دقیقا همان نقاط که خط PQ را تقریب می زنند رسم می کند که نسخه drawLine2 رسم می کند ، اگر مختصات P و Q معادله (??) را ارضا کند :

قبل از اجرای یکی از دو حلقه for یک شرط if اجرا می شود در حالتی که x یا y به جای افزایش کاهش یابند که اطمینان حاصل شود که رسم PQ همیشه نقاط مشابه با QP رسم می کند. فکر رسم خطوط شیبدار تنها با استفاده از متغیر های صحیح اولین بار توسط برزنهام ارائه شد. بنابراین نام او بر روی این الگوریتم قرار دارد.

متد drawLine بالا اگر با مختصات منطقی اعشاری که تا حالا استفاده کردیم روبرو باشیم بسیار ساده است. برای مثال در بخش ?? ، یک برنامه به نام ClipPoly.java خواهد بود که متد زیر در آن قرار دارد.

در اینجا متد \lr{drawLine} خودمان متد \lr{drawLine} جاوا از کلاس \lr{Graphics} را فرا می خواند. اگر به جای آن ، می خواستیم از متد \lr{drawLine} خودمان با چهار متغیر صحیح استفاده کنیم ، که در بالا آمده است می توانیم که خط آخر کد قبلی را با کد زیر عوض کنیم \begin{LTR} \codefont \begin{lstlisting} page 95
در صورتی که متد putPixel در ابتدای این بخش را نیز اضافه کنیم. این ابتدا ممکن است گیچ کننده به نظر بیاید زیرا حالا ما دو متد drawLine داریم. ولی کامپایلر جاوا متد برزنهام drawLine را انتخاب می کند ، زیرا این متد آرگومان g بعلاوه چهار آرگومان از نوع int می گیرد. همچنین جالب است که اشاره کنیم جهت مثبت y در این بحث ما مشکلی ایجاد نمی کند

 

 به کانال برنامه نویسی ما پیوندید واز آخرین مطالب روز باخبر شوید

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *