POLYGONLARI ÜÇGENLERE BÖLME

Aşağıda anlatılan tüm bilgiler
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/twoears.html
adresinden alınmıştır.

KediCAD 3B de önüme çıkan en büyük sorun kullanıcının çizdiği bir çizimi opengl ekranına aktarırken çizimin bozulmasıydı. Çünkü openglye çizimi polygon olarak aktarmak gerekiyor ve opengl polygonları sadece dışbükeyse düzgünce çizebiliyor. Eğer çizimde içbükey noktalar varsa saçma sapan bir görüntü oluşuyor. Bunu engellemek için en iyi yöntem çizimi üçgenlere bölmek ve bu şekilde küçük polygonlar veya üçgenler(gl.triangles) olarak çizdirmek gerekiyor.
Buna kısaca üçgenlemek deniyor. Gelişigüzel bir çizimi üçgenlere bölmek zannedildiği kadar kolay değilmiş. bunun için bir kaç yöntem var.
Ben burada kulak kesme yöntemini anlatacağım. teorinin tam adı (The Two-Ears Theorem) iki kulak teorisi. Temelinde yatan mantık bir polygonda en az iki birbirini kesmeyen kulak vardır. En önemli eksikliği sadece basit polygonlarda geçerlidir.

Önce Basit Polygon Nedir?
Bir polygon kendisini kesmiyorsa buna Basit polygon denir. Cad çizimlerinde yükseltilen veya döndürülen bir kesit kesinlikle basit polygondur.

Kulak Nedir?
Herhangi bir noktanın önceki ve sonraki noktalarını çizgi ile birleştirdiğimiz zaman çizgi çizimin içinde kalıyorsa bu üç nokta polygonun bir kulağını oluşturur.

Şimdi teori bize her poligon da(üçgenler hariç) en az iki kulak olduğunu ve bunların birbirini kesmediğini söylüyor.

Bu durumda elimizdeki bir poligonun kulaklarını bulup sıra ile bunları poligondan çıkrırsak yeni oluşan poligona da aynı işlemi üçgen haline gelene kadar tekrarlarsak üçgenlere bölme işlemi basit poligon için sağlanmış olur.

Üçgenleme için kaynak kodları
Java için
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applet1.html

gambas3 için
http://www.mediafire.com/myfiles.php ucgen-0.0.9.tar.gz

adresinden indirebilirsiniz.