Data StructuresMenengahFase D–FE1E5

QUADTREE

Quadtree adalah struktur data pohon yang membagi ruang 2D menjadi empat kuadran secara rekursif setiap kali sebuah wilayah memuat lebih dari satu titik. Proses subdivisi berhenti ketika tiap sel hanya berisi paling banyak satu titik. Visualisasi menunjukkan kotak yang terus terbelah menjadi empat bagian lebih kecil seiring titik-titik memaksa wilayah tersebut dipecah, beserta kedalaman (depth) pohon.

Example use case

Deteksi tabrakan (collision detection) pada game 2D dengan mempartisi objek ke wilayah spasial agar pengecekan lebih efisien.

Syllabus

Pohon yang membagi ruang 2D jadi empat kuadran berulang kali, memecah wilayah hanya saat memuat lebih dari satu titik.

Objectives

·Memahami pembagian ruang 2D menjadi empat kuadran
·Menjelaskan kapan sebuah sel perlu dipecah lagi
·Menerapkan quadtree untuk mempercepat pengecekan spasial

How It Works

·Mulai dari satu kotak besar yang meliputi seluruh ruang
·Bila sebuah wilayah memuat lebih dari satu titik, pecah jadi empat
·Tiap kuadran bisa dipecah lagi secara rekursif
·Subdivisi berhenti saat tiap sel berisi paling banyak satu titik
·Kedalaman pohon menunjukkan seberapa padat titik di area itu

Prerequisites

·Pohon
·Koordinat 2D
·Rekursi

Real-World Uses

·Deteksi tabrakan di game 2D agar cek antar objek lebih hemat
·Peta digital yang memuat titik lokasi sesuai tingkat zoom

Complexity O(log n) rata-rata per query