Bresenham'ın çizgi algoritması

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

Pseudo kod 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 x_k := x0
      int y_k := y0
      while x_k < x1 
           x_k+1 := x_k + 1
           if error > 0
                y_k+1 := y_k + 1
                error := error + 2 * deltay - 2 * deltax
           else
                y_k+1 := y_k
                error := error + 2 * deltay
           x_k := x_k+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 (x_k, y_k) olduğunu ve y-ekseninin yavaş arttığını varsayalım. d_alt gerçek doğruyla y_k arasındaki uzaklık olsun. d_üst gerçek doğruyla y_k + 1 arasındaki uzaklık olsun.

Eğer (d_alt < d_üst) ise y_k+1 := y_k olmalıdır. Aksi halde y_k+1 := y_k + 1 olmalıdır.

y = mx + b doğrusu için

    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)

    m = (y1 - y0) / (x1 - x0) = deltay / deltax

    d_alt - d_üst = 2 * m * (x_k + 1) - 2 * y_k - 1
                = 2 * deltay * (x_k + 1) / deltax - 2 * y_k - 1

Bölüm halindeki deltax'den kurtulmak için bulduğumuz formülü deltax'le çarpalım ve p_k olarak adlandıralım. p_k değeri optimize edilmiş algoritmada error olarak isimlendirilmişti ama burada ardışık error değerlerini karıştırmamak için p_k olarak adlandıracağız.

   p_k = deltax * (d_alt - d_üst) = 2 * deltay * (x_k + 1) - 2 * deltax * y_k - deltax

Eğer p_k pozitifse gerçek doğru üst piksele daha yakın olduğu için y_k+1 = y_k + 1, aksi halde y_k+1 = y_k olacaktır.

  p_k+1 - p_k = 2 * deltay * (x_k+1 - x_k) - 2 * deltax * (y_k+1 - y_k)

x_k+1 = x_k + 1 olduğundan

  p_k+1 = p_k + 2 * deltay - 2 * deltax * (y_k+1 - y_k)

Eğer p_k pozitifse (y_k+1 - y_k) = 1; aksi halde (y_k+1 - y_k) = 0

Görüldüğü üzere error değeri (yani p_k) pozitifse 2 * deltax kadar azaltılıyor ve y_k değeri artırılıyor. Ayrıca error değeri, her adımda 2 * deltay kadar artırılmaktadır.

İlgili Araştırma Makaleleri

Işın izleme, gerçek dünyada ışığın ne şekilde hareket ettiğini göz önünde bulundurarak bir sahnenin görüntüsünü çizen bir grafik oluşturma yöntemidir. Ancak bu yöntemde işlemler gerçek yeryüzündeki yolun tersini izler. Gerçek dünyada ışık ışınları bir ışık kaynağından çıkar ve nesneleri aydınlatırlar. Işık, nesnelerden yansır ya da şeffaf nesnelerin içinden geçer. Yansıyan ışık gözümüze ya da kamera merceğine çarpar. Yansıyan ışık ışınlarının çoğu bir gözlemciye erişmediği için bir sahnedeki ışınları izlemek sonsuza dek sürebilir.

Digital Differential Analyzer, doğrunun bilgisayar ekranına çizimi için kullanılan bir algoritmadır.

<span class="mw-page-title-main">Birleştirmeli sıralama</span>

Birleşmeli Sıralama, bilgisayar bilimlerinde $\text{[math]}$ derecesinde karmaşıklığa sahip bir sıralama algoritmasıdır. Girdi olarak aldığı diziyi en küçük hale gelene kadar ikili gruplara böler ve karşılaştırma yöntemi kullanarak diziyi sıralar.

<span class="mw-page-title-main">Seçmeli sıralama</span>

Seçmeli Sıralama, bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır. Karmaşıklığı $\text{[math]}$ olduğu için büyük listeler üzerinde kullanıldığında verim sağlamaz ve genel olarak benzeri olan eklemeli sıralamadan daha başarısızdır. Seçmeli sıralama yalın olduğu ve bazı durumlarda daha karmaşık olan algoritmalardan daha iyi sonuç verdiği için tercih edilebilir.

