Perancangan Dan Analisis Algoritma Komputasi Geometri Volume Ruang Yang Dibangun Berdasarkan Prinsip Fractal Hilbert: Studi Kasus SPOJ 2152 HILBERT CURVE

D'Layla, Adifa Widyadhani Chanda (2024) Perancangan Dan Analisis Algoritma Komputasi Geometri Volume Ruang Yang Dibangun Berdasarkan Prinsip Fractal Hilbert: Studi Kasus SPOJ 2152 HILBERT CURVE. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025201013-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2026. Download (86MB) | Request a copy

Abstract

Penelitian ini dilatarbelakangi untuk memecahkan masalah Fractal Hilbert Curve yang melibatkan perhitungan volume orientasi pada bidang ruang seperti air dalam bejana. Sebuah ruang pada permasalahan ini berbentuk kurva Hilbert dengan orde ke-n (Hn). Kurva Hilbert adalah kurva pengisi ruang yang memiliki sifat-sifat fraktal dan didefinisikan secara rekursif. Dalam skenario pengisian air, air dan udara di dalam ruang tersebut dianggap tidak dapat dimampatkan dan tidak dapat bocor melalui batas ruang. Udara yang terperangkap di dalam ruang tersebut mencegah air mengisi seluruh volume. Tujuan dari penelitian ini adalah menghitung total volume area ruang yang terisi air dengan mempertimbangkan sudut kemiringan (0) kurva terhadap permukaan. Untuk menyelesaikan permasalahan ini, digunakan pendekatan rekursif dalam membentuk kurva Hilbert orde ke-n dan algoritma Depth First Search (DFS) untuk menghitung volume area yang terisi air. Order pada kurva Hilbert memiliki sifat yang unik, yaitu dimulai dengan empat salinan dari kurva Hilbert order sebelumnya. Salinan pertama ditempatkan di kiri atas dan diputar -90 derajat (berlawanan arah jarum jam). Salinan kedua ditempatkan di kiri bawah tanpa rotasi. Salinan ketiga ditempatkan di kanan bawah tanpa rotasi juga. Terakhir, salinan keempat ditempatkan di kanan atas dan diputar 90 derajat (searah jarum jam). Setelah semua salinan ditempatkan sesuai dengan posisi dan rotasinya masing-masing, salinan-salinan ini dihubungkan dengan tiga garis untuk membentuk kurva Hilbert yang utuh. Kurva Hilbert diimplementasikan dalam grid dua dimensi dengan menggunakan struktur data array. Perhitungan volume area yang terisi air dilakukan dengan mempertimbangkan sudut kemiringan permukaan yang diberikan. Berdasarkan hasil uji coba pada studi kasus yang diberikan, solusi pendekatan komputasi geometri yang dibangun berdasarkan prinsip Fractal Hilbert berhasil menyelesaikan permasalahan dengan waktu rata-rata 0.00 detik dan memori rata-rata 5.25 MB. Solusi ini berhasil menempati peringkat pertama secara berkelompok pada situs Sphere Online Judge.
==================================================================================================================================
This research addresses the problem of the Fractal Hilbert Curve, specifically calculating the volume orientation in spatial fields, such as water in a container. The space in question is shaped like a Hilbert curve of order n (Hn). The Hilbert curve is a space-filling curve with fractal properties, defined recursively. In the water-filling scenario, both water and air within the space are considered incompressible and unable to leak through the boundaries. The trapped air prevents the water from filling the entire volume. The aim of this research is to calculate th total volume of space filled with water, taking into account the tilt angle (0) of the curve relative to the surface. To solve this problem, a recursive approach is used to form the Hilbert curve of order n, and the Depth First Search (DFS) algorithm is employed to calculate the volume of the area filled with water. The order of the Hilbert curve has a unique property: it begins with four copies of the previous order's Hilbert curve. The first copy is placed in the top left and rotated -90 degrees (counterclockwise). The second copy is placed in the bottom left without rotation. The third copy is placed in the bottom right, also without rotation. The fourth copy is placed in the top right and rotated 90 degrees (clockwise). After positioning and rotating these copies, they are connected by three lines to form a complete Hilbert curve. The Hilbert curve is implemented on a two-dimensional grid using an array data structure. The volume of the area filled with water is calculated, considering the given surface tilt angle. Based on test results in the provided case study, the geometric computational approach built on the Fractal Hilbert principle successfully solved the problem with an average time of 0.00 seconds and an average memory usage of 5.25 MB. This solution achieved first place in the group ranking on the Sphere Online Judge website

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Fractal, Kurva Hilbert, Graf, Geometri Tiga Dimensi
Subjects:	Q Science > QA Mathematics > QA166 Graph theory Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	ADIFA WIDYADHANI CHANDA D’LAYLA
Date Deposited:	01 Aug 2024 02:28
Last Modified:	01 Aug 2024 02:28
URI:	http://repository.its.ac.id/id/eprint/109529

Actions (login required)

View Item