Prosiding Semirata FMIPA Universitas Lampung, 2013
Penghitungan Subset Visibilitas pada Suatu Orthogonal Polyhedron Jefri Marzal Program Studi Pendidikan Matematika FKIP Universitas Jambi E-Mail:
[email protected] Abstrak: Problem visibilitas (visibility) adalah central untuk banyak aplikasi komputasi geometri. Salah satu tipe dari problem visibilitas adalah penghitungan daerah penglihatan (view) dari suatu titik pandang yang diberikan. Problem ini dirumuskan sebagai berikut: misalkan terdapat suatu orthogonal polyhedron yang telah dipartisi menjadi sebuah himpunan prisma segi-empat , dan misalkan c adalah sebuah titik dalam prisma segiempat tersebut, tentukanlah subset dari yang terlihat secara total dari c. Dalam paper ini, suatu prosedur dengan kompleksitas linear diusulkan untuk menghitung subset visibilitas dari titik pojok prisma segi-empat dalam suatu orthogonal polyhedron. Kata kunci: visibilitas, prisma segi-empat, orthogonal polyhedron
Pendahuluan Visibilitas adalah sebuah konsep yang penting dalam komputasi geometri. Persoalan yang melibatkan visibilitas objek telah muncul dalam banyak bidang, misalnya dalam komputer grafik, layout VLSI, dan motion planning. Dengan demikian, perbaikan dalam konsep visibilitas akan berpengaruh pada bidangbidang tersebut dan aplikasinya. Salah satu problem dalam visibilitas adalah problem menentukan apakah dua objek saling melihat secara total, parsial, atau tidak sama sekal [1]. Dua titik disebut saling melihat jika segment garis yang menghubungkan kedua titik tersebut tidak terhalang oleh sembarang halangan. Study visibilitas sangat berhubungan dengan studi segment garis yang bebas dalam suatu pandangan (scene). Visibilitas juga dapat didefinisikan dalam istilah teori graph, dimana simpul-simpul mewakili titik-titik pandang, dan p dan q dikatakan saling melihat apabila terdapat sinar yang menghubungan ke dua titik tersebut [2]. Penelitian tentang visibiltas dalam 2 dimensi sangat banyak dan berkembang [3, 4], akan tetapi tidak banyak teori-teori tentang visibilitas 3 dimensi. Penelitian
visibilitas 3 dimensi, pendeketanya saat ini kebanyakan adalah konstruktif bukan analitis. Bygi dan Ghodsi menjelaskan beberapa alasan kondisi ini, dan mereka mencoba mendefisisikan struktur geometri dalam ruang 3 dimensi [2]. Salah satu persoalan visibilitas adalah bagaimana menghitung daerah pandangan dari suatu titik yang diberikan pada suatu bangun ruang. Dalam paper ini, penelitian berkenaan dengan varian dari persoalan visibilitas yang didefinisikan seperti berikut: misalkan terdapat sebuah polyhedron orthogonal yang disusun atas himpungan prisma segi-empat (rectangular prism) , dan misalkan c adalah titik pojok dari prima segiempat, maka apakah subset yang terlihat secara total dari c? Pada studi ini, penulis mengusulkan suatu prosedur untuk menghitung subset visibilitas dari titik penglihat yang difinisikan. Selanjutnya, ditemukan bahwa kompleksitas waktu eksekusi prosedur bekerja dengan waktu yang linear. Definisi Dan Terminologi Polygon didefinisikan sebagai bidang datar yang dibatasi oleh segment garis yang saling terhubung secara tertutup. Permukaan polyhedron didefinisikan Semirata 2013 FMIPA Unila |291
Jefri: Penghitungan subset visibilitas pada suatu orthogonal polyhedron
sebagai bidang polygon yang terhubung dan terbatas, sedemikian sehingga setiap rusuk dari polygon adalah kepunyaan salah satu polygon yang lain, dengan proviso bahwa polygon-polygon mengelilingi setiap simpul membentuk sirkuit tunggal [5]. Sebuah rusuk yang mempunyai tepat dua polyogon disebut dengan rusuk two-manifold, and simpul yang merupakan puncak dari satu polygon disebut simpul two-manifold [6]. Sebuah cone didefiniskan sebagai bentuk 3dimensi yang mengerucut secara perlahan dari dasar kesebuah titik yang disebut dengan apex. Dengan demikian, suatu permukaan polyhedron memuat polygonpolygon terhubung yang hanya mempunyai rusuk two-manifold dan simpul two-manifold, dan tipe batas ini disebut batas two-manifold. Polygon yang berada pada permukaan polyhedron disebut juga dengan sisi, dan setiap sisi tidak saling memotong dengan sisi lainnya pada permukaan polyhedron tersebut. Sementara itu, polyhedron didefinisikan sebagai ruang dimensi 3 yang dibatasi oleh permukaan polyhedron [5]. Sisi, rusuk dan simpul adalah elementelement penting dari permukaan suatu polyhedron. Sisi adalah permukaan suatu polyhedron, dan setiap permukaan polyhedron mempunyai bentuk bidang yang disebut dengan polygon. permukaan polyhedron juga disebut dengan terminology boundary polyhedron. Rusuk adalah sebuah segment garis pada boundary polyhedron dimana dua atau lebih sisi bertemu. Simpul adalah titik pada boundary polyhedron dimana tiga atau lebih rusuk bertemu [7]. Boundary polyhedron membagi ruang atas dua bagian, satu diantaranya disebut dengan interior yang sifatnya berbatas, dan eksterior yang sifat daerahnya tidak terbatas. Titik pada polyhedron adalah titik pada boundary polyhedron atau dalam interior dari polyhedron. Titik 292| Semirata 2013 FMIPA Unila
interior dari polyhedron adalah titik dalam interior polyhedron, dan titik boundary adalah titik yang berada pada boundary polyhedron. Salah satu polyhedron yang banyak dipelajari adalah polyhedron orthogonal. Tang mendefinisikan bahwa polyhedron orthogonal adalah polyhedron dimana setiap rusuknya parallel dengan salah satu arah orthogonal [8]. Polyhedron orthogonal banyak dipelajari karena banyak bangun-bagun ruang dan pesoalan sehari-hari yang direpresetasikan secara polyhedron orthogonal. Untuk memfasilitasi diskusi tentang subset visibilitas, maka istilah-istilah berikut, yang sebagian telah diperkenalkan oleh [9], didefinisikan. Definisi 1: Dua titik x dan y dalam polyhedron orthogonal dikatakan saling melihat melihat (visible) jika dan hanya jika ruas garis xy tidak memotong boundary polyhedron orthogonal Definisi 2: Misalkan c adalah sebuah titik dari polyhedron orthogonal, daerah visibilitas c, dinyatakan dengan Vr(c) adalah himpunan titik polyhedron orthogonal yang dapat dilihat dari c. Definisi 3. Bagian dari polyhedron orthgonal dikatakan dapat terlihat secara total dari titik penglihat c jika setiap titik dari dapat terlihat dari c (yaitu Vr(c)). disebut dapat terlihat sebagian dari c jika beberapa, tidak semua, titik p dapat dilihat dari c. Visibilitas Dalam Polyhedron Orthogonal Misalkan terdapat suatu himpunan prisma segi-empat disusun dari suatu polyhedron orthgonal dengan algoritma yang disusulkan pada [10]. Prisma segiempat didefinisikan sebagai prisma yang semua sisinya berbentung persegi panjang dan parallel pada salah satu arah orthogonal dalam dimensi 3. Tujuan dari penghitungan subset visibilitas adalah untuk membangun suatu himpunan yang tidak kosong S = { Sj | j=1,...,k }, dimana
Prosiding Semirata FMIPA Universitas Lampung, 2013
Sj = { | dan Vr(cj)} adalah subset visibilitas untuk titik pojok cj. Gambar 1 menggambarkan suatu polyhedron orthgonal yang dipartisi ke dalam himpunan prisma segi-empat . Setelah pempartisian maka polyhedron orthogonal dilabel dengan vi adalah simpul, dan ui adalah titik buatan dari polyhedron. Masing masing v1 dan u1 juga titik pojok dari prisma segi-empat yang sama. Titik pojok ke jth disimbolkan sebagai cj. Sebagai tambahan, 1 dan 2 adalah bagian-bagain himpunan .
Gambar 1. Pempartisian polyhedron orthgonal Prosedur penghitungan subset visibilitas dari sebuah titik pojok prisma segi-empat berdasarkan observasi berikut: i) setiap prima segi-empat mempunyai enam sisi. Keenam sisi ini dapat dibagi atas dua tipe sisi Tipe I adalah sisi dari polyhedron orthgonal asal dan sisi Tipe II berasal dari titik interior polyhedron orthogonal asal kecuali pada rusuk-rusuk sisi. Jika rusuk dari suatu sisi adalah juga rusuk dari polyhedron orthogonal asal maka rusuk dikatakan rusuk Tipe I. Jika tidak demikian, maka rusuk terdiri dari titik interior saja dari polyhedron orthgonal asal dan disebut dengan Rusuk Tipe II. (ii) Untuk setiap suatu titik penglihat (view point), prisma segi-empat (prisma segi-empat pertama) dapat terlihat secara total dari titik penglihat tersebut jika dan hanya jika tidak terdapat prisma segi-empat dengan sisi Tipe I berpotongan dengan garis penghubung titik penglihat dengan sebuah titik pada prisma recatangular pertama.
Gambar 2. Algoritma membuat subset visibilitas Algoritma yang di atas mengasumsikan ketersediaan titik pojok ci ( i=1, 2, . . . , k) dari m prima segiempat rpj (j=1, 2, …, m) yang dihasilkan dari pempartisian sebuah polyhedron orthogonal. Perhatikan bahwa beberapa titik pojok dapat dipakai oleh lebih dari satu prisma segi-empat, sehingga k 8m. Hal ini akan membuat k subset visibilitas Si (i=1, 2, . . . , k). Untuk setiap titik pojok akan diperiksa apakah setiap prima segiempat dapat terlihat secara total dari titik pojok tersebut atau tidak. Jika setiap titik dalam prisma segi-empat dapat terlihat dari titik pojok, maka prisma segi-empat tersebut terlihat secara total dari titik pojok tersebut. Kalau tidak, prisma segiempat terhalang secara total atau sebagian dari titik pojok tersebut. Pada akhir pengulangan, Si akan berisi semua prisma segi-empat yang dapat terlihat secara total dari titik pojok cj. Lihat Gambar 2 untuk lebih detail.
Gambar 3. Fungsi IsViewBlocked untuk menentukan keterhalangan Semirata 2013 FMIPA Unila |293
Jefri: Penghitungan subset visibilitas pada suatu orthogonal polyhedron
Fungsi IsViewBlocked mengambil sebuat titk cj, dan dua prisma segi-empat, rpj dan rpl. Fungsi ini akan mempunyai nilai balik True jika penglihatan dari ci ke rpj dihambat dengan adanya rpl. Kalau tidak, maka fungsi mempunyai nilai balik False. Untuk sembarang prisma segiempat rpj dan titik ci terletak diluar rpj, terdapat antara satu dan tiga sisi rpj yang dapat terlihat dari ci, tergantung dari posisi titik tersebut ke prisma rectangualar. Sisi yang dapat terlihat ini dan titik pojok dapat membentuk tiga pyramida segiempat piramida yang alasnya berbentuk persegi panjang, dengan setiap sisi yang dapat terlihat pada dasar dan titik pojok pada puncak. Jika prisma segi-empat lain rpl menghambat penglihatan dari dari ci ke rpj, baik secara total ataupun sebahagian, maka akan memuat sekurang-kurangnya satu sisi Tipe I ataru rusuk Tipe I. Kalau tidak prisma segi-empat rp1 akan terdiri dari hanya titik interior saja dari polyhedron orthogonal asal, dengan demikian prisma segi-empat tersebut akan transparent. Prisma segi-empat rpl menghambat penglihatan dari ci ke rpj jika dan hanya jika rpl memuat sisi Tipe I dan rusuk Tipe I yang berpotongan dengan salah satu piramida segi-empat yang telah disebutkan di atas. Untuk melihat mengapa ini menjadi condisi yang diperlukan, misalkan diasumsikan bahwa rpl tidak menghampat penglihatan dari ci ke rpj. Hal ini berarti bahwa terdapat sekurang-kurangnya satu titik s dalam rpj yang dihambat oleh rpl. Garis yang menghubungkan ci dan s akan berpotongan dengan satu atau lebih titik rpl. Salah satu dari perpotongan ini haruslah terletak dalam sisi Tipe I atau rusuk Tipe I, karena jika tidak semua titik perpotongan akan menjadi titik interior polyhedron rectangular asal yang transaparan dan tidak menghalangi penglihatan. Hal ini membuktikan bahwa jika rpl menghambat penglihatan dari ci ke rpj, maka rpl harus 294| Semirata 2013 FMIPA Unila
memuat sisi Tipe I atau rusuk Tipe I yang berpotongan dangan salah satu piramida rectangular. Untuk melihat kondisi ini memadai, kita hanya membutuhkan untuk mengambil sembarang titik perpotongan s antara sisi Tipe I rpl dan salah satu piramida rectangular. Karena s terletak dalam piramida, garis dari ci ke s dapat diperpanjang sampai ke dasar piramida, berakhir di titik t. Jelaslah bahwa titik t pada sisi rpj tidak dapat dilihat dari ci karena penglihatan terhalang oleh titik s yang berada pada sisi Tipe I atau rusuk Tipe I rpl. Hal ini berarti bahwa rpl menghalangi penglihatan dari ci ke rpj. Untuk menentukan apakah suatu persegi panjang dan suatu piramida segiempat berpotongan satu sama lain, seseorang dapat memeriksa apakah salah satu dari empat titik pojok persegi panjang terletak dalam pyramid. Jika salah satu ditemukan dalam piramida, maka persegi panjang dan piramida berpotongan satu dengan yang lainnya. Jika tidak ada titik pojok yang yang terletak didalam piramida, kita masih perlu memperhatikan kasus ketika persegi panjang memotong piramida dimana semua titik pojok berada di luar piramida. Hal ini dengan mudah dapat diverifikasi dengan pengambil setiap rusuk piramida dan melihat apakah salah atau rusuk tersebut berpotongan dengan persegi panjang. Jika salah satu rusuk ditemukan berpotongan dengan persegi panjang, maka pyramida dan persegi panjang berpotongan satu sama lainnya. Dalam hal lainnya mereka tidak berpotongan satu sama lain. Sangatlah mudah untuk menentukan apakah sebuah rusuk berpotongan dengan sebuah piramida segi-empat. Pertamatama dapat dengan cara memeriksa setiap dua titik pangkal rusuk. Jika sekurangkurangnya satu titik pangkal dalam piramida, maka rusuk mesti berpotongan dangan piramida. Jika kedua titik pangkal rusuk terletak diluar piramida, maka masih ada kemungkinan bahwa rusuk
Prosiding Semirata FMIPA Universitas Lampung, 2013
tersebut memotong piramida. Terdapat suatu skenario, rusuk berpotongan dengan piramida jika dan hanya jika rusuk berpotongan dengan satu dari lima sisi piramida. Dengan demikian perpotongan dapat ditentukan dengan memeriksa apakah sisi piramida berpotongan dengan rusuk. HASIL DAN PEMBAHASAN Cost waktu dapat ditentukan sebagai berikut. Subset visibilitas dapat dibangun dengan kompleksitas waktu O(m3) seperti yang ditunjukan di atas. Apabila m < n3 maka subset visibilitas dapat dibangun dalam waktu yang polynomial n. Daftar Pustaka F. d. Durand, G. Drettakis, and C. Puech, "The 3D Visibility Complex," ACM Transactions on Graphics, vol. 21, pp. 176 - 206, 2002. M. N. Bygi and M. Ghodsi, "3D Visibility Graph," presented at the Computational Science and its Applications, Kuala Lampur, 2007. M.
Pocchiola and G. Vegter, "Topologically sweeping visibility complexes via pseudotriangulations," Discrete & Computational Geometry, vol. 16, pp. 419–453, 1996.
S. K. Ghosh and D. Mount, "An output sensitive algorithm for computing visibility graphs," SIAM Journal Computing, vol. 20, pp. 888-910, 1991. H. S. M. Coxeter, Regular polytopes. New York: Dover Publications, 1973. J. R. Rossignac and A. A. G. Requicha, "Construcitve Non-Regularized Geometry," Computer - Aided Design, vol. 23, pp. 21-32, 1991. T. Biedl and B. Genc, "Reconstructing orthogonal polyhedra from putative vertex sets," technical reports, 2007. K. Tang and T. C. Woo, "Algorithmic aspects of alternating sum of volumes. Part 1: Data structure and difference operation," Computer-Aided Design, vol. 23, pp. 357-366, June 1991. A. P. Tomas, A. L. Bajuelos, and F. Marques, "On visibility problems in the plane - solving minimum vertex guard problems by successive approximation," in the 9th Int. Symp. on Artif. Intel. and Math., 2006. J. Marzal, H. Xie, and C. C. Fung, "Vertex Configurations and Their Relationship on Orthogonal Pseudo Polyhedra " World Academy of Science, Engineering and Technology pp. 1-8, 2011.
Semirata 2013 FMIPA Unila |295
