ServerErr0r
uid=0(root)
Geometrik Algoritmalar İle İlgili Özet Bilgi
Günümüzde klasik mühendislik eğitiminin yanı sıra güncel teknolojiyi kullanma ve bilgisayar ortamında sayısal verileri kullanarak konuma ilişkin geometrik problemleri çözmen yeteneğinin kazandırılması önem kazanmaktadır. Genç mühendislerin ileride karşılaşacakları problemlerin çözümüne daha hazırlıklı olmaları ve dinamik bir yapı içerisinde farklı
disiplinlerle olan örtü alanlarını genişletmeleri kaçınılmaz bir zorunluluktur. Coğrafi Bilgi Sistemleri (CBS), Bilgisayarlı Grafik, CAD/CAM (Bilgisayar Destekli Tasarım ve Çizim ve Mekansal Modelleme) mühendislerimizin içinde yer almaları kaçınılmaz uygulama alanlarıdır. Bu alanlarda yaygın olarak kullanılan “Hesaplamalı Geometri” disiplininin mühendislerimiz tarafından tanınması ileride karşılaşacakları geometrik problemlerin çözümüne yardımcı olacaktır. Bu makalede, Hesaplamalı Geometri ve içerdiği problemler hakkında genel bilgiler verilecek ve bir hesaplamalı geometri problemi olan nokta içerme (point-in-polygon) problemi için yaygın olarak kullanılan iki çözüm yöntemi sunulacaktır.
Konuya Giriş
Bilgi üretim ve iletişimin öneminin her geçen gün daha çok arttığı günümüzde teknolojik gelişmelere paralel olarak üniversiteler ve çeşitli meslek grupları kendilerini yenileme ve yeniden yapılanma ihtiyacı duymaktadır. Bu yapılanma içerisinde klasik mühendislik eğitiminin yanı sıra, güncel teknolojiyi kullanma becerisi ve bilgisayar ortamında sayısal verileri kullanarak geometrik problemlerin çözümüne ilişkin bilgi önem kazanmaktadır. Ülkemizdeki kamu ve özel sektörün pratikte karşılaştıkları mesleki problemleri çözme gereksinimleri, yetişmiş mühendislerin kişisel yönlenmelerine ve bilgi birikimlerine bağlı olarak karşılanabilmektedir. Ülkemizdeki meslek içi eğitimin yetersizliği nedeniyle bu yükün büyük kısmını yeni yetişen mühendislerin taşıyacağı bir gerçektir. Yetişen gençlerin ileride karşılaşacakları problemlerin çözümüne daha hazırlıklı olmaları ve dinamik bir yapı içerisinde farklı disiplinlerle olan örtü alanlarını genişletmeleri bir zorunluluktur. Mühendislerimiz için, Coğrafi Bilgi Sistemleri, Bilgisayarlı Grafik, Bilgisayar Destekli Tasarım ve Çizim ile Mekansal Modelleme, içinde yer almaları kaçınılmaz uygulama alanlarıdır. Bu alanlarda yaygın olarak kullanılan “Hesaplamalı Geometri”nin mühendislerimiz tarafından tanınması ve ilgi alanı olarak görülmesi karşılaşacakları geometrik problemlerin çözümüne büyük katkı sağlayacaktır. Bu makalede, bu ihtiyaç doğrultusunda Hesaplamalı eometri hakkında genel bir fikir vermek ve konuyla ilgili bir perspektif çizmek amaçlanmıştır.
Hesaplamalı Geometri
Hesaplamalı geometrinin temeli analitik geometriye dayanmaktadır. 1970’li yıllarda hesaplamalı geometrinin içerdiği bir çok problemle ilgilenilmiş fakat konu ayrı bir disiplin olarak ele alınmamıştır. “Hesaplamalı Geometri” kavramının bir disiplin olarak düşünülmeye başlanması 1980’li yıllarda olmuştur. Bilgisayar olanaklarının artmasına paralel olarak bilgisayar programcılarının konuya ihtiyacı ve ilgisi artmıştır. Bilimsel bildiri ve makaleler düzeyinde ele alınmış konular kitap içerikleri olmaya başlamıştır. Coğrafi Bilgi Sistemleri, Bilgisayarlı Grafik, Bilgisayar Destekli Tasarım ve Çizim ile Mekansal Modelleme konularının farklı disiplinler tarafından kullanılmaya başlamasıyla hesaplamalı geometrinin önemi artmıştır. Konu ile ilgili son yıllarda “Computational Geometry (Hesaplamalı Geometri)” adında yabancı dilde kitaplar yazılmış ve yine bu isimle anılan uluslararası bilimsel dergiler çıkartılmıştır. Bu konuda dilimizde yapılan yayın sayısı çok sınırlı düzeyde kalmış ve/veya geniş kitlelere ulaşamamıştır. Hesaplamalı geometri kavramının ne olduğu ve hangi disiplinler için gerekli olduğu hakkında ön bilgi edinilmesi için şu üç örnek verilebilir.
Üniversite kampüsünde yürürken aniden bir telefon görüşmesi yapmanız gerektiğini fark ediyorsunuz. Kampüsde birçok telefon kulübesi var ve tabi ki siz en yakın olanına ulaşmak istiyorsunuz. Fakat, hangisi en yakın? Kampüsün neresinde olduğunuza ve en yakın telefon kulübesine bakabileceğiniz bir haritanızın olması ne kadar yararlı olurdu. Böyle bir harita, kampüsün her biri en yakın telefon kulübesini gösteren alt bölgelere ayrılmış bir şeklini içerirdi. Telefon konusu son derece önemli bir konu olmamasına karşın bu alt bölümlendirme bir çok uygulamada önemli rol oynayan geometrik bir yapının esaslarını tanımlamaktadır. Kampüsün bu alt bölümlendirilmesi “Voronoi diyagramı” olarak adlandırılmaktadır (Bkz.
Şekil-1). Voronoi diyagramı gibi geometrik yapıların hesaplanması geometrik algoritmalar gerektirmektedir. Bu tür algoritmalar hesaplamalı geometrinin bir konusudur.
İkinci bir örnek: Telefona ulaştığınızı varsayalım. Elinizdeki kampüs haritasıyla en yakın telefona ulaşırken muhtemelen zorluklarla karşılaştınız. Karşınıza duvarlar veya diğer objeler çıktı. Aynı performansı gösterip telefona ulaşacak bir robotun programlanması çok daha zor olacaktır. Bu durumda problemin özü yine geometrik olacaktır. Verilen bir geometrik engeller gurubu var ve siz engellere takılmadan iki nokta arasındaki en kısa bağlantıyı aramaktasınız. “Hareket planlaması” (motion planning) olarak adlandırılan ve Şekil-2’de gösterilen bu problemin çözümü robotikde çok önemli bir yer tutmaktadır.
Üçüncü bir örnek: Bir değil iki haritanız olduğunu varsayalım. Birinde çeşitli binalar ve içerdiği telefon kulübeleri diğerinde ise yollar ve kampüs tanımlanmış. Telefona olan hareketimizi planlarken bu haritaları üst üste bindirmemiz yani iki haritadaki bilgileri birleştirmemiz gerekecektir. Haritaların örtüştürülmesi (overlay) Coğrafi Bilgi Sistemleri’nin temel işlemlerinden biridir. Bu işlem bir haritadaki objelerin konumlarının diğer harita üzerinde konumlandırılmasını, çeşitli özelliklerin kesişimlerinin hesabını ve buna benzer bir çok hesabı gerektirecektir. Bu problemler de hesaplamalı geometrinin bir alt konusudur. Yukarıdaki örneklerden de anlaşılacağı gibi Coğrafi Bilgi Sistemleri, Bilgisayarlı Grafik, Robotik, Bilgisayar Destekli Tasarım ve Bilgisayar Destekli Modelleme, hesaplamalı geometrinin en yaygın olarak kullanıldığı alanlardır. Robotik göz ardı edilirse diğer tüm disiplinler, meslektaşlarımızın şimdi ve gelecekteki vazgeçilmez uygulama alanları arasında olacaktır.
Hesaplamalı Geometri Problemleri
Hesaplamalı Geometrinin içerdiği problemler sıralandığında uygulama alanları daha iyi anlaşılacaktır. Dışbükey çerçeve, kesişim, nokta içerme, komşuluk, üçgenleme, sorgulama ve arama problemleri hesaplamalı geometride en yaygın olarak kullanılan problemlerdir. Söz konusu problemler farklı başlıklar altında sınıflandırılabilir. Problemler bu çalışmada, 5 grup altında toplanmış ve aşağıdaki biçimde sıralanmıştır:
1. Dışbükey Çerçeve, Dışbükey Kabuk Problemleri
Verilen n noktalı bir S kümesinin d boyutlu uzayda dışbükey kabuğunun (iki boyutta dışbükey çerçeve) bulunması. Dışbükey kabuk (convex hull) bir nokta kümesini içine alan en küçük dışbükey kümedir. Bir veri kümesindeki bütün olası (P ve Q) nokta çiftini birleştirdiğinizde PQ doğru parçası tamamen nokta kümesi içinde kalıyorsa o kümeye dışbükey (convex) küme, aksi durumda dışbükey olmayan (non-convex) küme denir (Bkz. Şekil-3).
Verilen ayrık iki dışbükey çokgen (polygon) P ve Q’ nun ortak dışbükey çerçevesinin bulunması (Bkz. Şekil-4)
Verilen n noktalı dışbükey bir çokgenin (P) bir u noktasından geçen destekleyici (supporting) doğrularının bulunması (Bkz. Şekil-5)
Düzlemde verilen n noktalı basit (dışbükey ve yıldız şekilli olmayan) bir çokgenin dışbükey çerçevesinin bulunması (Bkz. Şekil-6)
2. Kesişim Problemleri
~ Verilen iki dışbükey çokgen P ve Q’ nun kesişiminin bulunması
~ Verilen iki yıldız şekilli çokgen P ve Q’ nun kesişiminin bulunması
~ Düzlemde verilen n doğru parçasından herhangi ikisinin kesişip kesişmediğinin belirlenmesi
~ Verilen iki basit çokgenin kesişip kesişmediğinin belirlenmesi
~ Verilen bir doğru parçaları kümesinde kesişen tüm çiftlerin bulunması,
~ Düzlemde verilen n yarı düzlemin ortak kesişimlerinin bulunması (Bkz. Şekil-7)
~ Verilen iki dışbükey çokyüzlü (polihedron) P ve Q’ nun kesişiminin bulunması
~ Kenarları koordinat eksenlerine paralel dikdörtgenlerin kesişimlerinin bulunması
~ Düzlemde verilen bir doğru parçası kümesi içerisinden belirli bir dikdörtgeni kesmeyenlerin bulunması
~ Uzayda verilen bir obje kümesi ile sorgulanan bir objenin kesişiminin sorgulanması
3. İçerme Problemleri
~ Kenarları koordinat eksenlerine paralel dikdörtgenlerden birbirlerini içerenlerin bulunması
~ Verilen iki çokgenden Q’nun P’ yi içene alıp alamayacağının belirlenmesi
~ Düzlemde verilen bir çokgen kümesi ve bunların dışında bir q noktası düşünürsek q noktasından görülebilen çokgen kenarlarının belirlenmesi
~ Düzlemde verilen bir nokta kümesi içerisinden belirli bir dikdörtgen içinde yer alan noktaların bulunması
~ Düzlemde verilen bir nokta kümesi içerisinden belirli bir çokgen içinde yer alan noktaların bulunması
~ Düzlemde verilen bir nokta kümesi içerisinden yarıçapı ve merkezi belirli bir daire içinde yer alan noktaların bulunması
~ Düzlemde verilen bir alt bölümlendirme içinde sorgulanan noktayı içeren alt bölümün bulunması
~ Bir noktanın bir çokgen içinde olup olmadığının bulunması
~ Verilen iki nokta kümesi arasından geçerek, kümeyi iki parçaya ayıracak bir doğru parçasının olup olmadığının belirlenmesi
~ Düzlemde verilen bir nokta kümesini içeren en küçük dairenin belirlenmesi (Bkz. Şekil-8)
~ Düzlemde verilen bir nokta kümesini içeren en küçük dikdörtgenin belirlenmesi
~ Düzlemde verilen bir nokta kümesini içeren en küçük üçgenin belirlenmesi
~ Düzlemde verilen bir nokta kümesi içinde oluşabilecek en büyük boş dairenin belirlenmesi (Bkz. Şekil-9)
~ Düzlemde verilen bir nokta kümesi içinde oluşabilecek en büyük boş dikdörtgenin belirlenmesi
4. Arama ve Komşuluk Problemleri
~ Düzlemde verilen bir nokta kümesi içerisinde birbirine en yakın iki noktanın bulunması
~ Düzlemde verilen bir nokta kümesi içerisinde birbirine en uzak iki noktanın bulunması
~ Düzlemde verilen bir nokta kümesi içerisinde bir noktaya en yakın noktanın bulunması
~ Düzlemde verilen bir nokta kümesi içerisinde bir noktaya en uzak noktanın bulunması
~ Düzlemde verilen dışbükey bir çerçevenin en yakın iki noktasının bulunması
~ Düzlemde verilen dışbükey bir çerçevenin en uzak iki noktasının bulunması
~ Düzlemde verilen bir nokta kümesinin Voronoi diyagramının oluşturulması
~ Düzlemde verilen iki nokta kümesi içerisinden birbirlerine en yakın nokta çiftinin bulunması
~ Düzlemde verilen iki nokta kümesi içerisinden birbirlerine en uzak nokta çiftinin bulunması.
~ Düzlemde verilen geometrik objeleri kesmeden iki nokta arasındaki en kısa yolun bulunması
5. Alt Bölümlendirme ve Üçgenleme Problemleri
~ Düzlemde verilen bir nokta kümesinin üçgenlenmesi (Bkz. Şekil-10)
~ Verilen basit bir çokgenin üçgenlenmesi yani üçgenlere bölünmesi
~ Verilen yıldız şekilli bir çokgenin üçgenlenmesi yani üçgenlere bölünmesi
~ Verilen basit bir çokgenin yıldız şekilli çokgenlere bölünmesi
~ Verilen basit bir çokgenin dışbükey çokgenlere bölünmesi
Burada dile getirilmemiş fakat uygulayıcılar tarafından karşılaşılmış farklı problemlerde söz konusu olabilir. Hesaplamalı Geometri yukarıda sayılan benzeri problemler için üretilen algoritmaları ve bu algoritmaların etkinliğini konu edinen bir disiplindir. Algoritmalar için kesinlik, yani olası tüm özel durumları dikkate alabilmesi ve çözümü gerçekleştirme sürelerinin veri sayısına olan bağımlılığının daha az olması, onların etkinliğini arttıran önemli özelliklerdir.
4. Bir Hesaplamalı Geometri Problemi ve Çözüm Algoritmaları
Sık karşılaşılan bir Hesaplamalı Geometri problemi, düzlemde koordinatı bilinen bir Q noktasının köşe koordinatları bilinen n noktalı dışbükey bir P çokgeni içine düşüp düşmediğinin sorgulanmasıdır. Örneğin, bir üçgenler ağı üzerinde çalışırken ele alınan yeni bir noktanın hangi üçgen içine düştüğünün bulunması bu problem için iyi bir örnektir. Üçgen bazlı bir Sayısal Arazi Modeli (SAM) üzerinde lineer enterpolasyonla yükseklik enterpolasyonu yapılırken bu problem ile karşılaşılır. Problemin çözümü için literatürde önerilmiş bir çok algoritma vardır. Bunlardan en yaygın olarak kullanılan ikisi, “Çift-Tek (Even-Odd) Yöntemi” ve “Eksi-Artı (Minus-Plus) Yöntemi” dir.
A. Çift-Tek Yöntemi
Yöntemde, bir ucu sorgulanan Q noktası diğer ucu çokgen dışında olduğu kesin olarak bilinen E noktası olan QE doğru parçası ile çokgenin kesişim noktaları sayılır. Bu sayı çift ise Q noktası P çokgeninin dışındadır. Hiç kesişim olmaması da çift sayı anlamına geleceğinden, nokta yine dışarıdadır. Kesişim sayısı tek ise, nokta çokgen içindedir. E noktası koordinat sisteminin orijini seçilirse veya QE doğru parçası x yada y eksenine paralel olarak seçilirse, kesişimlerin sorgulanması daha kolay olacaktır.
Sorgulanan Q noktasının koordinatları ( xq , yq ), P çokgeninin ardışık iki noktasının koordinatları ( x1, y1), ( x2 , y2 ) ve E noktasının koordinatları ( xe , ye ) olsun. 12 ve QE doğrularının denklemleri;
a1 = ( y1 − y2 ) , b1 = (x2 − x1) , c1 = (x1y2 − y1x2 ) (1a,b,c)
a2 = ( yq − ye ) , b2 = (xe − xq ) , c2 = (xq ye − yq xe ) (2a,b,c)
kısaltmaları kullanılarak (3) ve (4) eşitlikleri ile yazılabilir.
a1x + b1y + c1 = 0 (3)
a2 x + b2 y + c2 = 0 (4)
İki doğrunun I kesişim noktasının koordinatları (3) ve (4) eşitliklerinin beraber çözümünden elde edilir.
Aynı düzlemde bulunan bütün doğrular paralel olmadığı sürece birbirlerini keseceği için doğru parçalarının uzanımında gerçekleşen bir kesişim olup olmadığının anlaşılması amacıyla (5) eşitliğinden bulunan ( xi , yi ) koordinatlarının (1 ve 2) ve (Q ve E) noktaları arasında yer alıp almadığı kontrol edilir. Doğru parçalarının uzanımında gerçekleşen sanal kesişimler sayılmayacaktır. Bu yöntem, dışbükey olmayan çokgenler için de geçerli olan genel bir algoritmadır.
B. Eksi-Artı Yöntemi
P çokgeninin bütün noktalarının saat akrebi dönüş yönünde numaralandığını varsayalım (Bkz. Şekil-11). Eğer sorgulanan Q noktası bütün çokgen kenarlarının (12, 23, 34 ,.., n −1n ve n1) sağında ise nokta çokgen içerisindedir. Q noktası kenarlardan herhangi birinin solunda ise, Q çokgenin dışındadır. Numaralama saat akrebi dönüş yönünün tersinde yapılmış ise sağ ve sol yönleri yer değiştirecektir. Bir noktanın, bir doğrunun sağında veya solunda olduğu nasıl belirlenecektir? Bunun için önerilmiş çözüm yollarından ikisi, doğru denklemi ve alan yöntemidir.
B.1. Doğru Denklemi
Q noktası 12 doğru parçası üzerinde ise ( xq , yq ) koordinatları (6) eşitliğini sağlamalıdır;
a1xq + b1yq + c1 = 0 (6)
Aksi durumda (6) eşitliğinin sol tarafı pozitif (+) veya negatif (–) bir değer alacaktır. Pozitif (+) değer Q noktasının12 doğru parçasının sağında olduğunu, negatif (-) değer ise solunda olduğunu gösterir (Bkz. Şekil-12).
B.2. Alan Yöntemi
Yatay düzlem üzerinde bir üçgenin alanı, köşe noktalarının koordinatları kullanılarak 3. dereceden bir determinant ile ifade edilebilir.
Determinantın işaretinden noktanın sağda mı yoksa solda mı olduğu anlaşılabilir. Pozitif işaret Q noktasının 12 doğrusunun sağında olduğunu, negatif işaret ise solunda olduğunu gösterecektir.
5. Sonuç
Coğrafi Bilgi Sistemleri, Bilgisayarlı Grafik ve CAD/CAM (Bilgisayar Destekli Tasarım ve Çizim ile Mekansal Modelleme); Jeodezi ve Fotogrametri mühendislerinin içinde yer almaları kaçınılmaz uygulama alanlarıdır. Genç mühendislerin ileride karşılaşacakları problemlerin çözümüne hazırlıklı olmaları ve dinamik bir yapı içerisinde farklı disiplinlerle olan örtü alanlarını genişletmeleri bir zorunluluk olarak görülmektedir. Bu nedenle, konuma ilişkin geometrik problemleri çözme bilgi ve becerisinin kazandırılması önem kazanmaktadır.
Bu alanlarda yaygın olarak kullanılan “Hesaplamalı Geometri” disiplininin mühendislerimiz tarafından tanınması ve ilgi alanı olarak görülmesi, gelecekte karşılaşacakları geometrik problemlerin çözümüne büyük katkılar sağlayacaktır. Yurt dışında konu ile ilgili çok sayıda makale ve kitap bulunmasına karşın, Türkçe yapılan yayın sayısı çok azdır. Türkçe yayınların sayısı arttırılmalı, üniversitelerimiz ders içeriklerinde konuya yer vermeli ve hatta bu isimde dersler açılmalıdır. Ayrıca, meslek içi eğitimin etkili olduğu kurumlarda da, "Hesaplamalı Geometri" konusu göz ardı edilmemelidir.
Günümüzde klasik mühendislik eğitiminin yanı sıra güncel teknolojiyi kullanma ve bilgisayar ortamında sayısal verileri kullanarak konuma ilişkin geometrik problemleri çözmen yeteneğinin kazandırılması önem kazanmaktadır. Genç mühendislerin ileride karşılaşacakları problemlerin çözümüne daha hazırlıklı olmaları ve dinamik bir yapı içerisinde farklı
disiplinlerle olan örtü alanlarını genişletmeleri kaçınılmaz bir zorunluluktur. Coğrafi Bilgi Sistemleri (CBS), Bilgisayarlı Grafik, CAD/CAM (Bilgisayar Destekli Tasarım ve Çizim ve Mekansal Modelleme) mühendislerimizin içinde yer almaları kaçınılmaz uygulama alanlarıdır. Bu alanlarda yaygın olarak kullanılan “Hesaplamalı Geometri” disiplininin mühendislerimiz tarafından tanınması ileride karşılaşacakları geometrik problemlerin çözümüne yardımcı olacaktır. Bu makalede, Hesaplamalı Geometri ve içerdiği problemler hakkında genel bilgiler verilecek ve bir hesaplamalı geometri problemi olan nokta içerme (point-in-polygon) problemi için yaygın olarak kullanılan iki çözüm yöntemi sunulacaktır.
Konuya Giriş
Bilgi üretim ve iletişimin öneminin her geçen gün daha çok arttığı günümüzde teknolojik gelişmelere paralel olarak üniversiteler ve çeşitli meslek grupları kendilerini yenileme ve yeniden yapılanma ihtiyacı duymaktadır. Bu yapılanma içerisinde klasik mühendislik eğitiminin yanı sıra, güncel teknolojiyi kullanma becerisi ve bilgisayar ortamında sayısal verileri kullanarak geometrik problemlerin çözümüne ilişkin bilgi önem kazanmaktadır. Ülkemizdeki kamu ve özel sektörün pratikte karşılaştıkları mesleki problemleri çözme gereksinimleri, yetişmiş mühendislerin kişisel yönlenmelerine ve bilgi birikimlerine bağlı olarak karşılanabilmektedir. Ülkemizdeki meslek içi eğitimin yetersizliği nedeniyle bu yükün büyük kısmını yeni yetişen mühendislerin taşıyacağı bir gerçektir. Yetişen gençlerin ileride karşılaşacakları problemlerin çözümüne daha hazırlıklı olmaları ve dinamik bir yapı içerisinde farklı disiplinlerle olan örtü alanlarını genişletmeleri bir zorunluluktur. Mühendislerimiz için, Coğrafi Bilgi Sistemleri, Bilgisayarlı Grafik, Bilgisayar Destekli Tasarım ve Çizim ile Mekansal Modelleme, içinde yer almaları kaçınılmaz uygulama alanlarıdır. Bu alanlarda yaygın olarak kullanılan “Hesaplamalı Geometri”nin mühendislerimiz tarafından tanınması ve ilgi alanı olarak görülmesi karşılaşacakları geometrik problemlerin çözümüne büyük katkı sağlayacaktır. Bu makalede, bu ihtiyaç doğrultusunda Hesaplamalı eometri hakkında genel bir fikir vermek ve konuyla ilgili bir perspektif çizmek amaçlanmıştır.
Hesaplamalı Geometri
Hesaplamalı geometrinin temeli analitik geometriye dayanmaktadır. 1970’li yıllarda hesaplamalı geometrinin içerdiği bir çok problemle ilgilenilmiş fakat konu ayrı bir disiplin olarak ele alınmamıştır. “Hesaplamalı Geometri” kavramının bir disiplin olarak düşünülmeye başlanması 1980’li yıllarda olmuştur. Bilgisayar olanaklarının artmasına paralel olarak bilgisayar programcılarının konuya ihtiyacı ve ilgisi artmıştır. Bilimsel bildiri ve makaleler düzeyinde ele alınmış konular kitap içerikleri olmaya başlamıştır. Coğrafi Bilgi Sistemleri, Bilgisayarlı Grafik, Bilgisayar Destekli Tasarım ve Çizim ile Mekansal Modelleme konularının farklı disiplinler tarafından kullanılmaya başlamasıyla hesaplamalı geometrinin önemi artmıştır. Konu ile ilgili son yıllarda “Computational Geometry (Hesaplamalı Geometri)” adında yabancı dilde kitaplar yazılmış ve yine bu isimle anılan uluslararası bilimsel dergiler çıkartılmıştır. Bu konuda dilimizde yapılan yayın sayısı çok sınırlı düzeyde kalmış ve/veya geniş kitlelere ulaşamamıştır. Hesaplamalı geometri kavramının ne olduğu ve hangi disiplinler için gerekli olduğu hakkında ön bilgi edinilmesi için şu üç örnek verilebilir.
Üniversite kampüsünde yürürken aniden bir telefon görüşmesi yapmanız gerektiğini fark ediyorsunuz. Kampüsde birçok telefon kulübesi var ve tabi ki siz en yakın olanına ulaşmak istiyorsunuz. Fakat, hangisi en yakın? Kampüsün neresinde olduğunuza ve en yakın telefon kulübesine bakabileceğiniz bir haritanızın olması ne kadar yararlı olurdu. Böyle bir harita, kampüsün her biri en yakın telefon kulübesini gösteren alt bölgelere ayrılmış bir şeklini içerirdi. Telefon konusu son derece önemli bir konu olmamasına karşın bu alt bölümlendirme bir çok uygulamada önemli rol oynayan geometrik bir yapının esaslarını tanımlamaktadır. Kampüsün bu alt bölümlendirilmesi “Voronoi diyagramı” olarak adlandırılmaktadır (Bkz.
Şekil-1). Voronoi diyagramı gibi geometrik yapıların hesaplanması geometrik algoritmalar gerektirmektedir. Bu tür algoritmalar hesaplamalı geometrinin bir konusudur.
İkinci bir örnek: Telefona ulaştığınızı varsayalım. Elinizdeki kampüs haritasıyla en yakın telefona ulaşırken muhtemelen zorluklarla karşılaştınız. Karşınıza duvarlar veya diğer objeler çıktı. Aynı performansı gösterip telefona ulaşacak bir robotun programlanması çok daha zor olacaktır. Bu durumda problemin özü yine geometrik olacaktır. Verilen bir geometrik engeller gurubu var ve siz engellere takılmadan iki nokta arasındaki en kısa bağlantıyı aramaktasınız. “Hareket planlaması” (motion planning) olarak adlandırılan ve Şekil-2’de gösterilen bu problemin çözümü robotikde çok önemli bir yer tutmaktadır.
Üçüncü bir örnek: Bir değil iki haritanız olduğunu varsayalım. Birinde çeşitli binalar ve içerdiği telefon kulübeleri diğerinde ise yollar ve kampüs tanımlanmış. Telefona olan hareketimizi planlarken bu haritaları üst üste bindirmemiz yani iki haritadaki bilgileri birleştirmemiz gerekecektir. Haritaların örtüştürülmesi (overlay) Coğrafi Bilgi Sistemleri’nin temel işlemlerinden biridir. Bu işlem bir haritadaki objelerin konumlarının diğer harita üzerinde konumlandırılmasını, çeşitli özelliklerin kesişimlerinin hesabını ve buna benzer bir çok hesabı gerektirecektir. Bu problemler de hesaplamalı geometrinin bir alt konusudur. Yukarıdaki örneklerden de anlaşılacağı gibi Coğrafi Bilgi Sistemleri, Bilgisayarlı Grafik, Robotik, Bilgisayar Destekli Tasarım ve Bilgisayar Destekli Modelleme, hesaplamalı geometrinin en yaygın olarak kullanıldığı alanlardır. Robotik göz ardı edilirse diğer tüm disiplinler, meslektaşlarımızın şimdi ve gelecekteki vazgeçilmez uygulama alanları arasında olacaktır.
Hesaplamalı Geometri Problemleri
Hesaplamalı Geometrinin içerdiği problemler sıralandığında uygulama alanları daha iyi anlaşılacaktır. Dışbükey çerçeve, kesişim, nokta içerme, komşuluk, üçgenleme, sorgulama ve arama problemleri hesaplamalı geometride en yaygın olarak kullanılan problemlerdir. Söz konusu problemler farklı başlıklar altında sınıflandırılabilir. Problemler bu çalışmada, 5 grup altında toplanmış ve aşağıdaki biçimde sıralanmıştır:
1. Dışbükey Çerçeve, Dışbükey Kabuk Problemleri
Verilen n noktalı bir S kümesinin d boyutlu uzayda dışbükey kabuğunun (iki boyutta dışbükey çerçeve) bulunması. Dışbükey kabuk (convex hull) bir nokta kümesini içine alan en küçük dışbükey kümedir. Bir veri kümesindeki bütün olası (P ve Q) nokta çiftini birleştirdiğinizde PQ doğru parçası tamamen nokta kümesi içinde kalıyorsa o kümeye dışbükey (convex) küme, aksi durumda dışbükey olmayan (non-convex) küme denir (Bkz. Şekil-3).
Verilen ayrık iki dışbükey çokgen (polygon) P ve Q’ nun ortak dışbükey çerçevesinin bulunması (Bkz. Şekil-4)
Verilen n noktalı dışbükey bir çokgenin (P) bir u noktasından geçen destekleyici (supporting) doğrularının bulunması (Bkz. Şekil-5)
Düzlemde verilen n noktalı basit (dışbükey ve yıldız şekilli olmayan) bir çokgenin dışbükey çerçevesinin bulunması (Bkz. Şekil-6)
2. Kesişim Problemleri
~ Verilen iki dışbükey çokgen P ve Q’ nun kesişiminin bulunması
~ Verilen iki yıldız şekilli çokgen P ve Q’ nun kesişiminin bulunması
~ Düzlemde verilen n doğru parçasından herhangi ikisinin kesişip kesişmediğinin belirlenmesi
~ Verilen iki basit çokgenin kesişip kesişmediğinin belirlenmesi
~ Verilen bir doğru parçaları kümesinde kesişen tüm çiftlerin bulunması,
~ Düzlemde verilen n yarı düzlemin ortak kesişimlerinin bulunması (Bkz. Şekil-7)
~ Verilen iki dışbükey çokyüzlü (polihedron) P ve Q’ nun kesişiminin bulunması
~ Kenarları koordinat eksenlerine paralel dikdörtgenlerin kesişimlerinin bulunması
~ Düzlemde verilen bir doğru parçası kümesi içerisinden belirli bir dikdörtgeni kesmeyenlerin bulunması
~ Uzayda verilen bir obje kümesi ile sorgulanan bir objenin kesişiminin sorgulanması
3. İçerme Problemleri
~ Kenarları koordinat eksenlerine paralel dikdörtgenlerden birbirlerini içerenlerin bulunması
~ Verilen iki çokgenden Q’nun P’ yi içene alıp alamayacağının belirlenmesi
~ Düzlemde verilen bir çokgen kümesi ve bunların dışında bir q noktası düşünürsek q noktasından görülebilen çokgen kenarlarının belirlenmesi
~ Düzlemde verilen bir nokta kümesi içerisinden belirli bir dikdörtgen içinde yer alan noktaların bulunması
~ Düzlemde verilen bir nokta kümesi içerisinden belirli bir çokgen içinde yer alan noktaların bulunması
~ Düzlemde verilen bir nokta kümesi içerisinden yarıçapı ve merkezi belirli bir daire içinde yer alan noktaların bulunması
~ Düzlemde verilen bir alt bölümlendirme içinde sorgulanan noktayı içeren alt bölümün bulunması
~ Bir noktanın bir çokgen içinde olup olmadığının bulunması
~ Verilen iki nokta kümesi arasından geçerek, kümeyi iki parçaya ayıracak bir doğru parçasının olup olmadığının belirlenmesi
~ Düzlemde verilen bir nokta kümesini içeren en küçük dairenin belirlenmesi (Bkz. Şekil-8)
~ Düzlemde verilen bir nokta kümesini içeren en küçük dikdörtgenin belirlenmesi
~ Düzlemde verilen bir nokta kümesini içeren en küçük üçgenin belirlenmesi
~ Düzlemde verilen bir nokta kümesi içinde oluşabilecek en büyük boş dairenin belirlenmesi (Bkz. Şekil-9)
~ Düzlemde verilen bir nokta kümesi içinde oluşabilecek en büyük boş dikdörtgenin belirlenmesi
4. Arama ve Komşuluk Problemleri
~ Düzlemde verilen bir nokta kümesi içerisinde birbirine en yakın iki noktanın bulunması
~ Düzlemde verilen bir nokta kümesi içerisinde birbirine en uzak iki noktanın bulunması
~ Düzlemde verilen bir nokta kümesi içerisinde bir noktaya en yakın noktanın bulunması
~ Düzlemde verilen bir nokta kümesi içerisinde bir noktaya en uzak noktanın bulunması
~ Düzlemde verilen dışbükey bir çerçevenin en yakın iki noktasının bulunması
~ Düzlemde verilen dışbükey bir çerçevenin en uzak iki noktasının bulunması
~ Düzlemde verilen bir nokta kümesinin Voronoi diyagramının oluşturulması
~ Düzlemde verilen iki nokta kümesi içerisinden birbirlerine en yakın nokta çiftinin bulunması
~ Düzlemde verilen iki nokta kümesi içerisinden birbirlerine en uzak nokta çiftinin bulunması.
~ Düzlemde verilen geometrik objeleri kesmeden iki nokta arasındaki en kısa yolun bulunması
5. Alt Bölümlendirme ve Üçgenleme Problemleri
~ Düzlemde verilen bir nokta kümesinin üçgenlenmesi (Bkz. Şekil-10)
~ Verilen basit bir çokgenin üçgenlenmesi yani üçgenlere bölünmesi
~ Verilen yıldız şekilli bir çokgenin üçgenlenmesi yani üçgenlere bölünmesi
~ Verilen basit bir çokgenin yıldız şekilli çokgenlere bölünmesi
~ Verilen basit bir çokgenin dışbükey çokgenlere bölünmesi
Burada dile getirilmemiş fakat uygulayıcılar tarafından karşılaşılmış farklı problemlerde söz konusu olabilir. Hesaplamalı Geometri yukarıda sayılan benzeri problemler için üretilen algoritmaları ve bu algoritmaların etkinliğini konu edinen bir disiplindir. Algoritmalar için kesinlik, yani olası tüm özel durumları dikkate alabilmesi ve çözümü gerçekleştirme sürelerinin veri sayısına olan bağımlılığının daha az olması, onların etkinliğini arttıran önemli özelliklerdir.
4. Bir Hesaplamalı Geometri Problemi ve Çözüm Algoritmaları
Sık karşılaşılan bir Hesaplamalı Geometri problemi, düzlemde koordinatı bilinen bir Q noktasının köşe koordinatları bilinen n noktalı dışbükey bir P çokgeni içine düşüp düşmediğinin sorgulanmasıdır. Örneğin, bir üçgenler ağı üzerinde çalışırken ele alınan yeni bir noktanın hangi üçgen içine düştüğünün bulunması bu problem için iyi bir örnektir. Üçgen bazlı bir Sayısal Arazi Modeli (SAM) üzerinde lineer enterpolasyonla yükseklik enterpolasyonu yapılırken bu problem ile karşılaşılır. Problemin çözümü için literatürde önerilmiş bir çok algoritma vardır. Bunlardan en yaygın olarak kullanılan ikisi, “Çift-Tek (Even-Odd) Yöntemi” ve “Eksi-Artı (Minus-Plus) Yöntemi” dir.
A. Çift-Tek Yöntemi
Yöntemde, bir ucu sorgulanan Q noktası diğer ucu çokgen dışında olduğu kesin olarak bilinen E noktası olan QE doğru parçası ile çokgenin kesişim noktaları sayılır. Bu sayı çift ise Q noktası P çokgeninin dışındadır. Hiç kesişim olmaması da çift sayı anlamına geleceğinden, nokta yine dışarıdadır. Kesişim sayısı tek ise, nokta çokgen içindedir. E noktası koordinat sisteminin orijini seçilirse veya QE doğru parçası x yada y eksenine paralel olarak seçilirse, kesişimlerin sorgulanması daha kolay olacaktır.
Sorgulanan Q noktasının koordinatları ( xq , yq ), P çokgeninin ardışık iki noktasının koordinatları ( x1, y1), ( x2 , y2 ) ve E noktasının koordinatları ( xe , ye ) olsun. 12 ve QE doğrularının denklemleri;
a1 = ( y1 − y2 ) , b1 = (x2 − x1) , c1 = (x1y2 − y1x2 ) (1a,b,c)
a2 = ( yq − ye ) , b2 = (xe − xq ) , c2 = (xq ye − yq xe ) (2a,b,c)
kısaltmaları kullanılarak (3) ve (4) eşitlikleri ile yazılabilir.
a1x + b1y + c1 = 0 (3)
a2 x + b2 y + c2 = 0 (4)
İki doğrunun I kesişim noktasının koordinatları (3) ve (4) eşitliklerinin beraber çözümünden elde edilir.
Aynı düzlemde bulunan bütün doğrular paralel olmadığı sürece birbirlerini keseceği için doğru parçalarının uzanımında gerçekleşen bir kesişim olup olmadığının anlaşılması amacıyla (5) eşitliğinden bulunan ( xi , yi ) koordinatlarının (1 ve 2) ve (Q ve E) noktaları arasında yer alıp almadığı kontrol edilir. Doğru parçalarının uzanımında gerçekleşen sanal kesişimler sayılmayacaktır. Bu yöntem, dışbükey olmayan çokgenler için de geçerli olan genel bir algoritmadır.
B. Eksi-Artı Yöntemi
P çokgeninin bütün noktalarının saat akrebi dönüş yönünde numaralandığını varsayalım (Bkz. Şekil-11). Eğer sorgulanan Q noktası bütün çokgen kenarlarının (12, 23, 34 ,.., n −1n ve n1) sağında ise nokta çokgen içerisindedir. Q noktası kenarlardan herhangi birinin solunda ise, Q çokgenin dışındadır. Numaralama saat akrebi dönüş yönünün tersinde yapılmış ise sağ ve sol yönleri yer değiştirecektir. Bir noktanın, bir doğrunun sağında veya solunda olduğu nasıl belirlenecektir? Bunun için önerilmiş çözüm yollarından ikisi, doğru denklemi ve alan yöntemidir.
B.1. Doğru Denklemi
Q noktası 12 doğru parçası üzerinde ise ( xq , yq ) koordinatları (6) eşitliğini sağlamalıdır;
a1xq + b1yq + c1 = 0 (6)
Aksi durumda (6) eşitliğinin sol tarafı pozitif (+) veya negatif (–) bir değer alacaktır. Pozitif (+) değer Q noktasının12 doğru parçasının sağında olduğunu, negatif (-) değer ise solunda olduğunu gösterir (Bkz. Şekil-12).
B.2. Alan Yöntemi
Yatay düzlem üzerinde bir üçgenin alanı, köşe noktalarının koordinatları kullanılarak 3. dereceden bir determinant ile ifade edilebilir.
Determinantın işaretinden noktanın sağda mı yoksa solda mı olduğu anlaşılabilir. Pozitif işaret Q noktasının 12 doğrusunun sağında olduğunu, negatif işaret ise solunda olduğunu gösterecektir.
5. Sonuç
Coğrafi Bilgi Sistemleri, Bilgisayarlı Grafik ve CAD/CAM (Bilgisayar Destekli Tasarım ve Çizim ile Mekansal Modelleme); Jeodezi ve Fotogrametri mühendislerinin içinde yer almaları kaçınılmaz uygulama alanlarıdır. Genç mühendislerin ileride karşılaşacakları problemlerin çözümüne hazırlıklı olmaları ve dinamik bir yapı içerisinde farklı disiplinlerle olan örtü alanlarını genişletmeleri bir zorunluluk olarak görülmektedir. Bu nedenle, konuma ilişkin geometrik problemleri çözme bilgi ve becerisinin kazandırılması önem kazanmaktadır.
Bu alanlarda yaygın olarak kullanılan “Hesaplamalı Geometri” disiplininin mühendislerimiz tarafından tanınması ve ilgi alanı olarak görülmesi, gelecekte karşılaşacakları geometrik problemlerin çözümüne büyük katkılar sağlayacaktır. Yurt dışında konu ile ilgili çok sayıda makale ve kitap bulunmasına karşın, Türkçe yapılan yayın sayısı çok azdır. Türkçe yayınların sayısı arttırılmalı, üniversitelerimiz ders içeriklerinde konuya yer vermeli ve hatta bu isimde dersler açılmalıdır. Ayrıca, meslek içi eğitimin etkili olduğu kurumlarda da, "Hesaplamalı Geometri" konusu göz ardı edilmemelidir.
