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

พื้นที่ย่อยอาจเป็นรูปสี่เหลี่ยมจัตุรัสหรือสี่เหลี่ยมผืนผ้า หรืออาจมีรูปร่างตามอำเภอใจ แม้ว่าจะมีการใช้การแบ่งย่อยที่คล้ายกันนี้มานานแล้ว (เช่น ในทฤษฎีบทWhitney covering lemmaของปี 1934) ^{[ 1 ]}โครงสร้างข้อมูลนี้ได้รับการตั้งชื่อว่า quadtree โดยRaphael FinkelและJL Bentleyในปี 1974 ^{[ 2 ]}การแบ่งส่วนที่คล้ายกันนี้ยังเป็นที่รู้จักกันในชื่อQ- tree

โครงสร้างควอดทรีทุกรูปแบบมีลักษณะร่วมกันบางประการ:

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

พีระมิดต้นไม้ ( T -pyramid ) เป็นต้นไม้ "สมบูรณ์" โดยแต่ละโหนดของ T-pyramid จะมีโหนดลูกสี่โหนด ยกเว้นโหนดใบ โหนดใบทั้งหมดจะอยู่ในระดับเดียวกัน ซึ่งเป็นระดับที่สอดคล้องกับพิกเซลแต่ละพิกเซลในภาพ ข้อมูลในพีระมิดต้นไม้สามารถจัดเก็บได้อย่างกะทัดรัดในอาร์เรย์ในรูปแบบโครงสร้างข้อมูลโดยปริยายคล้ายกับวิธีที่ฮีปไบนารีสามารถจัดเก็บต้นไม้ไบนารีที่สมบูรณ์ได้อย่างกะทัดรัดในอาร์เรย์^{[ 3 ]}

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

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

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

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

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

ควอดทรีจุด^{[ 4 ]}เป็นการดัดแปลงต้นไม้ไบนารีที่ใช้เพื่อแสดงข้อมูลจุดสองมิติ มันมีคุณสมบัติของควอดทรีทั้งหมด แต่เป็นต้นไม้ที่แท้จริงเนื่องจากจุดศูนย์กลางของการแบ่งย่อยจะอยู่บนจุดเสมอ มักจะมีประสิทธิภาพมากในการเปรียบเทียบจุดข้อมูลสองมิติที่เรียงลำดับ โดยปกติจะทำงานใน เวลา O(log n)ควอดทรีจุดนั้นควรค่าแก่การกล่าวถึงเพื่อความสมบูรณ์ แต่พวกมันถูกแซงหน้าโดยต้นไม้k -d ในฐานะเครื่องมือสำหรับการค้นหาไบนารีทั่วไป^{[ 5 ]} ควอดทรีจุดที่มีการแทรกแบบสุ่มได้รับการศึกษาภายใต้ชื่อแลตทิซสุ่มระนาบแบบถ่วงน้ำหนัก^{[ 6 ]}

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

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

โหนดของควอดทรีแบบจุดนั้นคล้ายกับโหนดของต้นไม้ไบนารีโดยมีความแตกต่างที่สำคัญคือมันมีตัวชี้สี่ตัว (หนึ่งตัวสำหรับแต่ละควอดแรนต์) แทนที่จะเป็นสองตัว ("ซ้าย" และ "ขวา") เหมือนในต้นไม้ไบนารีทั่วไป นอกจากนี้ คีย์มักจะถูกแยกออกเป็นสองส่วน ซึ่งหมายถึงพิกัด x และ y ดังนั้น โหนดจึงประกอบด้วยข้อมูลต่อไปนี้:

• สี่ตัวชี้: quad['NW'], quad['NE'], quad['SW'] และ quad['SE']
• จุด ซึ่งประกอบด้วย:
  • สัญลักษณ์; โดยปกติจะแสดงเป็นพิกัด x, y
  • ค่า; ตัวอย่างเช่น ชื่อ

ควอดทรีแบบจุด-ภูมิภาค (PR) ^{[ 7 ] [ 8 ]}คล้ายกับควอดทรีแบบภูมิภาคมาก ความแตกต่างอยู่ที่ประเภทของข้อมูลที่จัดเก็บเกี่ยวกับเซลล์ ในควอดทรีแบบภูมิภาค จะมีการจัดเก็บค่าสม่ำเสมอที่ใช้กับพื้นที่ทั้งหมดของเซลล์ใบ อย่างไรก็ตาม เซลล์ของควอดทรีแบบจุด-ภูมิภาคจะจัดเก็บรายการของจุดที่อยู่ในเซลล์ใบ ดังที่กล่าวไว้ก่อนหน้านี้ สำหรับต้นไม้ที่ใช้กลยุทธ์การแยกส่วนนี้ ความสูงจะขึ้นอยู่กับการกระจายเชิงพื้นที่ของจุด เช่นเดียวกับควอดทรีแบบจุด ควอดทรีแบบจุด-ภูมิภาคอาจมีความสูงเชิงเส้นเมื่อได้รับชุด "ไม่ดี"

