Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...
Bilgisayarlı grafik ve geometride çizgi çizmek için kullanılan Bresenham algoritması, çizgi kesişimleri, dikdörtgen kesişimleri ve çember çakışmaları gibi temel geometrik işlemlerdir.
Hesaplamalı geometride en temel problemler, geometrik nesnelerin (nokta, çizgi, daire, dikdörtgen) uzayda birbirlerine göre durumlarının tespiti ve çizilmesidir.
Bresenham Çizgi Çizme algoritması, sadece tam sayı aritmetiği (toplama, çıkarma, kaydırma) kullanarak ekran piksellerinde pürüzsüz çizgiler çizilmesini sağlayan son derece optimize edilmiş tarihi bir yöntemdir.
Çizgi Kesişimi (Line Intersection) iki 2D doğru parçasının çakışıp çakışmadığını yönelim (orientation/cross product) testleriyle deterministik olarak hesaplar. Dikdörtgen Kesişimi (Rectangle Intersection) eksene hizalı (AABB) kutuların çakışmalarını aralık kontrolleriyle bulurken, Çember Kesişimi (Circle Intersection) merkezler arası Öklid mesafesini yarıçaplar toplamıyla kıyaslar.
Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.
1// CCW (Counter-Clockwise) yönelim testi2function ccw(p1: [number, number], p2: [number, number], p3: [number, number]): number {3 const val = (p2[1] - p1[1]) * (p3[0] - p2[0]) - (p2[0] - p1[0]) * (p3[1] - p2[1]);4 if (val === 0) return 0; // Collinear (doğrusal)5 return val > 0 ? 1 : -1; // 1: Saat yönü, -1: Saat yönü tersi6}78// İki kenarın kesişip kesişmediğini denetler9function doIntersect(10 a1: [number, number], a2: [number, number],11 b1: [number, number], b2: [number, number]12): boolean {13 const o1 = ccw(a1, a2, b1);14 const o2 = ccw(a1, a2, b2);15 const o3 = ccw(b1, b2, a1);16 const o4 = ccw(b1, b2, a2);1718 // Genel kesişim koşulu19 if (o1 !== o2 && o3 !== o4) return true;20 return false;21}Modu ve parametreleri girin. Modlar: BRESENHAM (x1,y1,x2,y2), LINE_INT (x1,y1,x2,y2; x3,y3,x4,y4), RECT_INT (x1,y1,w1,h1; x2,y2,w2,h2). Örnek: BRESENHAM; 0,0,8,4
Modu ve parametreleri girin. Modlar: BRESENHAM (x1,y1,x2,y2), LINE_INT (x1,y1,x2,y2; x3,y3,x4,y4), RECT_INT (x1,y1,w1,h1; x2,y2,w2,h2). Örnek: BRESENHAM; 0,0,8,4
En İyi Durum: O(1) kesişim testleri için
Ortalama Durum: O(dx) çizgi çizme için
En Kötü Durum: O(dx)
O(1) ek bellek - Bu algoritmanın karmaşıklığı belirtilmemiş.
Temel Geometrik İşlemler (Primitive Geometric Operations) Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar: