Sunday, October 2, 2016

Geometry Problems

Kali ini kita akan membahas tentang geometry problems.

Computational Geometry adalah cabang dari ilmu komputer yang dikhususkan untuk mempelajari algoritma yang dapat dinyatakan dalam suatu geometri. Dengan kata lain yaitu studi tentang masalah geometris dari sudut pandang komputasi. Intinya adalah teknik-teknik untuk mendesain dan menganalisis algoritma geometrik.

Ilmu ini membahas tentang bagaimana membentuk poligon dari sekumpulan titik, pendeteksian suatu titik terhadap suatu poligon apakah titik itu ada dalam poligon atau tidak, proses pencarian suatu titik dalam range tertentu, yang nantinya akan diaplikasikan dalam proses pencarian sejumlah data, cara mencari titik-titik terluar, perpotongan garis dan mencari titik terdckat.

Tujuan mempelajari ilmu ini adalah bahwa algoritma geometri dapat digunakan untuk membantu manusia dalam menyelesaikan per-masalahan-permasalahan yang berhubungan dengan bentuk-bentuk geometri yang juga tentunya berhubungan dengan titik dan garis sebagai dasar dari bangun geometri.

Apa saja yang bisa diaplikasikan dari ilmu algoritma geometrik ini??

Banyak hal, berikut ini contoh-contohnya :

1. Computer Graphics

Kegunaan algoritma geometri yaitu untuk menggambarkan, membuat, dan memvisualisasikan dunia nyata yang kompleks ke dunia virtual. Seperti yang sering kita lihat di film-film, video games, atau simulasi virtual.
2. Shape Reconstruction
Yaitu merekonstruksi suatu objek 2D ke dalam model komputer 3D. Biasanya digunakan untuk pencitraan alat medis, mikroskop, geologi, dan lain-lain.
3. Computer Vision

Yaitu untuk pemulihan struktur 3D dari gambar 2D, terutama yang menggunakan informasi stereoscopic dan gerak. Pengaplikasian ini juga termasuk segmentasi citra untuk mengekstrak sebuah informasi tentang objek dalam sebuah adegan.

4. Geographical Information Systems

Pengaplikasian dalam bidang ini meliputi pemodelan dan perkiraan medan yang rumit, serta analisis dari klasifikasi lahan, perencanaan pembangunan, dan lainnya. Untuk sistem transportasi juga digunakan untuk perencanaan rute, pemantauan kepadatan lalu lintas, dan lain-lain.

5. Mesh Generation

Digunakan dalam pemodelan elemen hingga struktur teknik dan cairan (Hydro dan Aero) misalnya simulasi terowongan angin, peramalan cuaca, dan lain-lain. Mesh Generation adalah aspek geometri yang terkait dengan algoritma untuk membangun pemodelan baik pada objek 2D maupun 3D.

6. Robotics
Algoritma geometrik diperlukan untuk memecahkan masalah perencanaan gerak robot. Contoh, robot yang dikirimkan ke planet lain akan memerlukan visi komputer untuk merekonstruksi model geometri yang kemudian digunakan untuk perencanaan gerakan eksplorasi.
Nah, diatas sudah disebutkan kegunaan-kegunaan atau pengaplikasian algoritma geometri, karena segala sesuatu yang kita lihat dan kita sentuh memiliki aspek geometrik yang memungkinkan kita untuk memahami dunia kita. Saat ini hampir segala bidang usaha akan dipengaruhi oleh algoritma geometri. Jadi ilmu ini sangat penting untuk kita yang mempelajari analisis algoritma.

Apa saja masalah-masalah yang dapat diselesaikan dengan algoritma geometri?

Algoritma geometri menyelesaikan beberapa masalah. Berikut ini contoh-contohnya :

1. Representasi Objek Geometris
  • Titik, garis, segmen dan bidang 
  • Segitiga, tetrahedron, poligon, dan polihedron 
  • Mengumpulkan objek benda-benda dan mencari hubungan di antara mereka. 
  • Parametrik kurva, dan permukaan. 
  • Ruangan, grafik planar, dan tepian 
2. Pengukuran Dasar
  • Jarak antara dua objek geometri 
  • Luas, volume, keliling, luas permukaan dan massa 
3. Konstruksi Euclidian
  • Segmentasi garis 
  • Garis paralel, dan garis tegak lurus 
  • Lingkaran tertulis dan lingkaran sirkum 
  • Garis singgung 
4. Teori Dasar
  • Persimpangan, kesatuan, dan perbedaan (Garis, poligon, polihedron, dll) 
  • Tes untuk masuknya suatu objek ke objek yang lainnya. 