เอดจ์ควอดทรี^{[ 9 ] [ 10 ]} (คล้ายกับ PM ควอดทรี) ใช้สำหรับจัดเก็บเส้นแทนจุด เส้นโค้งจะถูกประมาณโดยการแบ่งเซลล์ย่อยให้มีความละเอียดมาก โดยเฉพาะอย่างยิ่งจนกว่าจะมีส่วนของเส้นตรงเพียงเส้นเดียวต่อเซลล์ ใกล้กับมุม/จุดยอด เอดจ์ควอดทรีจะยังคงแบ่งต่อไปจนกว่าจะถึงระดับการแบ่งย่อยสูงสุด ซึ่งอาจส่งผลให้ต้นไม้ไม่สมดุลอย่างมาก ซึ่งอาจทำให้จุดประสงค์ของการทำดัชนีล้มเหลว

ควอดทรีแผนที่รูปหลายเหลี่ยม (หรือ PM Quadtree) เป็นรูปแบบหนึ่งของควอดทรีที่ใช้สำหรับจัดเก็บชุดของรูปหลายเหลี่ยมที่อาจเสื่อมสภาพ (หมายความว่ามีจุดยอดหรือขอบที่แยกออกจากกัน) ^{[ 11 ] [ 12 ]}ความแตกต่างที่สำคัญระหว่าง PM quadtree และ edge quadtree คือเซลล์ที่กำลังพิจารณาจะไม่ถูกแบ่งย่อยหากส่วนต่างๆ มาบรรจบกันที่จุดยอดในเซลล์

PM Quadtree แบ่งออกเป็นสามประเภทหลัก ซึ่งแตกต่างกันไปตามข้อมูลที่จัดเก็บในแต่ละโหนดสีดำ PM3 quadtree สามารถจัดเก็บขอบที่ไม่ตัดกันได้ไม่จำกัดจำนวน และจุดได้มากที่สุดหนึ่งจุด PM2 quadtree เหมือนกับ PM3 quadtree ยกเว้นว่าขอบทั้งหมดต้องมีจุดปลายเดียวกัน สุดท้าย PM1 quadtree คล้ายกับ PM2 แต่โหนดสีดำสามารถบรรจุจุดและขอบของจุดนั้น หรือเพียงแค่ชุดของขอบที่ใช้จุดร่วมกัน แต่ไม่สามารถมีจุดและชุดของขอบที่ไม่มีจุดนั้นอยู่ได้

ส่วนนี้สรุปเนื้อหาย่อยจากหนังสือของSariel Har- Peled ^{[ 13 ]}

หากเราจัดเก็บทุกโหนดที่สอดคล้องกับเซลล์ย่อย เราอาจต้องจัดเก็บโหนดว่างจำนวนมาก เราสามารถลดขนาดของต้นไม้แบบเบาบางเหล่านี้ได้โดยการจัดเก็บเฉพาะต้นไม้ย่อยที่มีข้อมูลที่น่าสนใจ (เช่น "ต้นไม้ย่อยที่สำคัญ") อันที่จริง เราสามารถลดขนาดลงได้อีก เมื่อเราเก็บเฉพาะต้นไม้ย่อยที่สำคัญ กระบวนการตัดแต่งกิ่งอาจทำให้มีเส้นทางยาวในต้นไม้ซึ่งโหนดกลางมีดีกรีสอง (ลิงก์ไปยังผู้ปกครองหนึ่งรายและลูกหนึ่งราย) ปรากฏว่าเราจำเป็นต้องจัดเก็บเฉพาะโหนดที่จุดเริ่มต้นของเส้นทางนี้ (และเชื่อมโยงเมตาเดต้าบางอย่างกับมันเพื่อแสดงถึงโหนดที่ถูกลบออก) และแนบต้นไม้ย่อยที่มีรากอยู่ที่ปลายเส้นทางนั้นเข้ากับ ต้นไม้ที่ถูกบีบอัดเหล่านี้ยังคงมีความสูงเชิงเส้นได้เมื่อได้รับจุดป้อนข้อมูล "ที่ไม่ดี" ${\displaystyle u}$${\displaystyle u}$

