Polygon packing approach to disconnected graph layout
Ayrışık çizge yerleştiriminde poligon paketleme yaklaşımı
- Tez No: 139282
- Danışmanlar: YRD. DOÇ. DR. UĞUR DOĞRUSÖZ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Çizge yerleştirimi, Aynk çizge yerleştirimi, İki boyutlu paketleme. iv, Graph Layout, Disconnected Graph Layout, Two-Dimensional Packing. in
- Yıl: 2003
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 55
Özet
ÖZET AYRIŞIK ÇİZGE YERLEŞTİMİNDE POLİGON PAKETLEME YAKLAŞIMI Cihad Baskoy Bilgisayar Mühendisliği, Yüksek Lisans Tez Yöneticisi: Yrd. Doç. Dr. Uğur Doğrusöz Ocak, 2003 Çizge yerleştirimi konusu, Bilgisayar Bilimlerinde son birkaç on yıl içerisinde önem kazanmıştır. Kullanım alanları oldukça geniş olmak ile beraber, veri yapılan, veritabanlan, yazılım mühendisliği, VLSI teknolojileri, elektrik mühendisliği, üretim planlaması, kimya ve biyoloji örnek olarak verilebilir. Yerleştirme algoritmalarının bir çoğu, çizgenin bağlaşık olduğunu varsayarak işlem yapmaktadır. Bununla birlikte, karşılaşılan çizgelerin ayrık olması durumunda kullanılabilecek algoritmalara ihtiyaç duyulmaktadır. İki boyutlu kap içerisine paketleme problemleri tekstil ve çelik endüstrilerinde geniş uygulama alanına sahiptir, örneğin çelik endüstrisinde, dikdörtgen plakalar üzerinde poligonsal şekillerin işaretlenmesi ve kesilmesi önemli bir problemdir. Bütün bu uygulamalardaki ana amaç, kullanılmayan alanın en aza indirimesi olarak özetlenebilir. Son zamanlarda, iki boyutlu paketleme algoritmaları, ayrık çizge yerleştirimi araştırmalarında, dikdörtgenler şeklinde tanımlanan ve bağlantılı olmayan çizge elemanlarını yüzey üzerine kaplamak için kullanılmaya başlanmıştır. Bu algoritmaların gereklerinde birisi, oluşturulacak yerleştirimde önceden tanımlanan boyut oranının korunmasıdır. Çizge yerleştirimi konusunda, elemanların polyomino'lar kullanılarak tanımlanması, hesaplama zamanlarını artırmakla birlikte daha doğru sonuçlar elde edilmesini sağlayan, yeni bir yaklaşımdır. Çizim performansı ve hesaplama zamanı arasındaki denge önemlidir. Bu çalışmada, çizge elemanlarının detaylı olarak tanımlanabilmesi için poligonlar kullanılmakta ve ayrık çizge yerleştirimini gerçekleştiren yeni bir algoritma sunulmaktadır, özetle, ayrık çizge yerleştirimlerinin iki boyutlu paketlenmesi için No-Fit poligon yaklaşımı uygulanmaktadır. Bu yeni yaklaşım kullanılarak elde edilen sonuçlar sunulmakta ve değerlendirilmektedir. Ayrıca bu sonuçların, önceki yaklaşımların sonuçlan karşılaştmlması yapılmaktadır.
Özet (Çeviri)
ABSTRACT POLYGON PACKING APPROACH TO DISCONNECTED GRAPH LAYOUT Cihad Başköy M.S. in Computer Engineering Supervisor: Asst. Prof. Uğur Doğrusöz January, 2003 Graph layout has become an important area of research in Computer Science for the last couple of decades. There is a wide range of applications for graph layout including data structures, databases, software engineering, VLSI technology, electrical engineering, production planning, chemistry, and biology. Most layout algorithms assume the graph to be connected. However, most graphs are disconnected and a method for putting the disconnected graph objects together is needed. Two-dimensional packing algorithms have wide area of application such as in the steel and textile industry. In steel industry, problems frequently occur when the need to stamp polygonal figures from a rectangular board arises. In the textile industry, similar problems exist. The aim is same: to maximize the use of the contiguous remainder of the board. Recently, two-dimensional packing has also been used in disconnected graph layout yielding algorithms that 'tile' the disconnected graph objects, which are represented by rectangles. These algorithms are also required to respect the specified aspect ratio for the final layout. A more recent approach to disconnected graph layout has been the use of polyominoes for representing the graph objects resulting in more accurate packings at the cost of increased execution times. In this thesis, we use polygons for a more accurate representation of graph objects and present new algorithms for disconnected graph layout. Specifically, we apply the No-Fit Polygon approach in two- dimensional packing to disconnected graph layout. We present and analyze the graph layouts resulting from our new approach and contrast the new approach with previous ones.
Benzer Tezler
- Parça yerleştirme algoritmalarının postal oluşturma problemine uygulanması
Başlık çevirisi yok
FİLİZ BUNYAK
Yüksek Lisans
Türkçe
1996
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ.DR. FÜSUN TUNALI (SEÇUK)
- Fully automated on-street parking spot detection with different deep learning methods
Farklı derin öğrenme yöntemleriyle tam otomatik cadde park yeri tespiti
EMRE ÇİÇEK
Doktora
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. SEZER GÖREN UĞURDAĞ
- İmalat sektöründe parça yerleştirme ve kesme probleminin optimizasyonu
Optimization of part placement and cutting problem in the manufacturing sector
HÜSEYİN FIRAT
Yüksek Lisans
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİnönü ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. DAVUT HANBAY
- Dikdörtgen bir plakadan dikdörtgen parçaların çıkartılmasında firenin minimizasyonu için bir algoritma
An algorithm to minimize the amount of loss, during the process of cutting rectangle out of polygon
TANJU ATAYLAR
Yüksek Lisans
Türkçe
1999
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGazi ÜniversitesiElektronik ve Bilgisayar Eğitimi Ana Bilim Dalı
PROF. DR. DOĞAN ÇALIKOĞLU
- Pararllel rendering algorithms for distributed-memory multicomputers
Çok işlemcili dağıtık hafızalı bilgisayarlarda paralel görüntüleme algoritmaları
TAHSİN MERTEFE KURÇ
Doktora
İngilizce
1997
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT