Quadtrees เป็นต้นไม้ที่ใช้ในการจัดเก็บข้อมูลของจุดบนพื้นที่สองมิติอย่างมีประสิทธิภาพ ในแผนผังนี้ แต่ละโหนดมีลูกได้สูงสุดสี่คน
เราสามารถสร้าง quadtree จากพื้นที่สองมิติโดยทำตามขั้นตอนต่อไปนี้
- พื้นที่สองมิติปัจจุบันแบ่งออกเป็นสี่ช่อง
- หากกล่องประกอบด้วยจุดหนึ่งจุดขึ้นไป ให้สร้างวัตถุลูก โดยจัดเก็บช่องว่างสองมิติของกล่องนั้นไว้
- ถ้ากล่องไม่มีแต้ม อย่าสร้างเด็กขึ้นมา
- ทำการเรียกซ้ำสำหรับเด็กแต่ละคน
Quadtrees ถูกนำมาใช้ในการบีบอัดภาพ โดยที่แต่ละโหนดประกอบด้วยสีเฉลี่ยของลูกๆ แต่ละตัว
ยิ่งเข้าไปลึกในต้นไม้ ยิ่งได้รายละเอียดของภาพมากเท่านั้น
Quadtrees ยังถูกนำมาใช้ในการค้นหาโหนดในพื้นที่สองมิติ ตัวอย่างเช่น หากเราต้องการคำนวณจุดที่ใกล้เคียงที่สุดกับพิกัดที่กำหนด เราสามารถทำได้โดยใช้ควอดทรี
ฟังก์ชันแทรก
ฟังก์ชันการแทรกถูกนำไปใช้เพื่อแทรกโหนดลงในทรีควอดทรีที่มีอยู่ ฟังก์ชันนี้จะตรวจสอบก่อนว่าโหนดที่กำหนดอยู่ภายในขอบเขตของควอดปัจจุบันหรือไม่ หากไม่เป็นเช่นนั้น เราจะยกเลิกการแทรกทันที หากอยู่ภายในขอบเขต เราเลือกชายน์ที่เหมาะสมเพื่อให้มีโหนดนี้ตามตำแหน่งของโหนด ฟังก์ชันนี้คือ O(Log N) โดยที่ N ระบุขนาดของระยะทาง
ฟังก์ชันการค้นหา
ฟังก์ชั่นการค้นหาถูกนำมาใช้เพื่อค้นหาโหนดในควอดที่กำหนด นอกจากนี้ยังสามารถแก้ไขได้เพื่อคืนโหนดที่ใกล้เคียงที่สุดไปยังจุดที่กำหนด ฟังก์ชันนี้ใช้โดยพิจารณาจุดที่กำหนด เปรียบเทียบกับขอบเขตของคณะลูกน้องและการเรียกซ้ำ ฟังก์ชันนี้คือ O(Log N) โดยที่ N ระบุขนาดของระยะทาง
การใช้งานควอดทรีโดยทั่วไป
- การแสดงภาพแทนภาพ
- การประมวลผลภาพของภาพ
- การสร้างตาข่ายของตาข่าย
- ทำการตรวจจับการชนกันอย่างมีประสิทธิภาพในสองมิติ
- ดำเนินการเพื่อค้นหาคำตอบของสนามหลายมิติ (พลศาสตร์ของไหลเชิงคำนวณ, แม่เหล็กไฟฟ้า)
- ประมาณการของรัฐ
- Quadtrees ยังถูกนำมาใช้ในด้านการวิเคราะห์ภาพเศษส่วน