แม้ว่าเราจะตัดส่วนของต้นไม้ไปมากเมื่อทำการบีบอัด แต่ก็ยังสามารถค้นหา แทรก และลบข้อมูลได้ในเวลาแบบลอการิทึมโดยใช้ประโยชน์จากเส้นโค้งลำดับZเส้น โค้งลำดับ Zจะแมปแต่ละเซลล์ของควอดทรีแบบเต็ม (และแม้แต่ควอดทรีที่ถูกบีบอัด) ในเวลาไปยังเส้นตรงหนึ่งมิติ (และแมปกลับมาในเวลาด้วย) ทำให้เกิดลำดับที่สมบูรณ์บนองค์ประกอบต่างๆ ดังนั้นเราจึงสามารถจัดเก็บควอดทรีไว้ในโครงสร้างข้อมูลสำหรับเซตที่มีลำดับ (ซึ่งเราจัดเก็บโหนดของต้นไม้ไว้) ${\displaystyle O(1)}$${\displaystyle O(1)}$

ก่อนดำเนินการต่อ เราต้องระบุข้อสมมติฐานที่สมเหตุสมผลก่อน นั่นคือ เราสมมติว่าเมื่อกำหนดจำนวนจริงสองจำนวนที่แสดงในรูปแบบเลขฐานสอง เราสามารถคำนวณดัชนีของบิตแรกที่แตกต่างกันได้ในเวลาที่กำหนด นอกจากนี้ เรายังสมมติว่าเราสามารถคำนวณ บรรพบุรุษร่วมที่ต่ำที่สุดของจุด/เซลล์สองจุดในควอดทรีและกำหนดลำดับ Z สัมพัทธ์ ของพวกมันได้ในเวลาที่กำหนดและเราสามารถคำนวณฟังก์ชันปัดเศษลงได้ในเวลาที่กำหนด ${\displaystyle \alpha ,\beta \in [0,1)}$${\displaystyle O(1)}$${\displaystyle O(1)}$${\displaystyle O(1)}$

ภายใต้สมมติฐานเหล่านี้ การระบุตำแหน่งของจุดที่กำหนด(เช่น การหาเซลล์ที่จะมีจุดนั้นอยู่) การแทรก และการลบ สามารถทำได้ทั้งหมดภายในเวลาที่กำหนด (เช่น เวลาที่ใช้ในการค้นหาในโครงสร้างข้อมูลชุดเรียงลำดับพื้นฐาน) ${\displaystyle q}$${\displaystyle q}$${\displaystyle O(\log {n})}$

ในการระบุตำแหน่งของจุด(เช่น ค้นหาเซลล์ของจุดนั้นในโครงสร้างต้นไม้ที่ถูกบีบอัด): ${\displaystyle q}$

1. ค้นหาเซลล์ที่มีอยู่แล้วในโครงสร้างต้นไม้แบบบีบอัดที่อยู่ก่อนหน้าใน ลำดับ Zเรียกเซลล์นี้ว่า...${\displaystyle q}$${\displaystyle v}$
2. ถ้าเป็นเช่นนั้นให้ส่งคืนค่า.${\displaystyle q\in v}$${\displaystyle v}$
3. หรืออีกวิธีหนึ่ง ให้หาบรรพบุรุษร่วมที่ต่ำที่สุดของจุดและเซลล์ในควอดทรีที่ไม่ถูกบีบอัด เรียกบรรพบุรุษนี้ว่าเซลล์${\displaystyle q}$${\displaystyle v}$${\displaystyle u}$
4. ค้นหาเซลล์ที่มีอยู่แล้วในโครงสร้างต้นไม้แบบบีบอัดที่อยู่ก่อนหน้าใน ลำดับ Zและส่งคืนค่าเซลล์นั้น${\displaystyle u}$

โดยไม่ต้องลงรายละเอียดมากนัก ในการดำเนินการแทรกและลบข้อมูล เราต้องกำหนดตำแหน่งของสิ่งที่ต้องการแทรก/ลบก่อน จากนั้นจึงทำการแทรก/ลบข้อมูลนั้น ต้องระมัดระวังในการปรับโครงสร้างของต้นไม้ให้เหมาะสม โดยการสร้างและลบโหนดตามความจำเป็น

