Bresenham Çizgi Algoritması
Bu algoritma bir satırı taramak için kullanılır. Bresenham tarafından geliştirilmiştir. Yalnızca tamsayılarda toplama, çıkarma ve çarpma işlemlerini içerdiğinden etkili bir yöntemdir. Bu işlemler çok hızlı bir şekilde gerçekleştirilebildiğinden satırlar hızlı bir şekilde oluşturulabilmektedir.
Bu yöntemde seçilen bir sonraki piksel, gerçek çizgiye en az mesafeye sahip olandır.
Yöntem şu şekilde çalışır:
Bir piksel P varsayalım 1 '(X 1 ',Ve 1 '), ardından mayıs ayından geceye kadar çalışırken sonraki pikselleri seçin, P'ye doğru yatay yönde her seferinde bir piksel konumu 2 '(X 2 ',Ve 2 ').
Herhangi bir adımda bir piksel seçildiğinde
Bir sonraki piksel
- Ya sağındaki (satırın alt sınırı)
- Biri sağda ve yukarısında (çizginin üst sınırı)
Çizgi, P arasındaki yoldan en az mesafeye düşen piksellerle en iyi şekilde tahmin edilir. 1 ',P 2 '.
Alt piksel S ile üst piksel T arasında bir sonrakini seçmek için.
S seçilirse
elimizde x var ben+1 =x Ben +1 ve y ben+1 =y Ben
T seçilirse
elimizde x var ben+1 =x Ben +1 ve y ben+1 =y Ben +1
Doğrunun x = x noktasındaki gerçek y koordinatları ben+1 dır-dir
y=mx ben+1 +b
S'den y yönünde gerçek çizgiye olan mesafe
s = y-y Ben
T'den y yönünde gerçek çizgiye olan mesafe
t = (y Ben +1)-y
Şimdi bu 2 mesafe değeri arasındaki farkı düşünün
s - t
Ne zaman (s-t) <0 ⟹ s < t < p>
En yakın piksel S'dir
(s-t) ≧0 ⟹ sn olduğunda En yakın piksel T'dir Bu fark m'yi yerine koyma Burada c= 2△y+△x (2b-1) Karar değişkenini d yazabiliriz ben+1 bir sonraki kayma için x_(i+1)=x olduğundan Ben +1, elimizde Özel Durumlar Seçilen piksel T pikselinin üst kısmındaysa (yani, d Ben ≧0)⟹ ve ben+1 =y Ben +1 Seçilen piksel T pikselinin alt kısmındaysa (yani, d Ben <0)⟹ y i+1=y Ben Son olarak d'yi hesaplıyoruz 1 mx'den beri 1 +b-y Ben =0 ve m = 1. Yalnızca tamsayı aritmetiği içerir, dolayısıyla basittir. 2. Yinelenen noktaların oluşmasını önler. 3. Çarpma ve bölme kullanılmadığı için donanım kullanılarak gerçekleştirilebilir. 4. DDA Algoritması gibi kayan nokta hesaplamaları içermediğinden DDA (Dijital Diferansiyel Analizör) ile karşılaştırıldığında daha hızlıdır. 1. Bu algoritma yalnızca temel çizgi çizmeye yöneliktir. Başlatma, Bresenham'ın çizgi algoritmasının bir parçası değildir. Yani düzgün çizgiler çizmek için farklı bir algoritmaya bakmanız gerekir. Aşama 1: Algoritmayı Başlat Adım 2: Değişken x'i bildirin 1 ,X 2 ,Ve 1 ,Ve 2 ,d,i 1 ,Ben 2 ,dx,dy Aşama 3: X'in değerini girin 1 ,Ve 1 ,X 2 ,Ve 2 Adım4: dx = x'i hesaplayın 2 -X 1 Adım 5: (x, y)'yi başlangıç noktası ve x olarak düşünün son x'in mümkün olan maksimum değeri olarak. Adım 6: (x,y) koordinatlarında nokta oluşturun. Adım 7: Tüm satırın oluşturulup oluşturulmadığını kontrol edin. Adım 8: Sonraki pikselin koordinatlarını hesapla Adım 9: Artış x = x + 1 Adım 10: En son (x, y) koordinatlarının bir noktasını çizin Adım 11: 7. adıma git Adım 1/2: Algoritmanın Sonu Örnek: Çizginin Başlangıç ve Bitiş konumları (1, 1) ve (8, 5)'tir. Ara noktaları bulun. Çözüm: X 1 =1 Çıktı:
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1 
ve karar değişkeninin tanıtılması
D Ben =△x (s-t)
D Ben =△x (2 (X Ben +1)+2b-2y Ben -1)
=2△xy Ben -2△y-1△x.2b-2y Ben △x-△x
D Ben =2△y.x Ben -2△x.y Ben +c
D ben+1 =2△y.x ben+1 -2△x.y ben+1 +c
D ben+1 -D Ben =2△y.(x ben+1 -X Ben )- 2△x(y ben+1 -Ve Ben )
D ben+1 +d Ben =2△y.(x Ben +1-x Ben )- 2△x(y ben+1 -Ve Ben )
D ben+1 =d Ben +2△y-2△x
D ben+1 =d Ben +2△y
D 1 =△x[2m(x 1 +1)+2b-2y 1 -1]
D 1 =△x[2(mx 1 +b-y 1 )+2m-1] , sahibiz
D 1 =2△y-△x Avantajı:
Dezavantajı:
Bresenham Çizgi Algoritması:
nerede x 1 ,Ve 1 başlangıç noktasının koordinatlarıdır
ve x 2 ,Ve 2 Bitiş noktasının koordinatlarıdır
dy = y'yi hesaplayın 2 -Ve 1
i'yi hesapla 1 =2*sen
i'yi hesapla 2 =2*(dy-dx)
d=i'yi hesapla 1 -dx
Eğer dx <0
O zaman x = x 2
y = y 2
X son =x 1
Eğer dx > 0 ise
O zaman x = x 1
y = y 1
X son =x 2
Eğer x > = x son
Durmak.
Eğer d <0
O zaman d = d + i 1
Eğer d ≧ 0 ise
O zaman d = d + i 2
y'yi artırın = y + 1
Ve 1 =1
X 2 =8
Ve 2 =5
dx=x 2 -X 1 =8-1=7
sen=y 2 -Ve 1 =5-1=4
BEN 1 =2* ∆y=2*4=8
BEN 2 =2*(∆y-∆x)=2*(4-7)=-6
d = ben 1 -∆x=8-7=1
X Ve d=d+ı 1 ya da ben 2 1 1 d+ı 2 =1+(-6)=-5 2 2 d+ı 1 =-5+8=3 3 2 d+ı 2 =3+(-6)=-3 4 3 d+ı 1 =-3+8=5 5 3 d+ı 2 =5+(-6)=-1 6 4 d+ı 1 =-1+8=7 7 4 d+ı 2 =7+(-6)=1 8 5 Bresenham Çizgi Çizim Algoritmasını uygulama programı:
#include #include void drawline(int x0, int y0, int x1, int y1) { int dx, dy, p, x, y; dx=x1-x0; dy=y1-y0; x=x0; y=y0; p=2*dy-dx; while(x=0) { putpixel(x,y,7); y=y+1; p=p+2*dy-2*dx; } else { putpixel(x,y,7); p=p+2*dy;} x=x+1; } } int main() { int gdriver=DETECT, gmode, error, x0, y0, x1, y1; initgraph(&gdriver, &gmode, 'c:\turboc3\bgi'); printf('Enter co-ordinates of first point: '); scanf('%d%d', &x0, &y0); printf('Enter co-ordinates of second point: '); scanf('%d%d', &x1, &y1); drawline(x0, y0, x1, y1); return 0; } 
DDA Algoritması ile Bresenham Çizgi Algoritması arasındaki farkı ayırt edin:
DDA Algoritması Bresenham Çizgi Algoritması 1. DDA Algoritması kayan noktayı, yani Gerçek Aritmetiği kullanır. 1. Bresenham'ın Doğru Algoritması sabit nokta kullanır, yani Tamsayı Aritmetiği 2. DDA Algoritmaları işleminde çarpma ve bölmeyi kullanır 2.Bresenham Çizgi Algoritması işleminde yalnızca çıkarma ve toplama işlemlerini kullanır 3. DDA Algoritması, gerçek aritmetik kullandığından (Kayan Nokta işlemi) çizgi çiziminde Bresenham'ın Çizgi Algoritmasından daha yavaştır. 3. Bresenham Algoritması, DDA Algoritmasından daha hızlıdır çünkü hesaplamasında yalnızca toplama ve çıkarma işlemlerini içerir ve yalnızca tamsayı aritmetiği kullanır. 4. DDA Algoritması, Bresenham'ın Çizgi Algoritması kadar doğru ve verimli değildir. 4. Bresenham'ın Çizgi Algoritması DDA Algoritmasına göre daha doğru ve verimlidir. 5.DDA Algoritması daire ve eğriler çizebilir ancak Bresenham Çizgi Algoritması kadar doğru değildir 5. Bresenham'ın Çizgi Algoritması, DDA Algoritmasından daha doğru bir şekilde daire ve eğriler çizebilir.
