Quadtrees คืออะไร?
Quadtrees = Trees สำหรับจัดเก็บ Points บน 2D Space อย่างมีประสิทธิภาพ แต่ละ Node มีลูกสูงสุด 4 ตัว
การสร้าง Quadtree จาก 2D Area
- แบ่ง 2D Space ปัจจุบันเป็น 4 Boxes
- ถ้า Box มี ≥1 Point → สร้าง Child Object เก็บ 2D Space ของ Box นั้น
- ถ้า Box ไม่มี Point → ไม่สร้าง Child
- Recurse สำหรับแต่ละ Child
การประยุกต์ใช้หลัก
- Image Compression: Node เก็บ Average Color ของ Children ลึกขึ้น = Detail มากขึ้น
- 2D Spatial Search: หา Closest Point ให้กับ Coordinates ที่กำหนด
Insert Function - O(log N)
ตรวจสอบ Node อยู่ใน Boundary ของ Current Quad → ไม่อยู่ = Cancel
อยู่ใน Boundary → เลือก Child ที่เหมาะสมตาม Location → Recurse
Search Function - O(log N)
หา Node ใน Quad / Closest Node ให้ Point ที่กำหนด
Compare กับ Child Quad Boundaries → Recurse
Common Uses
- Image Representation & Processing
- Mesh Generation
- 2D Collision Detection
- Multidimensional Field Solvers (CFD, Electromagnetics)
- State Estimation
- Fractal Image Analysis