• ภาพประกอบ
• การประมวลผลภาพ
• การสร้างตาข่าย^{[ 14 ]}
• การจัดทำดัชนีเชิงพื้นที่การค้นหาตำแหน่งจุด และการค้นหาช่วง
• การตรวจจับการชนที่มีประสิทธิภาพในสองมิติ
• การคัดกรอง ข้อมูลภูมิประเทศด้วยมุมมองแบบ frustum
• การจัดเก็บข้อมูลกระจัดกระจาย เช่น ข้อมูลการจัดรูปแบบสำหรับสเปรดชีต^{[ 15 ]}หรือสำหรับการคำนวณเมทริกซ์บางอย่าง
• การแก้ปัญหาในสาขา หลายมิติ ( พลศาสตร์ของไหลเชิงคำนวณ , แม่เหล็กไฟฟ้า )
• โปรแกรมจำลองเกมชีวิตของคอนเวย์^{[ 16 ]}
• การประมาณสถานะ^{[ 17 ]}
• การวิเคราะห์ภาพแฟรกทัล
• เซตที่ไม่ทับซ้อนกันสูงสุด

ควอดทรี โดยเฉพาะควอดทรีภูมิภาคเหมาะสมอย่างยิ่งสำหรับการใช้งานการประมวลผลภาพ เราจะจำกัดการอภิปรายของเราไว้ที่ข้อมูลภาพไบนารี แม้ว่าควอดทรีภูมิภาคและการดำเนินการประมวลผลภาพที่ดำเนินการกับควอดทรีเหล่านั้นจะเหมาะสมสำหรับภาพสีเช่นกัน^{[ 5 ] [ 18 ]}

ข้อดีอย่างหนึ่งของการใช้ควอดทรีสำหรับการจัดการภาพคือ การดำเนินการเซตของการรวมและการตัดกันสามารถทำได้ง่ายและรวดเร็ว^{[ 5 ] [ 19 ] [ 20 ] [ 21 ] [ 22 ]} เมื่อมีภาพไบนารีสองภาพ การรวมภาพ (หรือเรียกว่าการซ้อนทับ ) จะสร้างภาพที่พิกเซลเป็นสีดำหากภาพอินพุตภาพใดภาพหนึ่งมีพิกเซลสีดำในตำแหน่งเดียวกัน กล่าวคือ พิกเซลในภาพเอาต์พุตจะเป็นสีขาวก็ต่อเมื่อพิกเซลที่สอดคล้องกันใน ภาพอินพุต ทั้งสองภาพเป็นสีขาว มิฉะนั้นพิกเซลเอาต์พุตจะเป็นสีดำ แทนที่จะดำเนินการทีละพิกเซล เราสามารถคำนวณการรวมได้อย่างมีประสิทธิภาพมากขึ้นโดยใช้ประโยชน์จากความสามารถของควอดทรีในการแสดงพิกเซลหลายพิกเซลด้วยโหนดเดียว สำหรับวัตถุประสงค์ของการอภิปรายด้านล่าง หากซับทรีมีทั้งพิกเซลสีดำและสีขาว เราจะกล่าวว่ารากของซับทรีนั้นมีสีเทา

อัลกอริทึมทำงานโดยการท่องไปในควอดทรีอินพุตสองอัน ( และ) ในขณะที่สร้างควอดทรีเอาต์พุตโดยคร่าวๆ แล้ว อัลกอริทึมมีดังนี้ พิจารณาโหนดและ ที่สอดคล้องกับบริเวณเดียวกันในภาพ ${\displaystyle T_{1}}$${\displaystyle T_{2}}$${\displaystyle T}$${\displaystyle v_{1}\in T_{1}}$${\displaystyle v_{2}\in T_{2}}$

• ถ้าหรือเป็นสีดำ โหนดที่เกี่ยวข้องจะถูกสร้างขึ้นในและถูกระบายสีดำ ถ้ามีเพียงโหนดใดโหนดหนึ่งเป็นสีดำและอีกโหนดหนึ่งเป็นสีเทา โหนดสีเทาจะประกอบด้วยซับทรีอยู่ข้างใต้ ซับทรีนี้ไม่จำเป็นต้องถูกสำรวจ${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle T}$
• ถ้า(ตามลำดับ) เป็นสีขาว(ตามลำดับ) และซับทรีที่อยู่ข้างใต้ (ถ้ามี) จะถูกคัดลอกไปยัง${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle v_{2}}$${\displaystyle v_{1}}$${\displaystyle T}$
• ถ้าทั้งและ เป็นสีเทา ระบบ จะพิจารณาเฉพาะลูกที่สอดคล้องกันของและ เท่านั้น${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle v_{1}}$${\displaystyle v_{2}}$

แม้ว่าอัลกอริทึมนี้จะใช้งานได้ แต่ก็ไม่ได้รับประกันว่าควอดทรีจะมีขนาดเล็กที่สุดเสมอไป ตัวอย่างเช่น ลองพิจารณาผลลัพธ์หากเรารวมกระดานหมากรุก (โดยที่แต่ละช่องเป็นพิกเซล) ที่มีขนาด เท่ากับส่วนเติมเต็ม ผลลัพธ์ที่ได้คือสี่เหลี่ยมจัตุรัสสีดำขนาดใหญ่ ซึ่งควรจะแสดงด้วยควอดทรีที่มีเพียงโหนดราก (สีดำ) แต่แทนที่จะเป็นเช่นนั้น อัลกอริทึมกลับสร้างต้นไม้ 4-ary เต็มรูปแบบที่มีความลึกเพื่อแก้ไขปัญหานี้ เราจึงทำการสำรวจควอดทรีที่ได้แบบจากล่างขึ้นบน โดยตรวจสอบว่าโหนดลูกทั้งสี่มีสีเดียวกันหรือไม่ ในกรณีดังกล่าว เราจะแทนที่โหนดแม่ด้วยโหนดใบที่มีสีเดียวกัน^{[ 5 ]}${\displaystyle 2^{k}\times 2^{k}}$${\displaystyle k}$

การหาจุดตัดของภาพสองภาพนั้นใช้ขั้นตอนวิธีเกือบเหมือนกัน วิธีคิดอย่างหนึ่งเกี่ยวกับการหาจุดตัดของภาพสองภาพก็คือ เรากำลังทำการรวมกันโดยพิจารณาจาก พิกเซล สีขาวดังนั้น ในการหาจุดตัด เราจึงสลับการกล่าวถึงสีดำและสีขาวในขั้นตอนวิธีรวมกัน

พิจารณาพิกเซลสีดำสองพิกเซลที่อยู่ติดกันในภาพไบนารี พิกเซลเหล่านั้นจะอยู่ติดกันหากมีขอบแนวนอนหรือแนวตั้งร่วมกัน โดยทั่วไป พิกเซลสีดำสองพิกเซลจะเชื่อมต่อกันหากสามารถเข้าถึงพิกเซลหนึ่งจากอีกพิกเซลหนึ่งได้โดยการเคลื่อนที่ไปยังพิกเซลที่อยู่ติดกันเท่านั้น (กล่าวคือ มีเส้นทางของพิกเซลสีดำระหว่างพิกเซลทั้งสอง โดยที่แต่ละคู่ที่อยู่ติดกัน) แต่ละชุดของพิกเซลสีดำที่เชื่อมต่อกันมากที่สุดเรียกว่าส่วนประกอบที่เชื่อมต่อกันการใช้การแสดงภาพแบบควอดทรีSamet ^{[ 23 ]} ได้แสดงให้เห็นว่าเราสามารถค้นหาและติดป้ายกำกับส่วนประกอบที่เชื่อมต่อกันเหล่านี้ได้ในเวลาที่เป็นสัดส่วนกับขนาดของควอดทรี^{[ 5 ] [ 24 ]}อัลกอริทึมนี้ยังสามารถใช้สำหรับการระบายสีรูปหลายเหลี่ยมได้อีกด้วย

อัลกอริทึมนี้ทำงานโดยมีสามขั้นตอน:

1. กำหนดความสัมพันธ์ที่อยู่ติดกันระหว่างพิกเซลสีดำ
2. ประมวลผลความสัมพันธ์สมมูลจากขั้นตอนแรกเพื่อให้ได้ป้ายกำกับที่ไม่ซ้ำกันสำหรับแต่ละส่วนประกอบที่เชื่อมต่อกัน
3. ติดป้ายกำกับพิกเซลสีดำด้วยป้ายกำกับที่เชื่อมโยงกับส่วนประกอบที่เชื่อมต่ออยู่

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

ขั้นตอนแรกทำได้โดย การท่อง ต้นไม้ควอดทรีแบบโพสต์ออร์เดอ ร์ สำหรับใบสีดำแต่ละใบ เราจะดูที่โหนดหรือกลุ่มโหนดที่แสดงถึงเซลล์ที่เป็นเพื่อนบ้านทางเหนือและเพื่อนบ้านทางตะวันออก (กล่าวคือ เซลล์ทางเหนือและตะวันออกที่ใช้ขอบร่วมกับเซลล์ของ) เนื่องจากต้นไม้จัดเรียงตาม ลำดับ Zเราจึงมีข้อคงที่ว่าเพื่อนบ้านทางใต้และทางตะวันตกได้รับการดูแลและพิจารณาไปแล้ว ให้เพื่อนบ้านทางเหนือหรือทางตะวันออกที่กำลังพิจารณาอยู่เป็นถ้าแทนพิกเซลสีดำ: ${\displaystyle v}$${\displaystyle v}$${\displaystyle u}$${\displaystyle u}$