5. Kombinasi
  • Karakteristik Euler, Genus, Betti number, dan lain-lain. 
  • Pengaturan dari pengumpulan garis-garis maupun bidang. 
6. Masih banyak contoh lainnya...

Convex Hull

Dalam ilmu matematika, convex hull adalah satu set X dari titik pada bidang Euclidian atau ruang Euclidean, yaitu himpunan cembung terkecil yang berisi X. Sebagai contoh, ketika X merupakan bagian yang dibatasi dalam sebuah bidang, convex hull dapat divisualisasikan sebagai bentuk yang tertutup oleh karet gelang yang membentang di sekitar X.

Secara formal, convex hull dapat didefinisikan sebagai persimpangan dari semua set convex yang mengandung X atau juga sebagai hipunan dari semua kombinasi titik X.

Dalam dunia algoritma geometri, salah satu permasalahan manusia yang berkaitan dengan penentuan bentuk geometri dapat diselesaikan dengan menggunakan algoritma pencarian convex hull. Salah satu aplikasi penggunaan convex hull adalah untuk menentukan bentuk permukaan alam seperti yang sering dipakai dalam disiplin ilmu GIS (Geographical Information Systems)

Convex Hull


Pencarian Convex Hull dengan metode Graham's Scan

Dengan menggunakan metode algoritma Graham's Scan, kita dapat menemukan convex hull pada O(nLogn). Berikut ini adalah algoritma Graham's Scan :

Misalkan titik (0..n-1) adalah input dari sebuah array.

1.  Cari titik paling bawah dengan membandingkan koordinat y dari semua titik. Jika ada dua titik dengan nilai y yang sama, maka titik dengan nilai koordinat x terkecil adalah yang dapat dihitung. Biarkan titik paling bawah tersebut sebagai P0. Masukkan P0 tersebut pada posisi pertama output hull.

2.   Hitung sisa titik n-1 yang tersisa, dan urutkan titik-titik tersebut dengan sudut polar yang berlainan arah jarum jam di sekitar titik [0]. Jika sudut polar dari sebuah titik sama, maka simpanlah titik yang terdekat.

3.   Setelah diurutkan, cek apabila dua atau lebih titik mempunyai sudut yang sama. Apabila dua atau lebih titik mempunyai sudut yang sama, maka hapus semua titik yang mempunyai sudut yang sama kecuali titik yang terjauh dari P0. Anggaplah ukuran baru dari array sebagai m.

4.   Jika m kurang dari 3, return alias convex hull tidak memungkinkan.

5.   Buatlah stack kosong 'S' dan masukkan titik [0], titik [1] dan titik [2] ke stack tersebut.

6.   Selesaikan titik m-3 yang tersisa tadi satu persatu. Lakukan hal di bawah ini untuk semua titik[i]
  • Hapus titik dari stack selagi orientasi dari 3 titik tidak berlawanan arah jarum jam (Atau tidak berbelok ke arah kiri)
  • Pindahkan next ke tumpukkan paling atas.
  • Pindah ke tumpukkan paling atas
  • Masukkan nilai titik[i] ke S
7.   Tampilkan isi dari S.

Algoritma di atas dapat dipisahkan menjadi dua fase.

Fase pertama (Mengurutkan titik) : Pertama kita cari titik terbawah. Maksudnya adalah untuk mengurutkan titik-titik tersebut secara teratur ke titik yang paling bawah. Ketika titiknya sudah berurutan, Titik tersebut membentuk sebuah garis yang tertutup



Apa yang harus menjadi kriteria pengurutan? Perhitungan sudut aktual akan menjadi tidak efisien karena fungsi trigonometri yang tidak sederhana. Maksudnya adalah dengan menggunakan orientasi untuk membandingkan sudut yanpa benar-benar menghitung titik tersebut.

Fase kedua (Menerima atau menolak titik) Ketika kita sudah mendapatkan garis yang tertutup, langkah selanjutnya adalah melintasi garis dan menghapus titik cekung yang ada di garis tersebut. Bagaimana cara untuk menentukan titik mana yang harus dihapus dan titik mana yang harus disimpan? Sekali lagi, orientasi sangat membantu pada kasus ini. Dua titik yang pertama pada array yang sudah diurutkan akan selalu menjadi bagian dari convex hull. Untuk sisanya, catat tiga titik yang baru, dan cari sudut yang dibentuk oleh titik-titik tersebut. Biarkan tiga titik tersebut menjadi titik prev (Sebelumnya), titik curr (Saat ini), dan titik next (Selanjutnya). Jika orientasi dari titik-titik tersebut tidak berlawanan arah jarum jam, buanglah titik curr. Dan titik lainnya harus disimpan. Berikut ini adalah diagram yang menunjukkan langkah-langkah proses pada fase kedua ini.