Olasılık kuramı ve istatistik bilim dallarında geometrik dağılım şu iki şekilde ifade edilebilen ayrık olasılık dağılımıdır:

Bütün tam sayılar setine, yani { 1, 2, 3, .... } üzerine, bağlı olarak X sayıda Bernoulli denemesinde ilk başarıyı elde etmenin olasılık dağılımı; veya
Bütün tam sayılar setine, yani {1, 2,3, ....} üzerine, bağlı olarak ilk başarıyı elde etmeden Y = X − 1 başarısızlık sayısı olasılık dağılımı.

Tarak Sıralaması, ilk defa 1991 yılının Nisan ayında Stephen Lacey ve Richard Box tarafından Byte dergisinde duyurulmuş yalın bir sıralama algoritmasıdır. Kendisinden önce duyurulmuş kabarcık sıralaması algoritmasından başarılıdır ve karmaşıklıkta hızlı sıralama algoritmasıyla yarışır. Algoritmanın ana fikri listenin sonundaki küçük değerli öğelerin sayısını azaltmaktır. Kabarcık sıralaması algoritmasında sıralanacak listenin sonundaki küçük değerli öğelerin varlığı algoritmayı çok yavaşlattığı için tarak sıralamasında bu değerlerin sayısının azaltılması yoluna gidilmiştir.

Olasılık kuramı ve istatistik bilim dallarında Cauchy-Lorentz dağılımı bir sürekli olasılık dağılımı olup, bu dağılımı ilk ortaya atan Augustin Cauchy ve Hendrik Lorentz anısına adlandırılmıştır. Matematik istatistikçiler genel olarak Cauchy dağılımı adını tercih edip kullanmaktadırlar ama fizikçiler arasında Lorentz dağılımı veya Lorentz(yen) fonksiyon veya Breit-Wigner dağılımı olarak bilinip kullanılmaktadır.

Pivot ya da pivot element algoritmaların bir matris, dizi veya bir tür sonlu küme içinden, bir hesaplamada kullanılmak üzere seçtiği ilk elemandır. Matris algoritmaları için pivotun en azından sıfırdan farklı olması istenir ve genellikle sıfırdan uzak bir değer seçilir. Bu durumda algoritmanın düzgün çalışması için uygun pivot seçiminde satır veya sütunlar aralarında yer değiştirtilebilir.

Matematikte bir doğrunun eğimi ya da gradyanı o doğrunun dikliğini, eğimliliğini belirtir. Daha büyük eğim, daha dik bir doğru demektir.

Dijital İmza Algoritması dijital imza için bir FIPS standardıdır. Ağustos 1991'de National Institute of Standards and Technology (NIST) tarafından tasarlanmıştır. Dijital imza algoritması, ElGamal İmza Algoritması'nın bir varyantıdır.

Matematikte Gauss fonksiyonu, bir fonksiyon biçimidir ve şöyle ifade edilir:

\text{[math]}

Blum–Goldwasser Kriptosistem veya Blum-Goldwasser şifreleme sistemidir. 1984 yılında Manuel Blum ve Şafi Goldwasser tarafından önerilen bir asimetrik anahtar şifreleme algoritmasıdır. Bulum-Goldwasser bilinen en verimli kripto sistemlerden biridir. RSA ile hız ve mesaj genişlemesi açısından kıyaslanabilir. Bu şifreleme algoritmasında rastgele sayı üretmek için Blum Blum Shub rastgele sayı üretme algoritması kullanılır. Büyük sayıların asal çarpanlarına ayrılma probleminin çözülemezliği kabulüne dayanan bir şifreleme algoritmasıdır.