• ถ้าเซลล์ใด เซลล์หนึ่งมีป้ายกำกับ ให้กำหนดป้ายกำกับนั้นให้กับเซลล์อีกเซลล์หนึ่ง${\displaystyle u}$${\displaystyle v}$
• หากทั้งสองไม่มีป้ายกำกับ ให้สร้างป้ายกำกับขึ้นมาและกำหนดป้ายกำกับนั้นให้กับทั้งสอง
• ถ้าและมีป้ายกำกับที่แตกต่างกัน ให้บันทึกความเท่าเทียมกันของป้ายกำกับนี้แล้วดำเนินการต่อไป${\displaystyle u}$${\displaystyle v}$

ขั้นตอนที่สองสามารถทำได้โดยใช้โครงสร้างข้อมูลยูเนียน-ฟินด์ [ ^{25 ] เรา}เริ่มต้นด้วยป้ายกำกับที่ไม่ซ้ำกันแต่ละป้ายเป็นชุดแยกต่างหาก สำหรับความสัมพันธ์สมมูลทุกรายการที่ระบุไว้ในขั้นตอนแรก เราจะรวมชุดที่สอดคล้องกันเข้าด้วยกัน หลังจากนั้น ชุดที่เหลือที่แตกต่างกันแต่ละชุดจะเชื่อมโยงกับส่วนประกอบที่เชื่อมต่อกันที่แตกต่างกันในภาพ

