****** 1

Report
‫فصل سوم‬
‫الگوریتم های ترسیم‬
‫‪1‬‬
‫‪S. POORKIANI‬‬
‫ترسیم خط‪ :‬مقدمه‬
‫‪ ‬در این مبحث ابتدا در باره اصول ومبانی خط بحث می شود سپس دو الگوریتم‬
‫‪ DDA‬و ‪ Bresenham‬مورد بررس ی قرار می گیرند‪.‬‬
‫‪y‬‬
‫‪y  mxb‬‬
‫‪yend‬‬
‫‪where:‬‬
‫‪y end  y 0‬‬
‫‪x end  x 0‬‬
‫‪m ‬‬
‫‪b  y 0  m  x0‬‬
‫‪2‬‬
‫‪y0‬‬
‫‪x‬‬
‫‪xend‬‬
‫‪S. POORKIANI‬‬
‫‪x0‬‬
‫ مقدمه‬:‫ترسیم خط‬
:‫ شیب ها‬
m=∞
m=4
m=2
m = -4
m = -2
m=1
m = -1
m = 1/2
m = -1/2
m = -1/3
m = 1/3
m=0
m=0
S. POORKIANI
3
‫ مقدمه‬:‫ترسیم خط‬
y
m 
(7, 5)
5
y end  y 0
x end  x 0
y = mx + b
2
x 
(2, 2)
2
7
x
S. POORKIANI
yb
m
b  y 0  m  x0
4
‫ترسیم خط‪ :‬مقدمه‬
‫‪ ‬ابتدا پیدا کردن ‪ m‬و ‪: b‬‬
‫‪3‬‬
‫‪‬‬
‫‪5‬‬
‫‪4‬‬
‫‪52‬‬
‫‪72‬‬
‫‪2 ‬‬
‫‪5‬‬
‫‪3‬‬
‫)‪(7, 5‬‬
‫)‪(2, 2‬‬
‫‪1‬‬
‫‪5‬‬
‫‪2‬‬
‫‪55‬‬
‫‪3‬‬
‫‪4‬‬
‫‪5‬‬
‫‪4‬‬
‫‪5‬‬
‫‪4 ‬‬
‫‪6 ‬‬
‫‪5‬‬
‫‪3‬‬
‫‪5‬‬
‫‪2‬‬
‫‪b  2‬‬
‫برای هر مقدار ‪ x‬پیدا کردن مقدار ‪ y‬متناظر‪:‬‬
‫‪4‬‬
‫‪5‬‬
‫‪m ‬‬
‫‪5‬‬
‫‪3‬‬
‫‪y‬‬
‫‪x‬‬
‫‪3‬‬
‫‪y (4) ‬‬
‫‪y (6) ‬‬
‫‪S. POORKIANI‬‬
‫‪7‬‬
‫‪2‬‬
‫‪5‬‬
‫‪6‬‬
‫‪4‬‬
‫‪4‬‬
‫‪3 ‬‬
‫‪3‬‬
‫‪3‬‬
‫‪5‬‬
‫‪5‬‬
‫‪5‬‬
‫‪4‬‬
‫‪4‬‬
‫‪3‬‬
‫‪5‬‬
‫‪3‬‬
‫‪5‬‬
‫‪5 ‬‬
‫‪5‬‬
‫‪2‬‬
‫‪y (3) ‬‬
‫‪y (5) ‬‬
‫‪5‬‬
‫ مقدمه‬:‫ترسیم خط‬
y (3)  2
7
6
5
y (4)  3
4
3
y (5)  3
2
1
0
0
1
2
3
4
5
6
7
8
S. POORKIANI
y (6)  4
3
5
1
5
4
5
2
 2 .6  3
 3 .2  3
 3 .8  4
 4 .4  4
5
6
‫ترسیم خط‪:‬‬
‫‪ ‬در این مبحث دو الگوریتم رسم معرفی وبررس ی می شوند‪:‬‬
‫‪.i‬‬
‫‪.ii‬‬
‫‪7‬‬
‫‪DDA‬‬
‫‪Bersenham‬‬
‫‪S. POORKIANI‬‬
‫ترسیم خط‪ :‬الگوریتم ‪DDA‬‬
‫منظور از گام افزایش‪:‬‬
‫یعنی بین دو ‪ pixel‬در مرحله بعدی که باید یک ‪ pixel‬را انتخاب کنیم‪ ،‬کدام یک‬
‫شانس انتخاب دارد ؟‬
‫‪8‬‬
‫‪S. POORKIANI‬‬
‫ترسیم خط‪ :‬الگوریتم ‪DDA‬‬
‫‪ -1‬هنگامی که شیب بین ‪1‬و‪ -1‬است به مختصات ‪ ، x‬یک واحد یک واحد و‬
‫مختصات ‪ y‬براساس فرمول زیر افزایش می یابد‪:‬‬
‫‪y k 1  y k  m‬‬
‫))‪(xk+1, round(yk+m‬‬
‫)‪(xk+1, yk+m‬‬
‫))‪(xk, round(yk‬‬
‫‪9‬‬
‫‪S. POORKIANI‬‬
‫)‪(xk, yk‬‬
‫ترسیم خط‪ :‬الگوریتم ‪DDA‬‬
‫‪ -2‬هنگامی که شیب بین ‪1‬و‪ -1‬نیست‪( ،‬شیب تند)‪ .‬به مختصات ‪ ، y‬یک واحد‬
‫یک واحد و مختصات ‪ x‬براساس فرمول زیر افزایش می یابد‪:‬‬
‫‪1‬‬
‫‪m‬‬
‫‪x k 1  x k ‬‬
‫)‪(round(xk+ 1/m), yk+1‬‬
‫)‪(xk+ 1/m, yk+1‬‬
‫‪10‬‬
‫)‪(round(xk), yk‬‬
‫‪S. POORKIANI‬‬
‫)‪(xk, yk‬‬
m=(2-1)/(8-1) = (1/7)
(8,2)
:‫ مثال‬
(1,1)
X
y
Round(y)
1
1
1
2
1+(1/7)=1.14
1
3
1.14+(1/7)=1.28
1
4
1.28+(1/7)=1.42
1
5
1.42+(1/7)=1.57
2
6
1.57+(1/7)=1.71
2
7
1.71+(1/7)=1.85
2
8 S. POORKIANI
1.85+(1/7)=1.99
2
11
‫ترسیم خط‪ :‬الگوریتم برزنهام‬
‫‪ Jack Bresenham‬ایده ترسیم‬
‫خط و دایره را با محاسبه ضربها و‬
‫توانهای کمتر در اوایل دهه ‪1950‬‬
‫ارائه کرد و با استقبال زیادی روبرو‬
‫شد‪.‬‬
‫برزنهام در اين الگوريتم فقط از‬
‫افزايش ها و کاهش هاي‬
‫مقاديرصحيح استفاده ميکند و درگیر‬
‫محاسبات اعشاری نمیشود‪.‬‬
‫‪12‬‬
‫‪S. POORKIANI‬‬
‫ الگوریتم برزنهام‬:‫ترسیم خط‬
y – y0 = m (x - x0 )  ax + by +c =0

Midpoint Line Algorithm

NE
Decision variable
d  F M 
1

 F  x p  1, y p  
2

Q
M
P(xp, yp)
E
1

 a x p  1  b y p    c
2


d > 0 : choose NE

d <= 0 : choose E S. POORKIANI
13
‫ الگوریتم برزنهام‬:‫ترسیم خط‬

Initial Value of d
1
1


F  x0  1, y0    a  x0  1  b y0    c
2
2



Update d
 x  ,

if d  0, then  y  ,
d   2a  b 

S. POORKIANI
 x  ,
if d  0, then 
d   2 a
14
‫ترسیم خط‪ :‬الگوریتم برزنهام‬
‫‪m=(3-0)/(6-1) = 0.6‬‬
‫)‪(6,3‬‬
‫)‪(1,0‬‬
‫‪15‬‬
‫‪S. POORKIANI‬‬
‫ترسیم خط‪------------:‬‬
‫براي رسم خط چين ها‪:‬‬
‫‪ ‬روش اول ‪ :‬خط از ابتدا تا انتها رسم مي شود در ترسيم دوباره خط چین ها به رنگ‬
‫پس زمينه مي شود (روش نا کارامد )‪.‬‬
‫‪ ‬روش دوم‪ :‬ابتدا و انتهاي خط را محاسبه و به چندين خط تقسيم و خطوط کوچکتر‬
‫ترسيم مي گردند‪ .‬در اين روش بخاطر عدم ترسيم مناطق خالي زمان ذخیره مي‬
‫شود)‪.‬‬
‫‪16‬‬
‫‪S. POORKIANI‬‬
‫ترسیم دایره‪ :‬خواص دایره‬
‫‪ ‬دایره به صورت مجموعه نقاطی که همگی در فاصله داده شده ‪ r‬از نقطه مرکز‬
‫)‪ (xc,yc‬قرار دارند تعریف می شود‪.‬‬
‫‪ ‬برای هر نقطه‪ (X,Y) ،‬روی دایره با رابطه فیثاغورث به صورت رابطه زیر‬
‫تعریف می شود‪:‬‬
‫)‪(x,y‬‬
‫‪2‬‬
‫‪  y  yc   r‬‬
‫‪2‬‬
‫‪2‬‬
‫‪x  xc ‬‬
‫‪ө‬‬
‫‪r‬‬
‫‪y‬‬
‫‪c‬‬
‫‪xc‬‬
‫‪17‬‬
‫‪S. POORKIANI‬‬
‫ترسیم دایره‪ :‬خواص دایره‬
‫‪ ‬از معادله فیثاغورث می توان برای محاسبه نقاط روی محیط دایره با برداشن‬
‫گامهایی به طول واحد در روی محور ‪ x‬ها از ‪ r-xc‬تا ‪ r+xc‬و محاسبه مقادیر ‪y‬‬
‫استفاده کرد ‪:‬‬
‫‪2‬‬
‫‪r   x  xc ‬‬
‫‪2‬‬
‫‪y  yc ‬‬
‫‪ ‬ایرادات این روش ‪:‬‬
‫‪ -1‬نیازمند محاسبات زیاد‬
‫‪ -2‬شکل دایره دارای عدم تقارن می باشد ‪.‬‬
‫‪18‬‬
‫‪S. POORKIANI‬‬
‫ترسیم دایره‪ :‬خواص دایره‬
‫راه دیگر برای رسم دایره می توان از معادله دایره به صورت قطبی استفاده کرد که به‬
‫صورت زیر می باشد ‪:‬‬
‫‪x  x c  r cos ‬‬
‫‪y  y c  r sin ‬‬
‫از این معادالت برای تولید دایره می توان با اندازه گام زاویه ای ثابت استفاده کرد‪.‬‬
‫اما استفاده از این معادالت جهت ایجاد دایره به خاطر معادالت مثلثاتی زمان گير می‬
‫باشد‪.‬‬
‫‪19‬‬
‫‪S. POORKIANI‬‬
‫ترسیم دایره‬
‫‪ ‬برای هر کدام از روشهای گفته شده می توان با در نظر گرفتن خاصیت تقارنی دایره‬
‫محاسبات را کاهش داد‪.‬‬
‫‪20‬‬
‫‪S. POORKIANI‬‬
‫ترسیم دایره‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪21‬‬
‫با این حال باز هم محاسبات برای رسم دایره زمان زیادی را می گیرد !‬
‫در معادله اول محاسبات ضرب و جذر و در معادله دوم ضرب و محاسبات‬
‫مثلثاتی زمان گیر است‪.‬‬
‫با این حال الگوریتم کارآمدتری برای دایره با محاسبات افزاینده پارامترهای‬
‫تصمیم مانند الگوریتم خط برزنهام ارائه شده اند‪.‬‬
‫الگوریتم دایره برزنهام با مقایسه مربعات فواصل پیکسلها از این محاسبات‬
‫پیچیده اجتناب می کند ‪.‬‬
‫‪S. POORKIANI‬‬
‫ترسیم دایره‪ :‬برزنهام‬
‫براي دايره با معادله ‪ fcircle(x,y)= y2+x2-r2 ، y2+x2=r2‬را در نظر بگیريد‪،‬‬
‫‪22‬‬
‫‪S. POORKIANI‬‬
‫ترسیم دایره‪ :‬برزنهام‬
‫‪ ‬براي انتخاب يکي از دو نقطه ‪:‬‬
‫‪ ‬اگر ‪ Pk<0‬باشد آنگاه نقطه داخل دايره‬
‫است‪.‬‬
‫‪ ‬اگر ‪ Pk>0‬باشد آنگاه نقطه خارج دايره‬
‫است‪.‬‬
‫‪23‬‬
‫‪S. POORKIANI‬‬
‫ترسیم دایره‪ :‬برزنهام‬
‫هدف اين است که همه محاسباتمان را افزايش ي انجام دهيم‪،‬‬
‫در مورد نقطه ‪ S‬و ‪ T‬داریم‪:‬‬
‫از آنجاييکه )‪ f(S‬همیشه مثبت و )‪ f(T‬همیشه منفی است‪ ،‬متغیر ‪ d‬را به صورت زیر‬
‫تعریف می کنیم‪:‬‬
‫‪24‬‬
‫‪S. POORKIANI‬‬
‫ترسیم دایره‪ :‬برزنهام‬
‫با توجه به مقدار ‪ d‬بدست آمده خواهيم داشت ‪:‬‬
‫‪25‬‬
‫‪S. POORKIANI‬‬
‫ترسیم دایره‪ :‬برزنهام‬
‫‪ ‬ترسیم دایره به روش نقطه میانی به شعاع ‪ r=10‬رسم کنید ‪.‬‬
‫‪ ‬شروع از ‪ X=0‬و ‪y=10‬‬
‫‪26‬‬
‫‪S. POORKIANI‬‬
S. POORKIANI
27
‫ترسیم بیض ی‬
‫‪ ‬به کمک تعريف چند جمله اي بيض ي ‪:‬‬
‫‪ ‬در اين روش‪:‬‬
‫‪28‬‬
‫‪S. POORKIANI‬‬
‫ترسیم بیض ی‬
S. POORKIANI
29
‫ترسیم بیض ی‬
‫‪= 1‬‬
‫‪(y-k)2‬‬
‫‪b2‬‬
‫‪+‬‬
‫‪(x-h)2‬‬
‫‪a2‬‬
‫اگر مرکز‪ ،‬مبدا مختصات باشد‪:‬‬
‫‪h=0 , k=0‬‬
‫‪y2‬‬
‫‪= 1‬‬
‫‪2‬‬
‫‪b‬‬
‫‪+‬‬
‫‪x2‬‬
‫‪a2‬‬
‫‪b2 x2 + a2 y2= b2 a2‬‬
‫‪30‬‬
‫‪S. POORKIANI‬‬
‫در هر مرحله به ‪ x‬ها اضافه میشود و در‬
‫صورت لزوم از ‪y‬ها کم می کنیم‪.‬‬
‫ترسیم بیض ی‬
‫‪y‬‬
‫‪m > -1‬‬
‫‪m < -1‬‬
‫‪b‬‬
‫‪x‬‬
‫‪a‬‬
‫در هر مرحله از ‪ y‬ها کم میشود و در‬
‫صورت لزوم به ‪x‬ها اضافه می کنیم‪.‬‬
‫‪31‬‬
‫‪S. POORKIANI‬‬
‫ترسیم مستطیل‬
‫‪32‬‬
‫‪S. POORKIANI‬‬

similar documents