{"id":8000,"date":"2020-05-17T15:51:44","date_gmt":"2020-05-17T08:51:44","guid":{"rendered":"http:\/\/binus.ac.id\/knowledge\/?p=8000"},"modified":"2020-12-17T16:58:23","modified_gmt":"2020-12-17T09:58:23","slug":"implementasi-algoritma-quad-tree-pada-bits-authoring-editor","status":"publish","type":"post","link":"https:\/\/binus.ac.id\/knowledge\/2020\/05\/implementasi-algoritma-quad-tree-pada-bits-authoring-editor\/","title":{"rendered":"Implementasi Algoritma Quad Tree pada BITS Authoring Editor"},"content":{"rendered":"<p>Quad Tree merupakan algoritma yang menggunakan konsep tree untuk menyimpan data berupa titik dalam bidang dua dimensi. Pada tree ini, setiap node akan memiliki maksimal empat node anak. Quad tree ini dapat digunakan untuk mencari titik terdekat secara efisien terhadap sebuah posisi yang diinginkan.<\/p>\n<p style=\"text-align: center;\"><strong><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter\" src=\"https:\/\/homes.sice.indiana.edu\/yye\/lab\/teaching\/spring2014-C343\/PRquadtree.png\" alt=\"More trees: balanced BSTs and specialized trees\" width=\"551\" height=\"287\" \/>Gambar 1. Representasi quad tree.<\/strong><br \/>\n<strong>Sumber Gambar: <a href=\"http:\/\/homes.sice.indiana.edu\/yye\/lab\/teaching\/spring2014-C343\/moretrees.php\">http:\/\/homes.sice.indiana.edu\/yye\/lab\/teaching\/spring2014-C343\/moretrees.php<\/a>\u00a0<\/strong><\/p>\n<p>Pada Gambar 1 sebelah kanan merupakan bidang dua dimensi yang berisi 6 titik (A, B, C, D, E, F) yang selanjutnya dilakukan partitioning dengan quad tree. Pada sebelah kiri merupakah quad tree yang terbentuk berdasarkan hasil partitioning bidang dua dimensi.<\/p>\n<p>Pada BITS <em>Authoring Tool Editor<\/em>, saya mengimplementasikan quad tree ini untuk memberikan rekomendasi objek terdekat yang dapat disejajarkan. Setiap objek di BITS merupakan kontainer yang berupa bentuk persegi terdiri dari 4 titik. Quad tree digunakan untuk menyimpan seluruh koordinat kontainer yang telah ditambahkan ke dalam editor. Ketika sebuah kontainer digeser ke arah tertentu atau salah satu sisi kontainer ditarik ke arah tertentu, maka akan dilakukan pencarian titik terdekat dari kontainer lain (Gambar 2).<\/p>\n<div style=\"width: 332px;\" class=\"wp-video\"><!--[if lt IE 9]><script>document.createElement('video');<\/script><![endif]-->\n<video class=\"wp-video-shortcode\" id=\"video-8000-1\" width=\"332\" height=\"270\" loop autoplay preload=\"metadata\" controls=\"controls\"><source type=\"video\/mp4\" src=\"http:\/\/binus.ac.id\/knowledge\/wp-content\/uploads\/2020\/12\/quadtree.mp4?_=1\" \/><a href=\"http:\/\/binus.ac.id\/knowledge\/wp-content\/uploads\/2020\/12\/quadtree.mp4\">http:\/\/binus.ac.id\/knowledge\/wp-content\/uploads\/2020\/12\/quadtree.mp4<\/a><\/video><\/div>\n<p style=\"text-align: center;\"><strong>Gambar 2. Implementasi rekomendasi kontainer terdekat pada BITS Editor<\/strong><\/p>\n<p>Menurut notasi asymptotic proses pencarian ini adalah O(lg n) baca: log basis 2 dari N, dimana N adalah banyaknya titik pada quad tree. Misalnya pada sebuah halaman konten terdapat 20 kontainer, berarti 20 x 4 titik = 80 titik. ketika ingin mencari jarak terdekat terhadap titik tertentu, maka hanya perlu dilakukan log basis 2 dari 80 yaitu 7 kali proses (6.3 dibulatkan ke atas). Hal ini tentu sangat efisien dibanding melakukan perbandingan <em>naive<\/em> terhadap semua 80 titik dan dicari yang terdekat.<\/p>\n<p><strong>Referensi:<br \/>\n<\/strong><a href=\"http:\/\/homes.sice.indiana.edu\/yye\/lab\/teaching\/spring2014-C343\/moretrees.php\">http:\/\/homes.sice.indiana.edu\/yye\/lab\/teaching\/spring2014-C343\/moretrees.php<\/a><br \/>\n<a href=\"https:\/\/www.geeksforgeeks.org\/quad-tree\/\">https:\/\/www.geeksforgeeks.org\/quad-tree\/<\/a><br \/>\n<a href=\"https:\/\/jimkang.com\/quadtreevis\/\">https:\/\/jimkang.com\/quadtreevis\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Quad Tree merupakan algoritma yang menggunakan konsep tree untuk menyimpan data berupa titik dalam bidang dua dimensi. Pada tree ini, setiap node akan memiliki maksimal empat node anak. Quad tree ini dapat digunakan untuk mencari titik terdekat secara efisien terhadap sebuah posisi yang diinginkan. Gambar 1. Representasi quad tree. Sumber Gambar: http:\/\/homes.sice.indiana.edu\/yye\/lab\/teaching\/spring2014-C343\/moretrees.php\u00a0 Pada Gambar 1 [&hellip;]<\/p>\n","protected":false},"author":5,"featured_media":8011,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83],"tags":[461,152,155],"class_list":["post-8000","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-news","tag-algoritma","tag-authoring-tool","tag-bits"],"_links":{"self":[{"href":"https:\/\/binus.ac.id\/knowledge\/wp-json\/wp\/v2\/posts\/8000","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/binus.ac.id\/knowledge\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/binus.ac.id\/knowledge\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/binus.ac.id\/knowledge\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/binus.ac.id\/knowledge\/wp-json\/wp\/v2\/comments?post=8000"}],"version-history":[{"count":11,"href":"https:\/\/binus.ac.id\/knowledge\/wp-json\/wp\/v2\/posts\/8000\/revisions"}],"predecessor-version":[{"id":8013,"href":"https:\/\/binus.ac.id\/knowledge\/wp-json\/wp\/v2\/posts\/8000\/revisions\/8013"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/binus.ac.id\/knowledge\/wp-json\/wp\/v2\/media\/8011"}],"wp:attachment":[{"href":"https:\/\/binus.ac.id\/knowledge\/wp-json\/wp\/v2\/media?parent=8000"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/binus.ac.id\/knowledge\/wp-json\/wp\/v2\/categories?post=8000"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/binus.ac.id\/knowledge\/wp-json\/wp\/v2\/tags?post=8000"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}