ขั้นตอนที่สามดำเนินการท่องต้นไม้แบบโพสต์ออร์เดอร์อีกครั้ง คราวนี้ สำหรับแต่ละโหนดสีดำ เราใช้การดำเนินการ findของ union-find (โดยใช้ป้ายกำกับเดิมของ) เพื่อค้นหาและกำหนดป้ายกำกับใหม่ (ซึ่งเชื่อมโยงกับส่วนประกอบที่เชื่อมต่อของ ซึ่งเป็นส่วนหนึ่งของ ) ${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$

ส่วนนี้สรุปบทหนึ่งจากหนังสือของ Har-Peled และ de Berg และคณะ^{[ 26 ] [ 27 ]}

การสร้างตาข่าย (Mesh generation)โดยพื้นฐานแล้วคือการแบ่งชุดจุดออกเป็นรูปสามเหลี่ยมเพื่อนำไปประมวลผลต่อ ดังนั้น จึงเป็นที่พึงปรารถนาให้รูปสามเหลี่ยมที่ได้มีคุณสมบัติบางอย่าง (เช่น ความไม่สม่ำเสมอ รูปสามเหลี่ยมที่ไม่ "ผอมเกินไป" รูปสามเหลี่ยมขนาดใหญ่ในบริเวณที่เบาบาง และรูปสามเหลี่ยมขนาดเล็กในบริเวณที่หนาแน่น เป็นต้น) เพื่อให้การประมวลผลต่อไปรวดเร็วและลดโอกาสเกิดข้อผิดพลาด โครงสร้างแบบควอดทรี (Quadtrees) ที่สร้างขึ้นจากชุดจุดสามารถนำมาใช้สร้างตาข่ายที่มีคุณสมบัติตามที่ต้องการเหล่านี้ได้

พิจารณาใบของควอดทรีและเซลล์ที่สอดคล้องกันเรากล่าวว่า ควอดทรี นั้นสมดุล ( สำหรับการสร้างตาข่าย) หากด้านของเซลล์ถูกตัดโดยจุดมุมของเซลล์ข้างเคียงไม่เกินหนึ่งครั้งในแต่ละด้าน ซึ่งหมายความว่าระดับควอดทรีของใบที่อยู่ติดกับจะแตกต่างจากระดับของเซลล์ไม่เกินหนึ่ง เมื่อเงื่อนไขนี้เป็นจริงสำหรับใบทั้งหมด เรากล่าวว่าควอดทรีทั้งหมดสมดุล (สำหรับการสร้างตาข่าย) ${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$

พิจารณาเซลล์และบริเวณใกล้เคียงของเซลล์ที่มีขนาดเท่ากันซึ่งมีจุดศูนย์กลางอยู่ที่ เซลล์ นั้น เราเรียกบริเวณใกล้เคียงนี้ว่าคลัสเตอร์ขยายเรากล่าวว่าควอดทรีมีความสมดุลดี (well-balanced)หากควอดทรีนั้นมีความสมดุล และสำหรับทุกใบที่ประกอบด้วยจุดจากเซตของจุด คลัสเตอร์ขยายของใบนั้นก็อยู่ในควอดทรีด้วย และคลัสเตอร์ขยายนั้นไม่มีจุดอื่นใดจากเซตของจุดนั้น ${\displaystyle v}$${\displaystyle 5\times 5}$${\displaystyle v}$${\displaystyle u}$

การสร้างตาข่ายทำได้ดังนี้:

1. สร้างโครงสร้างข้อมูลแบบควอดทรีบนจุดข้อมูลขาเข้า
2. ตรวจสอบให้แน่ใจว่าควอดทรีมีความสมดุล สำหรับทุกใบ หากมีเพื่อนบ้านที่ใหญ่เกินไป ให้แบ่งเพื่อนบ้านนั้นออกเป็นส่วนย่อย ทำซ้ำเช่นนี้จนกว่าต้นไม้จะสมดุล นอกจากนี้ เรายังตรวจสอบให้แน่ใจว่าสำหรับใบที่มีจุดอยู่ โหนดสำหรับคลัสเตอร์ขยายของแต่ละใบนั้นอยู่ในต้นไม้ด้วย
3. สำหรับโหนดใบทุกโหนดที่มีจุด หากคลัสเตอร์ที่ขยายออกไปมีจุดอื่นอีก เราจะแบ่งต้นไม้ต่อไปอีกและปรับสมดุลใหม่ตามความจำเป็น หากจำเป็นต้องแบ่งย่อย สำหรับลูกแต่ละตัวของเราจะตรวจสอบให้แน่ใจว่าโหนดของคลัสเตอร์ที่ขยายออกไปของ อยู่ในต้นไม้ (และปรับสมดุลใหม่ตามที่ต้องการ)${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$
4. ทำซ้ำขั้นตอนก่อนหน้าจนกว่าต้นไม้จะสมดุลดี
5. แปลงโครงสร้างควอดทรีให้เป็นโครงสร้างสามเหลี่ยม

เราพิจารณาจุดมุมของเซลล์ต้นไม้เป็นจุดยอดในการสร้างสามเหลี่ยมของเรา ก่อนขั้นตอนการแปลง เรามีกล่องจำนวนมากที่มีจุดอยู่ในบางกล่อง ขั้นตอนการแปลงจะทำในลักษณะต่อไปนี้: สำหรับแต่ละจุด ให้บิดมุมที่ใกล้ที่สุดของเซลล์เพื่อให้มาบรรจบกัน และสร้างสามเหลี่ยมจากรูปสี่เหลี่ยมจัตุรัสทั้งสี่ที่ได้ เพื่อสร้างสามเหลี่ยมที่ "สวยงาม" (ผู้อ่านที่สนใจสามารถดูรายละเอียดเพิ่มเติมเกี่ยวกับสิ่งที่ทำให้สามเหลี่ยม "สวยงาม" ได้ ในบทที่ 12 ของ Har-Peled ^{[ 26 ] )}

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

สุดท้ายแล้ว เราก็จะได้โครงข่ายสามเหลี่ยมที่สวยงามของชุดจุดที่เราสร้างขึ้นจากโครงสร้างควอดทรี

รหัสเทียมต่อไปนี้แสดงวิธีการหนึ่งในการสร้างโครงสร้างข้อมูลแบบควอดทรีซึ่งจัดการเฉพาะจุดเท่านั้น ยังมีวิธีการอื่นๆ อีก

สันนิษฐานว่ามีการใช้งานโครงสร้างเหล่านี้

// วัตถุพิกัดอย่างง่ายเพื่อแสดงจุดและเวกเตอร์struct XY { float x ; float y ; function __construct ( float _x , float _y ) {...} } // กล่องขอบเขตที่จัดแนวตามแกนพร้อมมิติครึ่งหนึ่งและจุดศูนย์กลางstruct AABB { XY center ; float halfDimension ; function __construct ( XY _center , float _halfDimension ) {...} function containsPoint ( XY point ) {...} function intersectsAABB ( AABB other ) {...} }

คลาสนี้แสดงถึงทั้งควอดทรีหนึ่งต้นและโหนดที่เป็นรากของควอดทรีนั้น

คลาสQuadTree { // ค่าคงที่ที่กำหนดจำนวนองค์ประกอบที่สามารถจัดเก็บในโหนด QuadTree นี้ได้constant int QT_NODE_CAPACITY = 4 ; // กล่องขอบเขตที่จัดเรียงตามแกนซึ่งจัดเก็บเป็นจุดศูนย์กลางที่มีขนาดครึ่งหนึ่ง// เพื่อแสดงขอบเขตของ QuadTree นี้AABB boundary ; // จุดในโหนด QuadTree นี้Array of XY [ size = QT_NODE_CAPACITY ] points ; // ลูกQuadTree * northWest ; QuadTree * northEast ; QuadTree * southWest ; QuadTree * southEast ; // เมธอดfunction __construct ( AABB_boundary ) {...} function insert ( XY p ) {...} function subdivide () {...} // สร้างลูกสี่ตัวที่แบ่ง Quad นี้ออกเป็นสี่ Quad ที่มีพื้นที่เท่ากันfunction queryRange ( AABB range ) {... } }

วิธีการต่อไปนี้จะแทรกจุดลงในควอดที่เหมาะสมของควอดทรี โดยจะทำการแบ่งหากจำเป็น

คลาสQuadTree { ... // แทรกจุดลงใน QuadTree ฟังก์ชันinsert ( XY p ) { // ละเว้นวัตถุที่ไม่เกี่ยวข้องกับ QuadTree นี้หาก( ! boundary . containsPoint ( p )) ให้คืนค่าfalse ; // ไม่สามารถเพิ่มวัตถุได้// หากมีพื้นที่ว่างใน QuadTree นี้และไม่มีการแบ่งย่อย ให้เพิ่มวัตถุที่นี่หาก( points . size < QT_NODE_CAPACITY && northWest == null ) { points . append ( p ); ให้คืนค่า true ; } // มิฉะนั้น ให้แบ่งย่อยแล้วเพิ่มจุดไปยังโหนดใดก็ได้ที่ยอมรับได้หาก( northWest == null ) subdivide (); // เราต้องเพิ่มจุด/ข้อมูลที่อยู่ในอาร์เรย์ Quad นี้ไปยัง Quad ใหม่ หากเราต้องการให้// โหนดสุดท้ายเก็บข้อมูล เท่านั้น หาก( northWest -> insert ( p )) ให้คืนค่าtrue ; หาก( northEast -> insert ( p )) ให้คืนค่าtrue ; หาก( southWest -> insert ( p )) ให้คืนค่าtrue ; ถ้า( southEast -> insert ( p )) ให้คืนค่าtrue ; // มิฉะนั้น จะไม่สามารถแทรกจุดได้ด้วยเหตุผลบางอย่างที่ไม่ทราบสาเหตุ (ซึ่งไม่ควรเกิดขึ้น) ให้คืนค่าfalse ; } }

วิธีการต่อไปนี้จะค้นหาจุดทั้งหมดที่อยู่ในช่วงที่กำหนด

คลาสQuadTree { ... // ค้นหาจุดทั้งหมดที่ปรากฏภายในช่วงฟังก์ชันqueryRange ( AABB range ) { // เตรียมอาร์เรย์ของผลลัพธ์อาร์เรย์ของ จุด XY pointsInRange ; // ยกเลิกโดยอัตโนมัติหากช่วงไม่ตัดกับรูปสี่เหลี่ยมนี้if ( ! boundary . intersectsAABB ( range )) return pointsInRange ; // รายการว่าง// ตรวจสอบวัตถุในระดับรูปสี่เหลี่ยมนี้for ( int p = 0 ; p < points . size ; p ++ ) { if ( range . containsPoint ( points [ p ])) pointsInRange . append ( points [ p ]); } // สิ้นสุดที่นี่ หากไม่มีลูกif ( northWest == null ) return pointsInRange ; // มิฉะนั้น ให้เพิ่มจุดจากลูกpointsInRange . appendArray ( northWest -> queryRange ( range )); pointsInRange . appendArray ( northEast -> queryRange ( range )); pointsInRange.appendArray ( southWest- > queryRange ( range ) ) ; pointsInRange.appendArray ( southEast- > queryRange ( range ) ) ; return pointsInRange ; } }

• การปรับแต่งตาข่ายแบบปรับได้
• การแบ่งพื้นที่ไบนารี
• การปูพื้นแบบไบนารี
• ต้นไม้k -d
• อ็อกทรี
• อาร์-ทรี
• ต้นไม้ UB
• ฐานข้อมูลเชิงพื้นที่
• การปูผิวทาง
• เส้นโค้งลำดับ Z