Çokgen Doldurma Algoritması
Çokgen, aşağıdaki şekilde gösterildiği gibi sıralı bir köşe noktası listesidir. Çokgenleri belirli renklerle doldurmak için, çokgenin sınırına düşen pikselleri ve çokgenin içine düşenleri belirlemeniz gerekir. Bu bölümde, çokgenleri farklı teknikler kullanarak nasıl doldurabileceğimizi göreceğiz.
Tarama Çizgisi Algoritması
Bu algoritma, tarama çizgisini çokgen kenarlarla keserek çalışır ve çokgeni kesişim çiftleri arasında doldurur. Aşağıdaki adımlar, bu algoritmanın nasıl çalıştığını göstermektedir.
Step 1 - Verilen çokgenden Ymin ve Ymax'ı bulun.
Step 2- ScanLine, Ymin'den Ymax'a kadar poligonun her kenarıyla kesişir. Çokgenin her kesişme noktasını adlandırın. Yukarıda gösterilen şekle göre p0, p1, p2, p3 olarak adlandırılırlar.
Step 3 - Kesişme noktasını artan X koordinatına göre sıralayın, yani (p0, p1), (p1, p2) ve (p2, p3).
Step 4 - Çokgenlerin içindeki tüm koordinat çiftlerini doldurun ve alternatif çiftleri göz ardı edin.
Taşkın Doldurma Algoritması
Bazen alanı ve sınırını farklı renklerle doldurmak istediğimiz bir nesneye rastlıyoruz. Bu tür nesneleri, sınır doldurma algoritmasında olduğu gibi belirli sınır rengini aramak yerine, belirli bir iç renkle boyayabiliriz.
Nesnenin sınırına güvenmek yerine, dolgu rengine güvenir. Başka bir deyişle, nesnenin iç rengini dolgu rengiyle değiştirir. Orijinal iç rengin artık pikselleri kalmadığında, algoritma tamamlanır.
Bir kez daha, bu algoritma pikselleri doldurmak için Four-connect veya Sekiz-bağlantı yöntemine dayanır. Ancak sınır rengini aramak yerine, iç mekanın bir parçası olan tüm bitişik pikselleri arıyor.
Sınır Doldurma Algoritması
Sınır doldurma algoritması, adı olarak çalışır. Bu algoritma, bir nesnenin içindeki bir noktayı seçer ve nesnenin sınırına ulaşana kadar doldurmaya başlar. Bu algoritmanın çalışması için sınırın rengi ve doldurduğumuz renk farklı olmalıdır.
Bu algoritmada, sınırın renginin tüm nesne için aynı olduğunu varsayıyoruz. Sınır doldurma algoritması 4 bağlantılı pikseller veya 8 bağlantılı pikseller ile uygulanabilir.
4 Bağlantılı Çokgen
Bu teknikte şekilde gösterildiği gibi 4 bağlantılı pikseller kullanılır. Pikselleri mevcut piksellerin üstüne, altına, sağına ve soluna koyuyoruz ve bu işlem farklı renkte bir sınır bulana kadar devam edecek.
Algoritma
Step 1 - Tohum noktası (seedx, seedy), fcolor ve dcol değerini başlatın.
Step 2 - Poligonun sınır değerlerini tanımlayın.
Step 3 - Geçerli tohum noktasının varsayılan renk olup olmadığını kontrol edin, ardından sınır piksellerine ulaşana kadar 4. ve 5. adımları tekrarlayın.
If getpixel(x, y) = dcol then repeat step 4 and 5Step 4 - Tohum noktasındaki dolgu rengiyle varsayılan rengi değiştirin.
setPixel(seedx, seedy, fcol)Step 5 - Prosedürü dört mahalle noktasıyla yinelemeli olarak izleyin.
FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)Step 6 - Çıkış
Bu teknikte bir sorun var. Tüm bölgeyi doldurmaya çalıştığımız durumu aşağıda gösterilen şekilde düşünün. Burada görüntü sadece kısmen doldurulur. Bu gibi durumlarda 4 bağlantılı piksel tekniği kullanılamaz.
8-Bağlı Çokgen
Bu teknikte şekilde gösterildiği gibi 8 bağlantılı pikseller kullanılır. 4 bağlantılı teknikte yaptığımız gibi pikselleri mevcut piksellerin üstüne, altına, sağına ve soluna koyuyoruz.
Buna ek olarak, mevcut pikselin tüm alanı kapsanacak şekilde pikselleri köşegenlere de yerleştiriyoruz. Bu süreç farklı renkte bir sınır bulana kadar devam edecek.
Algoritma
Step 1 - Tohum noktası (seedx, seedy), fcolor ve dcol değerini başlatın.
Step 2 - Poligonun sınır değerlerini tanımlayın.
Step 3 - Geçerli tohum noktasının varsayılan renk olup olmadığını kontrol edin, ardından sınır piksellerine ulaşana kadar 4. ve 5. adımları tekrarlayın
If getpixel(x,y) = dcol then repeat step 4 and 5Step 4 - Tohum noktasındaki dolgu rengiyle varsayılan rengi değiştirin.
setPixel(seedx, seedy, fcol)Step 5 - Prosedürü dört mahalle noktasıyla yinelemeli olarak izleyin
FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx, seedy + 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy - 1, fcol, dcol)Step 6 - Çıkış
4 bağlantılı piksel tekniği, 8 bağlantılı teknikte olmayacak şekilde aşağıdaki şekilde işaretlenen alanı doldurmada başarısız oldu.
İç-Dış Test
Bu yöntem aynı zamanda counting number method. Bir nesneyi doldururken, genellikle belirli bir noktanın nesnenin içinde mi yoksa dışında mı olduğunu belirlememiz gerekir. Belirli bir noktanın bir nesnenin içinde mi yoksa dışında mı olduğunu belirleyebileceğimiz iki yöntem vardır.
- Tek-Çift Kuralı
- Sıfır olmayan sargı numarası kuralı
Tek-Çift Kuralı
Bu teknikte, çizgi boyunca herhangi bir noktadan (x, y) sonsuza kadar geçen kenarı sayacağız. Etkileşimlerin sayısı tekse, (x, y) noktası bir iç noktadır; ve etkileşim sayısı çift ise, (x, y) noktası bir dış noktadır. Aşağıdaki örnek bu kavramı tasvir etmektedir.
Yukarıdaki şekilden, (x, y) noktasından, sol taraftaki etkileşim noktası sayısının 5 ve sağ taraftaki etkileşim noktasının 3 olduğunu görebiliriz. Her iki uçtan da etkileşim noktalarının sayısı tuhaftır. nokta, nesne içinde değerlendirilir.
Sıfır Olmayan Sargı Numarası Kuralı
Bu yöntem, verilen noktanın iç olup olmadığını test etmek için basit çokgenlerle de kullanılır. Bir pim ve bir lastik bant yardımı ile basitçe anlaşılabilir. Pimi poligonun kenarlarından birine sabitleyin ve lastik bandı buna bağlayın ve ardından lastik bandı poligonun kenarları boyunca gerdirin.
Poligonun tüm kenarları lastik bantla kaplandığında, test edilecek noktada sabitlenmiş olan pimi kontrol edin. Poligon içinde düşündüğümüz noktada en az bir rüzgar bulursak, aksi takdirde noktanın poligonun içinde olmadığını söyleyebiliriz.
Başka bir alternatif yöntemde, çokgenin tüm kenarlarına yön verin. Test edilecek noktadan X yönünün en soluna doğru bir tarama çizgisi çizin.
Yukarı doğru giden tüm kenarlara 1 değerini ve yön değeri olarak tüm diğer -1 değerini verin.
Tarama hattının içinden geçtiği kenar yönü değerlerini kontrol edin ve bunları toplayın.
Bu yön değerinin toplam toplamı sıfır değilse, test edilecek bu nokta bir interior point, aksi halde bir exterior point.
Yukarıdaki şekilde, tarama hattının geçtiği yön değerlerini topluyoruz ve ardından toplam 1 - 1 + 1 = 1; sıfır olmayan. Yani noktanın bir iç nokta olduğu söyleniyor.