Vatti kırpma algoritması
Vatti kırpma algoritması,[1] bilgisayar grafiklerinde kullanılır. Rastgele sayıda köşesi olan ve rastgele bir şekilde oluşturulmuş hedef çokgenin, yine kendisi gibi rastgele oluşturulmuş başka bir rastgele çokgen ile kırpılmasını sağlar. Sutherland-Hodgman ve Weiler-Atherton algoritmalarının tersine, bu algoritma üzerinde çalışılacak şekillere kısıtlama getirmez. İçinde boşluk olan veya kendi kendini kesen poligonlarla çalışılabilinir. Algoritma genel olarak sadece 2B (2 Boyutlu) ortamda uygulanabilir.
Açıklama
[değiştir | kaynağı değiştir]Kırpmak direkt anlamda parçalamak-ayırmak da olsa, sözü edilen kırpma hedef çokgenle kırpma aracı olarak kullanılacak çokgenin alansal etkileşimidir. Çünkü kırpma algoritmaları sadece kesişim alanlarını bulmaya yaramaz. Aynı zamanda küme işlemlerinde olduğu gibi iki alan arasındaki farkları, birleşimleri veya birisinin içinde-birisinin dışında kalan alanı bulmaya yarar.
Vatti algoritması klasik biçimde hem kesen hem de kesilen çokgenin köşeleri ile ilgilenir; bunu en altta bulunan köşeden başlayarak en üste doğru tarayarak yapar. Bu yaklaşıma İngilizce "sweep line approach" adı verilir. Türkçeye süpürme yaklaşımı olarak geçer. Yani program yukarıya doğru tüm poligon köşelerini süpürerek tarar ve hayali yatay çizgiler, her bir poligonun köşesinden çıkarak alanları ayırır. Bu yöntem, problemi tarama çizgileri ile bölerek kolaylaştırır. Tarama çizgilerinin oluşturduğu tarama aralıkları sırayla en alttan en üste doğru işlenerek istenen işlem gerçekleştirilir.