Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

ภูมิภาค Quadtrees ในโครงสร้างข้อมูล


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

อาจใช้ quadtree ของภูมิภาคที่มีความลึก n เพื่อแสดงรูปภาพที่ประกอบด้วยพิกเซล 2n × 2n โดยที่ค่าพิกเซลแต่ละค่าเป็น 0 หรือ 1 โหนดรูทมีประโยชน์ในการแสดงขอบเขตของรูปภาพทั้งหมด หากพิกเซลในภูมิภาคใดไม่ใช่ 0 หรือ 1 ทั้งหมด จะถูกแบ่งย่อย ในแอปพลิเคชันนี้ leaf node แต่ละอันมีประโยชน์ในการแสดงบล็อกของพิกเซลที่เป็น 0 ทั้งหมดหรือ 1 ทั้งหมด สังเกตการประหยัดที่อาจเกิดขึ้นในแง่ของพื้นที่เมื่อใช้ต้นไม้เหล่านี้เพื่อจัดเก็บภาพ ภาพเหล่านี้มักมีหลายพื้นที่ที่มีขนาดพอเหมาะซึ่งมีค่าสีเท่ากันตลอด แทนที่จะจัดเก็บอาร์เรย์ 2 มิติขนาดใหญ่ของทุกๆ พิกเซลในภาพ quadtree สามารถบันทึกข้อมูลเดียวกันได้ ซึ่งอาจมีระดับความแตกแยกจำนวนมากที่ใหญ่กว่าเซลล์ที่มีขนาดความละเอียดพิกเซลที่เราต้องการ ขนาดพิกเซลและรูปภาพสามารถผูกกับความละเอียดของต้นไม้และขนาดโดยรวมได้

นอกจากนี้ยังอาจใช้ quadtree ของภูมิภาคเป็นตัวแทนความละเอียดตัวแปรของฟิลด์ข้อมูล เช่น อุณหภูมิในพื้นที่อาจจัดเก็บเป็นควอดทรี โดยแต่ละโหนดของลีฟจะจัดเก็บอุณหภูมิเฉลี่ยทั่วทั้งภูมิภาคย่อยที่แสดงแทน

หากมีการใช้ quadtree ของภูมิภาคเพื่อแสดงชุดข้อมูลจุด (เช่น ละติจูดและลองจิจูดของชุดเมือง) ภูมิภาคจะถูกแบ่งย่อยจนกว่าและเว้นแต่แต่ละใบไม้จะมีจุดสูงสุดเพียงจุดเดียว