ต้นไม้สี่เหลี่ยมที่ถูกบีบอัด
ในขณะที่จัดเก็บทุกโหนดที่สัมพันธ์กับเซลล์ที่แบ่งย่อย เราอาจจบลงด้วยการจัดเก็บโหนดที่ว่างเปล่าจำนวนมาก การลดขนาดของต้นไม้ที่กระจัดกระจายนั้นทำได้โดยการจัดเก็บเฉพาะต้นไม้ย่อยที่มีใบที่มีข้อมูลที่น่าสนใจเท่านั้น (เช่น "ต้นไม้ย่อยที่สำคัญ") อีกครั้งเราสามารถลดขนาดลงได้อีก เมื่อเราพิจารณาเฉพาะทรีย่อยที่สำคัญ กระบวนการตัดแต่งกิ่งอาจหลีกเลี่ยงเส้นทางยาวในทรีที่โหนดระดับกลางมีระดับที่สอง ปรากฎว่าเราเพียงต้องการเก็บโหนด U ที่จุดเริ่มต้นของเส้นทางนี้ (และเชื่อมโยงข้อมูลเมตาบางอย่างกับมันเพื่อเป็นตัวแทนของโหนดที่ถูกลบ) และแนบทรีย่อยที่รูทที่ปลายของมันกับ U ต้นไม้ที่ถูกบีบอัดเหล่านี้ยังคงมี ความสูงเชิงเส้นเมื่อกำหนดจุดป้อน "ไม่ดี"
แม้ว่าเราจะตัดต้นไม้จำนวนมากเมื่อเราดำเนินการบีบอัดนี้ แต่ก็ยังสามารถบรรลุการแทรก การลบ และการค้นหาเวลาลอการิทึมได้ด้วยการใช้ประโยชน์จากเส้นโค้ง Z-order เส้นโค้ง Z-order จะแปลงแต่ละเซลล์ของ quadtree แบบเต็ม (และด้วยเหตุนี้แม้แต่ quadtree ที่ถูกบีบอัด) ในเวลา O(1) เป็นเส้น 1 มิติ (และแปลงกลับเป็น O(1) เวลาด้วย) สร้างลำดับทั้งหมด บนองค์ประกอบ ตอนนี้ เราสามารถจัดเก็บควอดทรีในโครงสร้างข้อมูลสำหรับชุดคำสั่ง (ที่เราเก็บโหนดของทรี) ตอนนี้ เราต้องระบุสมมติฐานที่สมเหตุสมผลก่อนที่จะดำเนินการต่อ:สมมติว่าให้จำนวนจริงสองจำนวน α,β € [0,1] แสดงว่าเป็นเลขฐานสอง เราสามารถคำนวณใน O(1) เวลาดัชนีของบิตแรกที่พวกมัน แตกต่างกัน เรายังถือว่าเราสามารถคำนวณใน O(1) เวลาที่บรรพบุรุษร่วมที่เล็กที่สุดของสองจุด/เซลล์ในควอดทรีและสร้างลำดับ Z สัมพัทธ์ และเราสามารถคำนวณฟังก์ชันพื้นในเวลา O(1) ด้วยสมมติฐานเหล่านี้ ตำแหน่งจุดของจุด Q ที่กำหนด (เช่น ค้นหาเซลล์ที่จะมี Q) การลบและการแทรกสามารถทำได้ในเวลา O(n log n) (เช่น เวลาที่ใช้ในการค้นหาใน โครงสร้างข้อมูลชุดคำสั่งพื้นฐาน)
เพื่อดำเนินการระบุตำแหน่งจุดสำหรับ Q (เช่น กำหนดเซลล์ในแผนผังที่บีบอัด)
- พบเซลล์ที่มีอยู่แล้วในแผนผังที่บีบอัดซึ่งมาก่อน Q ในลำดับ Z เรียกเซลล์นี้ว่า V.
- หากดำเนินการ Q€V ให้คืนค่า V
- มิฉะนั้น ให้ค้นหาสิ่งที่จะเป็นบรรพบุรุษร่วมที่เล็กที่สุดของจุด Q และเซลล์ V ในควอดทรีที่ไม่มีการบีบอัด เรียกเซลล์บรรพบุรุษนี้ว่า U.
- ค้นหาเซลล์ที่มีอยู่ในทรีบีบอัดที่อยู่ก่อนหน้า U ในลำดับ Z แล้วส่งคืน
โดยไม่ต้องลงรายละเอียดเฉพาะ ในการดำเนินการแทรกและลบ ขั้นแรกเราจะดำเนินการตำแหน่งจุดสำหรับสิ่งที่เราต้องการแทรก/ลบ จากนั้นจึงแทรก/ลบ ต้องใช้ความระมัดระวังในการปรับรูปร่างต้นไม้ตามความเหมาะสม การสร้างและการลบโหนดตามความจำเป็น
ออคทรี
octree ถูกกำหนดให้เป็นโครงสร้างข้อมูลแบบต้นไม้ซึ่งแต่ละโหนดภายในเชื่อมโยงกับลูกๆ แปดตัวเท่านั้น
ส่วนใหญ่มักใช้ Octrees เพื่อแบ่งพื้นที่สามมิติโดยแบ่งย่อยออกเป็นแปดส่วนซ้ำๆ
Octrees ถือเป็นแอนะล็อกสามมิติของ quadtrees ชื่อนี้สร้างจาก oct + tree แต่โปรดทราบว่าปกติแล้วจะเขียนว่า "octree" โดยมี "t" เพียงตัวเดียว
Octree มักใช้ในกราฟิก 3 มิติและเอ็นจิ้นเกม 3 มิติ
สำหรับการแสดงเชิงพื้นที่
แต่ละโหนดใน octree มีหน้าที่แบ่งพื้นที่ที่แสดงถึงออกเป็นแปดอ็อกเทน ในพื้นที่จุด (PR)
octree โหนดเก็บจุด 3 มิติที่ชัดเจนซึ่งเป็น "ศูนย์กลาง" ของส่วนย่อยสำหรับโหนดนั้น ประเด็น
ระบุมุมหนึ่งมุมสำหรับเด็กแปดคนแต่ละคน ในกรณีของอ็อกทรีแบบเมทริกซ์ (MX) จุดแบ่งย่อยเป็นจุดศูนย์กลางของช่องว่างที่แสดงโดยโหนดโดยปริยาย โหนดรูทของ PR octree สามารถแสดงพื้นที่อนันต์ได้ โหนดรูทของ MX octree จะต้องสามารถแสดงพื้นที่ที่มีขอบเขตจำกัด เพื่อให้ศูนย์กลางโดยปริยายมีการกำหนดไว้อย่างชัดเจน
การใช้งานทั่วไป
- ระดับของการแสดงรายละเอียดในคอมพิวเตอร์กราฟิก 3 มิติ
- การจัดทำดัชนีเชิงพื้นที่
- ค้นหาเพื่อนบ้านที่ใกล้ที่สุด
- การตรวจจับการชนกันอย่างมีประสิทธิภาพในสามมิติ
- การวิเคราะห์องค์ประกอบจำกัด
- กระจัดกระจาย voxel octree
- ประมาณการของรัฐ
- ประมาณการของเซต
