Compressed Quadtrees
Quadtrees ธรรมดาเก็บ Node ทุกตัวของ Subdivided Cell → ว่างเยอะ (Sparse) → Compressed Quadtree เก็บแค่ Important Subtrees (Leaves ที่มีข้อมูลน่าสนใจ)
เพิ่ม Compression: Prune Path ที่ Node Degree = 2 (1 Parent, 1 Child) → เก็บแค่ Node U ต้นทาง + Metadata แทน Node ที่ลบ → Attach Subtree ท้ายทางเข้ากับ U
Z-Order Curve (Morton Order) - Key to Efficiency
Z-order แปลง Cell ของ Quadtree (แม้ Compressed) ↔ 1D Line ใน O(1) → Total Order บน Elements
เก็บ Quadtree ใน Ordered Set Data Structure (เช่น Balanced BST)
สมมติฐานสำคัญ (O(1) Operations)
- Given α, β ∈ [0,1] Binary → หา First Differing Bit Index ใน O(1)
- หา Smallest Common Ancestor ของ 2 Points/Cells + Relative Z-order ใน O(1)
- Floor Function ใน O(1)
Point Location (หา Cell ที่มี Point Q) - O(log n)
- หา Cell V ใน Compressed Tree ที่อยู่ก่อน Q ใน Z-order
- ถ้า Q ∈ V → Return V
- Else: หา Smallest Common Ancestor U ของ Q และ V ใน Uncompressed Quadtree
- หา Cell ใน Compressed Tree ที่อยู่ก่อน U ใน Z-order → Return
Insert/Delete: Point Location ก่อน → Insert/Delete → Reshape Tree (Create/Delete Nodes ตามต้องการ)
Octree (อ็อกทรี)
Octree = Tree ที่ Internal Node มีลูก 8 ตัว แบ่ง 3D Space เป็น 8 Octants แบบ Recursive = 3D Analog ของ Quadtree
2 โหมด Spatial Representation
- Point Region (PR) Octree: Node เก็บ 3D Point โดยตรง = "Center" ของ Subdivision ระบุ Corner ของ 8 Children
- Matrix-based (MX) Octree: Subdivision Point = Center ของ Space ที่ Node แทน (Implicit)
PR Octree Root = Infinite Space ได้, MX Octree Root = Bounded Space (เพื่อ Implicit Centers)
Common Uses
- Level of Detail Rendering (3D Graphics)
- Spatial Indexing
- Nearest Neighbor Search
- Efficient 3D Collision Detection
- Finite Element Analysis
- Sparse Voxel Octree (SVO)
- State/Set Estimation
