Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Tarihçe
Bresenham'ın çizgi algoritması, Amerikalı bilgisayar mühendisi Jack Bresenham tarafından, 1960'lı yıllarda IBM için doğrunun bilgisayar ekranına çizimi için geliştirilen bir algoritmadır.
Artıları
Bresenham Algoritmasi DDA'ya göre daha hızlıdır, çünkü DDA'nın aksine ondalıklı sayılarla (float) işlem yapılmaz. Bresenham algoritması tam sayılarla(int) toplama, çıkarma ve ikiyle çarpma işlemlerini içerir. İkiyle çarpma işlemi shift Operasyonu ile Assembler düzeyinde çok hızlı yapılabildiğinden, Bresenham algoritması oldukça verimli bir algoritmadır.
Genel Algoritma
ile şu şekilde ifade edilir. Bu hali ondalıklı sayılarla işlem içerdiği için kullanılmaz.
function line(x0, x1, y0, y1) int deltax := abs(x1 - x0) int deltay := abs(y1 - y0) real error := 0 real deltaerr := deltay / deltax // Assume deltax != 0 (line is not vertical) int y := y0 for x from x0 to x1 plot(x,y) error := error + deltaerr if error ≥ 0.5 then y := y + 1 error := error - 1.0
Optimize Edilmiş Hali
Bu hali sadece tam sayılar kullandığı için oldukça verimlidir. Aşağıdaki hali algoritmanın anlaşılması için basitleştirilmiştir. aşağıdaki hali x-eksenin y-ekseninden daha hızlı arttığını (yani deltax'in deltay'den büyük olduğunu) ve x0'ın x1'den küçük olduğunu varsaymaktadır.
function line(x0, y0, x1, y1) int deltax := abs(x1 - x0) int deltay := abs(y1 - y0) int error := 2 * deltay - deltax int xk := x0 int yk := y0 while xk < x1 xk+1 := xk + 1 if error > 0 yk+1 := yk + 1 error := error + 2 * deltay - 2 * deltax else yk+1 := yk error := error + 2 * deltay xk := xk+1
Matematiksel İspatı
Bresenham algoritması verimliliğini, yavaş artan eksenin belirli bir kurala göre arttığını gözlemlemesine borçludur. Hızlı artan eksen her iterasyondan 1 piksel artarken, yavaş artan eksen bazen sabit kalıp, bazen bir piksel artar. Matematiksel olarak anlatmak istersek:
En son çizilen pikselin koordinatlarının (xk, yk) olduğunu ve y-ekseninin yavaş arttığını varsayalım. dalt gerçek doğruyla yk arasındaki uzaklık olsun. düst gerçek doğruyla yk + 1 arasındaki uzaklık olsun.
Eğer (dalt < düst) ise yk+1 := yk olmalıdır. Aksi halde yk+1 := yk + 1 olmalıdır.
y = mx + b doğrusu için
dalt = y - yk = m(xk + 1) + b - yk
düst = yk + 1 - y = yk + 1 - m(xk + 1)
m = (y1 - y0) / (x1 - x0) = deltay / deltax
dalt - düst = 2 * m * (xk + 1) - 2 * yk - 1 = 2 * deltay * (xk + 1) / deltax - 2 * yk - 1
Bölüm halindeki deltax'den kurtulmak için bulduğumuz formülü deltax'le çarpalım ve pk olarak adlandıralım. pk değeri optimize edilmiş algoritmada error olarak isimlendirilmişti ama burada ardışık error değerlerini karıştırmamak için pk olarak adlandıracağız.
pk = deltax * (dalt - düst) = 2 * deltay * (xk + 1) - 2 * deltax * yk - deltax
Eğer pk pozitifse gerçek doğru üst piksele daha yakın olduğu için yk+1 = yk + 1, aksi halde yk+1 = yk olacaktır.
pk+1 - pk = 2 * deltay * (xk+1 - xk) - 2 * deltax * (yk+1 - yk)
xk+1 = xk + 1 olduğundan
pk+1 = pk + 2 * deltay - 2 * deltax * (yk+1 - yk)
Eğer pk pozitifse (yk+1 - yk) = 1; aksi halde (yk+1 - yk) = 0
Görüldüğü üzere error değeri (yani pk) pozitifse 2 * deltax kadar azaltılıyor ve yk değeri artırılıyor. Ayrıca error değeri, her adımda 2 * deltay kadar artırılmaktadır.
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Bresenham in cizgi algoritmasi kullanilinca ortaya cikan bir cizgiTarihceBresenham in cizgi algoritmasi Amerikali bilgisayar muhendisi Jack Bresenham tarafindan 1960 li yillarda IBM icin dogrunun bilgisayar ekranina cizimi icin gelistirilen bir algoritmadir ArtilariBresenham Algoritmasi DDA ya gore daha hizlidir cunku DDA nin aksine ondalikli sayilarla float islem yapilmaz Bresenham algoritmasi tam sayilarla int toplama cikarma ve ikiyle carpma islemlerini icerir Ikiyle carpma islemi shift Operasyonu ile Assembler duzeyinde cok hizli yapilabildiginden Bresenham algoritmasi oldukca verimli bir algoritmadir Genel Algoritmaile su sekilde ifade edilir Bu hali ondalikli sayilarla islem icerdigi icin kullanilmaz function line x0 x1 y0 y1 int deltax abs x1 x0 int deltay abs y1 y0 real error 0 real deltaerr deltay deltax Assume deltax 0 line is not vertical int y y0 for x from x0 to x1 plot x y error error deltaerr if error 0 5 then y y 1 error error 1 0Optimize Edilmis HaliBu hali sadece tam sayilar kullandigi icin oldukca verimlidir Asagidaki hali algoritmanin anlasilmasi icin basitlestirilmistir asagidaki hali x eksenin y ekseninden daha hizli arttigini yani deltax in deltay den buyuk oldugunu ve x0 in x1 den kucuk oldugunu varsaymaktadir function line x0 y0 x1 y1 int deltax abs x1 x0 int deltay abs y1 y0 int error 2 deltay deltax int xk x0 int yk y0 while xk lt x1 xk 1 xk 1 if error gt 0 yk 1 yk 1 error error 2 deltay 2 deltax else yk 1 yk error error 2 deltay xk xk 1Matematiksel IspatiBresenham algoritmasi verimliligini yavas artan eksenin belirli bir kurala gore arttigini gozlemlemesine borcludur Hizli artan eksen her iterasyondan 1 piksel artarken yavas artan eksen bazen sabit kalip bazen bir piksel artar Matematiksel olarak anlatmak istersek En son cizilen pikselin koordinatlarinin xk yk oldugunu ve y ekseninin yavas arttigini varsayalim dalt gercek dogruyla yk arasindaki uzaklik olsun dust gercek dogruyla yk 1 arasindaki uzaklik olsun Eger dalt lt dust ise yk 1 yk olmalidir Aksi halde yk 1 yk 1 olmalidir y mx b dogrusu icin dalt y yk m xk 1 b yk dust yk 1 y yk 1 m xk 1 m y1 y0 x1 x0 deltay deltax dalt dust 2 m xk 1 2 yk 1 2 deltay xk 1 deltax 2 yk 1 Bolum halindeki deltax den kurtulmak icin buldugumuz formulu deltax le carpalim ve pk olarak adlandiralim pk degeri optimize edilmis algoritmada error olarak isimlendirilmisti ama burada ardisik error degerlerini karistirmamak icin pk olarak adlandiracagiz pk deltax dalt dust 2 deltay xk 1 2 deltax yk deltax Eger pk pozitifse gercek dogru ust piksele daha yakin oldugu icin yk 1 yk 1 aksi halde yk 1 yk olacaktir pk 1 pk 2 deltay xk 1 xk 2 deltax yk 1 yk xk 1 xk 1 oldugundan pk 1 pk 2 deltay 2 deltax yk 1 yk Eger pk pozitifse yk 1 yk 1 aksi halde yk 1 yk 0 Goruldugu uzere error degeri yani pk pozitifse 2 deltax kadar azaltiliyor ve yk degeri artiriliyor Ayrica error degeri her adimda 2 deltay kadar artirilmaktadir