Metode Algoritma Jarvis atau metode pembungkusan


Berikut ini adalah set point pada suatu bdang. Convex hull yang ada pada set adalah convex poligon yang terkecil yang memiliki semua titik pada bidang tersebut.

Maksud dari algoritma jarvis sebenarnya sangat simple. Dimulai dari titik yang paling kiri (Atau titik dengan nilai koordinat x terkecil) dan terus membungkus titik secara berlawanan arah jarum jam. Titik next (Selanjutnya) dipilih sebagai titik yang mengalahkan semua titik pada orientasi yang berlawanan dengan jarum jam. Sebagai contoh titik next yaitu q apabila titik yang lainnya adalah r, maka kita mempunyai orientasi (p, r, q) = berlawanan arah jarum jam. Berikut ini adalah algoritma lengkapnya :

1.   Inisialisasi p sebagai titik paling kiri.
2.   Lakukan hal dibawah ini saat kita tidak kembali ke titik awal (atau titik yang paling kiri tadi).

  • Titik q selanjutnya adalah titik yang mana triplet (p, q, r) menjadi berlawanan dengan semua titik r.
  • next[p] = q (Simpan q sebagai titik p selanjutya pada output convex hull)
  • p = q (Set p sebagai q untuk iterasi selanjutnya)


Algoritma Divide and Conquer Closest Pair


Algoritma brute force memeriksa jarak antara semua pasangan titik dan menjaga jalur yang paling minim. Rumusnya adalah O(n(n-1)2, quadratic.

Awal dari metode algoritma penggabungan dan pengurutan adalah untuk mengurutkan titik-titik sepanjang dimensi x lalu secara rekursif  membagi array dari titik dan mememukan titik terkecil. Yang perlu dilakukan adalah melihat jarak antara titik-titik tersebut dari dua set. Berikut ini algoritma lengkapnya :

1.   Inisialisasi urutan dari titik n. Pi = (xi, yi) dengan dimensi x.
2.   Lalu secara rekursif pisahkan titik n. S1 = {P1,...,Pn/2} and S2 = {Pn/2+1,...,Pn} sehingga titik S1  adalah dua titik yang paling kiri dari x = xn/2  dan S2 adalah sisi kanan dari x = xn/2.
3.   Kita harus memeriksa semua titik S1 yang ada pada strip ini untuk setiap titik S2 dan mendapatkan jarak terdekat dari dbetween
4.   Agar lebih efisien, maka diperlukan pengurutan titik sepanjang dimensi y, menggunakan pendekatan merge-sort.
5.   Lalu jarak terdekat adalah min(d, dbetween).

Algoritma Convex Hull Monotone Chain


Rangkai sebuah convex hull dari set titik dua dimensi pada o(n log n). Caranya dengan mengurutkan titik lexicographically, kemudian merangkai badan atas dan bawah dari titik pada o(n) time.

Badan atas yaitu bagian dari convex hull, yang mana terlihat dari bawah. Hal tersebut dijalankan dari titik yang paling kanan ke titik yang paling kiri secara berlawanan arah jarum jam. Badan bawah yaitu sisa bagian dari convex hull.

Animasi menggambarkan algoritma convex hull monotone


Pseudo-Code :
Urutkan titik-titik p dari koordinat x.
Inisialisasi U dan L sebagai list kosong.
List tersebut akan menahan simpul dari badan atas dan bawah secara masing-masing.
for i = 1, 2, ..., n:
     while L berisi setidaknya dua titik dan urutan dari dua titik terakhir dari L dan titik p[i] tidak berbelok berlawanan arah jarum jam:
                hapus titik terakhir dari L
          tambahkan p[i] ke L
for i = n, n-1, ..., 1:
     while U berisi setidaknya dua titik dan urutan dari dua titik terakhir dari U dan titik p[i] tidak berbelok berlawanan arah jarum jam:
          hapus titik terakhir dari U
     tambahkan p[i] ke U
Hapus titik terakhir dari kedua list (Sama dengan titik terakhir dari list lainnya).
Gabungkan L dan U untuk memperoleh convex hull dari p.
Titik pada hasil penggabungan tersebut akan terdaftar pada urutan yang berlawanan arah jarum jam.
Input : Sekumpulan p dari titik pada suatu bidang.

Referensi :

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)