Uluslararası Veri Şifreleme Algoritması (IDEA), 1991 yılında Xuejia Lai ve James Massey tarafından tasarlanmış bir blok şifreleme algoritmasıdır. Bilinen en güçlü algoritmalardandır.

Birim çember Matematikte, yarıçapı bir birim olan çembere birim çember denir. Çoğunlukla, özellikle trigonometride, Öklid düzlemine göre Kartezyen koordinat sisteminde, merkezi orijin üzerinde (0,0) olan ve yarıçapı bir birim olan çemberdir. n birim çember sıklıkla S¹; olarak ifade edilir. Genellikle daha büyük boyutları ise birim küredir. (x,y) birim çember üzerinde bir nokta olduğunda, |x| ve |y|, dik olan ve hipotenüsü bir olan üçgenin diğer kenar uzunluklarıdır. Bu nedenle, Pisagor teoremine göre, x ve y bu denklemi karşılamaktadır.

\text{[math]}

Diğer interpolasyon yöntemleri ile aynı olan amacı, belli bir fonksiyonun ayrık parçalarının (noktalarının) bilgilerini kullanarak, aynı fonksiyonun bilinmeyen başka noktaları için bir veri elde etmektir.

K-ortalama kümeleme ya da K-means kümeleme yöntemi N adet veri nesnesinden oluşan bir veri kümesini giriş parametresi olarak verilen K adet kümeye bölümlemektir. Amaç, gerçekleştirilen bölümleme işlemi sonunda elde edilen kümelerin, küme içi benzerliklerinin maksimum ve kümeler arası benzerliklerinin ise minimum olmasını sağlamaktır.

Medyan bir anakütle ya da örneklem veri serisini küçükten büyüğe doğru sıraladığımızda, seriyi ortadan ikiye ayıran değere denir. İstatistiğin bir alt dalı olan betimsel istatistikde medyan bir merkezsel konum ölçüsü kabul edilir.

<span class="mw-page-title-main">Lineer interpolasyon</span> eğri uydurma metodu

Lineer interpolasyon, lineer polinomlar kullanarak, verilerin bilindiği noktalardan yeni verilerin üretilmesini sağlayan bir eğri uydurma metodudur.

Toplanmış alan tablosu, bir ızgaranın dikdörtgen bir alt kümesindeki değerlerin toplamını hızlı ve verimli bir şekilde oluşturmak için bir veri yapısı ve algoritmadır. Görüntü işleme alanında, bütünleşik görüntü olarak da bilinir. 1984 yılında Frank Painter tarafından mipmap'lerle kullanılmak üzere bilgisayar grafiklerine tanıtıldı. Bilgisayarla görmede Lewis tarafından popüler hale getirildi ve ardından "bütünleşik görüntü" adı verildi. 2001'de Viola-Jones nesne algılama çerçevesinde belirgin bir şekilde kullanıldı. Tarihsel olarak, bu ilke, çok boyutlu olasılık dağılım fonksiyonları çalışmasında, yani ilgili kümülatif dağılım fonksiyonlarından 2D olasılıkların hesaplanmasında çok iyi bilinmektedir.

Sayısal analizde, Newton-Raphson yöntemi olarak da bilinen ve adını Isaac Newton ve Joseph Raphson'dan alan Newton metodu, gerçel değerli bir fonksiyonun köklerine art arda daha iyi yaklaşımlar üreten bir kök bulma algoritmasıdır. En temel versiyonu, tek bir gerçek değişkenli $x$ için tanımlı olan $f$ fonksiyonu, fonksiyonun türevi $f '$ ve $f$ 'in bir kökü için bir $x 0$ başlangıç tahmini ile başlar. Fonksiyon yeterli ön kabulleri karşılıyorsa ve ilk tahmin yakınsa, o zaman

\text{[math]}

Bu sayfa, bu Vikipedi makalesine dayanmaktadır.
Metin, CC BY-SA 4.0 lisansı altında mevcuttur; ek koşullar uygulanabilir.
Görseller, videolar ve sesler kendi lisansları altında mevcuttur.