Hat Oluşturma Algoritması

Bir çizgi iki noktayı birleştirir. Grafikte temel bir unsurdur. Bir çizgi çizmek için, aralarına çizgi çizebileceğiniz iki noktaya ihtiyacınız vardır. Aşağıdaki üç algoritmada, bir satır noktasına $ X_ {0}, Y_ {0} $ ve ikinci satır noktasına $ X_ {1}, Y_ {1} $ diyoruz.

DDA Algoritması

Sayısal Diferansiyel Analiz (DDA) algoritması, burada adım adım açıklanan basit hat oluşturma algoritmasıdır.

Step 1 - İki uç nokta $ (X_ {0}, Y_ {0}) $ ve $ (X_ {1}, Y_ {1}) $ girdisini alın.

Step 2 - İki uç nokta arasındaki farkı hesaplayın.

dx = X₁ - X₀
dy = Y₁ - Y₀

Step 3- 2. adımda hesaplanan farka bağlı olarak, piksel koymak için adım sayısını belirlemeniz gerekir. Dx> dy ise, x koordinatında daha fazla adıma ihtiyacınız vardır; aksi takdirde y koordinatında.

if (absolute(dx) > absolute(dy))
   Steps = absolute(dx);
else
   Steps = absolute(dy);

Step 4 - x koordinatı ve y koordinatındaki artışı hesaplayın.

Xincrement = dx / (float) steps;
Yincrement = dy / (float) steps;

Step 5 - X ve y koordinatlarını uygun şekilde artırarak pikseli yerleştirin ve çizginin çizimini tamamlayın.

for(int v=0; v < Steps; v++)
{
   x = x + Xincrement;
   y = y + Yincrement;
   putpixel(Round(x), Round(y));
}

Bresenham'ın Hat Üretimi

Bresenham algoritması, başka bir artımlı tarama dönüştürme algoritmasıdır. Bu algoritmanın en büyük avantajı, yalnızca tamsayı hesaplamaları kullanmasıdır. X ekseni boyunca birim aralıklarla hareket edin ve her adımda iki farklı y koordinatı arasından seçim yapın.

Örneğin, aşağıdaki şekilde gösterildiği gibi, (2, 3) konumundan (3, 3) ve (3, 4) arasından seçim yapmanız gerekir. Orijinal çizgiye daha yakın olan noktayı istersiniz.

$ X_ {k} + 1 örnek konumunda, $ matematiksel çizgiden dikey ayrımlar $ d_ {üst} $ ve $ d_ {alt} $ olarak etiketlenir.

Yukarıdaki çizimden, $ x_ {k} + 1 $ 'daki matematiksel doğrudaki y koordinatı -

Y = m ($ X_ {k} $ + 1) + b

Dolayısıyla, $ d_ {üst} $ ve $ d_ {alt} $ aşağıdaki gibi verilir -

$$ d_ {alt} = y-y_ {k} $$

$$ = m (X_ {k} + 1) + b - Y_ {k} $$

$$ d_ {üst} = (y_ {k} + 1) - y $$

$ = Y_ {k} + 1 - m (X_ {k} + 1) - b $

Bunları hangi pikselin matematiksel çizgiye daha yakın olduğuna dair basit bir karar vermek için kullanabilirsiniz. Bu basit karar, iki piksel konumu arasındaki farka dayanmaktadır.

$$ d_ {alt} - d_ {üst} = 2 dk (x_ {k} + 1) - 2y_ {k} + 2b - 1 $$

Bize yerine olsun m ile dy / dx burada dx ve dy son noktaları arasındaki farklar bulunmaktadır.

$$ dx (d_ {alt} - d_ {üst}) = dx (2 \ frac {\ mathrm {d} y} {\ mathrm {d} x} (x_ {k} + 1) - 2y_ {k} + 2b - 1) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + 2dy + 2dx (2b-1) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + C $$

Yani, $ P_ için {k} $ parametresi bir karar k bir hat boyunca inci adım verilir -

$$ p_ {k} = dx (d_ {alt} - d_ {üst}) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + C $$

$ P_ {k} $ karar parametresinin işareti, $ d_ {alt} - d_ {üst} $ ile aynıdır.

$ P_ {k} $ negatifse, alt pikseli seçin, aksi takdirde üst pikseli seçin.

Unutmayın, koordinat değişiklikleri x ekseni boyunca birim adımlarla gerçekleşir, böylece her şeyi tam sayı hesaplamalarıyla yapabilirsiniz. K + 1 adımında, karar parametresi şu şekilde verilir -

$$ p_ {k +1} = 2dy.x_ {k + 1} - 2dx.y_ {k + 1} + C $$

Buradan $ p_ {k} $ çıkarırsak -

$$ p_ {k + 1} - p_ {k} = 2dy (x_ {k + 1} - x_ {k}) - 2dx (y_ {k + 1} - y_ {k}) $$

Ancak, $ x_ {k + 1} $, $ (xk) + 1 $ ile aynıdır. Yani -

$$ p_ {k + 1} = p_ {k} + 2dy - 2dx (y_ {k + 1} - y_ {k}) $$

Burada, $ Y_ {k + 1} - Y_ {k} $, $ P_ {k} $ işaretine bağlı olarak 0 veya 1'dir.

İlk karar parametresi $ p_ {0} $, $ (x_ {0}, y_ {0}) $ olarak değerlendirilir -

$$ p_ {0} = 2dy - dx $$

Şimdi, yukarıdaki tüm noktaları ve hesaplamaları göz önünde bulundurarak, işte m <1 eğimi için Bresenham algoritması -

Step 1 - Sol uç noktayı $ (x_ {0}, y_ {0}) $ içine kaydederek, çizginin iki bitiş noktasını girin.

Step 2 - $ (x_ {0}, y_ {0}) $ noktasını çizin.

Step 3 - dx, dy, 2dy ve (2dy - 2dx) sabitlerini hesaplayın ve karar parametresi için ilk değeri şu şekilde alın:

$$ p_ {0} = 2dy - dx $$

Step 4 - Çizgi boyunca, k = 0'dan başlayarak her $ X_ {k} $ için aşağıdaki testi gerçekleştirin -

$ P_ {k} $ <0 ise, grafiğin bir sonraki noktası $ (x_ {k} +1, y_ {k}) $ ve

$$ p_ {k + 1} = p_ {k} + 2dy $$ Aksi takdirde,

$$ (x_ {k}, y_ {k} +1) $$

$$ p_ {k + 1} = p_ {k} + 2dy - 2dx $$

Step 5 - 4. adımı (dx - 1) kez tekrarlayın.

M> 1 için, her seferinde y'yi artırırken x'i artırmanız gerekip gerekmediğini öğrenin.

Çözdükten sonra, $ P_ {k} $ karar parametresinin denklemi çok benzer olacak, sadece denklemdeki x ve y değişecek.

Orta Nokta Algoritması

Orta nokta algoritması, Pitteway ve Van Aken tarafından modifiye edilen Bresenham'dan kaynaklanmaktadır. P noktasını (x, y) koordinatına zaten koyduğunuzu ve aşağıdaki şekilde gösterildiği gibi doğrunun eğiminin 0 ≤ k ≤ 1 olduğunu varsayalım.

Şimdi bir sonraki noktayı E'ye mi yoksa N'ye mi koyacağınıza karar vermelisiniz. Bu, N veya E noktasına en yakın Q kesişme noktasını belirleyerek seçilebilir. Q kesişme noktası N noktasına en yakınsa, N olarak kabul edilir. sonraki nokta; aksi takdirde E.

Bunu belirlemek için önce orta noktayı M (x + 1, y + ½) hesaplayın. E ve N'yi birleştiren dikey çizgi ile çizginin Q kesişme noktası M'nin altındaysa, bir sonraki nokta olarak E'yi alın; aksi takdirde bir sonraki nokta olarak N'yi alın.

Bunu kontrol etmek için örtük denklemi dikkate almalıyız -

F (x, y) = mx + b - y

Herhangi bir X'de pozitif m için,

Y satır üzerindeyse, F (x, y) = 0
Y çizginin üstündeyse, F (x, y) <0
Y çizginin altındaysa, F (x, y)> 0