Çokgen Konveks mi Konkav mı ?

Selamlar,
Uzun zaman oldu...Programlama konusunda değişik bir işlemden bahsetmek istedim.
 Fare yardımıyla koyduğum noktalar ile oluşan kapalı geometrik şeklin konveks mi yoksa konkav mı olduğunu bulduralım...


 İlk olarak konveks ve konkav ne demek onu açıklamaya çalışayım. Bunların çok çeşitli tanımlarını bulmak mümkündür. Örneğin;

1 - çokgenin en az bir kenarının uzantısı çokgeni kesiyorsa şekil konkav ya da içbükey, kesmiyorsa dışbükey ya da konkvekstir.

2 - bir çokgenin içinde alınan her hangi iki nokta arasında çizilen doğru parçasına ait noktaların hepsi çokgenin içinde kalıyorsa şekil konveks, bir kısmı şeklin dışında kalıyorsa şekil konkavdır.

Bu tanımlar programlama kısmına pek uygun değildir (Bana göre). Algoritma geliştirme süreci sıkıntılı olabilir.Benim daha çok sevdiğim tanım

3 - eğer çokgenin iç açılarından en az bir tanesi 180 dereceden büyükse şekil konkav yani içbükey, eğer iç açılardan hiç biri 180 dereceden büyük değilse şekil konveks yani dışbükeydir.

Üç tanıma göre aşağıdaki iki şekli irdeleyelim.

Birinci tanıma göre;

Bura da  çokgeni oluşturan kenarları kırmızı kesik çizgiyle uzattım şekil 1 de görüldüğü gibi uzantılar şekli kesmiyor ya da şekle ait her hangi bir kenarı kesmiyor yani cokgenimiz konveks (dışbükey), şekil 2 de ise kesik çizgiler şekli bölüyor ya da herhangi bir kenarı kesiyor. Hatta 3 noktada kesiyor fakat şartın sağlanması için en az bir nokta yeterli. Bu durumda şekil 2 de ki çokgen konkav(içbükey).

İkinci tanıma göre;

Bu tanıma göre ise şekil 1 de her hangi iki noktayı birleştiren doğru parçasına ait bütün noktalar şeklin içinde kaldığı için şekil 1 deki çokgen konveks(dışbükey), şekil 2 de ise iki tane doğru parçası konveks diyebilmemiz için gereken şartları sağlasa da bir tane doğru parçasına ait noktaların bir kısmı şeklin dış gölgesinde kaldığı için (herhangi bir şartına uygun olarak) bu çokgen konkavdır.(içbükey)

Üçüncü tanıma göre;

Bu tanıma göre de şekil 1 konveks, şekil 2 konkav çıkacaktır.Çünkü tanıma göre düşündüğümüzde şekil 1 deki çokgenin iç bölgesinde kalan açıların hiç biri 180 dereceden büyük değildir. Bu yüzden konveks(dışbükey) çokgendir. Şekil 2 de ise iki tane 180 dereceden büyük açı vardır. En az bir tane olması konkav olabilmesine yeterli olduğu için şekil 2 deki çokgen konkav (içbükey) çokgendir.

Bu geometri bilgilerinden sonra gelelim programlama kısmına. Yazının başlarında da dediğim gibi bana daha kolay geldiği için 3. tanımdan yola çıkarak algoritmamı tasarladım.

İlk olarak elimizde noktalarımız olmalı diyelim ki elimizde 4 tane nokta var isimleri A, B, C, D olsun. Kendimize bu noktalar içinden bir başlanğıç noktası seçiyoruz. Örneğin ekrana koyduğumuz ya da elimizdeki ilk noktayı seçelim o da A noktası olsun.

Yine geometriden hatırladığımız üzere bir açı için doğrusal olmayan en az 3 nokta gerekli, bu yüzden elimizdeki noktaları üçerli gruplara ayırıyoruz. Fakat bu gruplandırmayı belli bir sistematiğe göre yapmamız gerekiyor. Yani ABC,DEF,... şeklinde yapamayız. Her nokta bir kere ortaya gelecek şekilde yazılmalı ki ortada kalan noktaya ait açıyı temsil etsin.Kısaca bu işlemi her nokta için şu şekilde yapmalıyız. (Noktalara A,B,C,D isimleri verdiğim için harf olarak yazacağım)

ABC, B noktasındaki açıyı

BCD, C noktasındaki açıyı

CDA, D noktasındaki açıyı

DAB, A noktasındaki açıyı

ifade edecek şekilde elimizdeki noktaları sınıflandırıyoruz.

Görüldüğü gibi elimizdeki nokta sayısı kadar açı olmak zorunda.

Daha sonra bu sınıfladığımız üçlü gruplar yardımıyla açılarımızı hesaplıyoruz.Bu hesap için ben kosinüs teoreminden yararlandım.

Burada önce a, b ve c uzunlukları hesaplanıp sonra beta açısı çekilir. Bu işlem her köşe için ardışık tekrarlandığında çokgendeki bütün köşelere ait açılar hesaplanmış olur. Daha sonra kontrol kısmına geçilir. 3. tanıma göre bu açılardan herhangi birinin 180 dereceden büyük olup olmadığına bakılır. Eğer büyük varsa çokgen konkav(içbükey), 180 dereceden büyük yoksa çokgen konvekstir.

Bu çalışmamın videosunu BURADAN izleyebilirsiniz.