โครงสร้างข้อมูลครึ่งขอบ

แนะนำตัว

HDS สำหรับพารามิเตอร์เทมเพลตหรือโครงสร้างข้อมูล halfedge (ย่อมาจาก HalfedgeDS) ถูกกำหนดให้เป็นโครงสร้างข้อมูลแบบ edge-centered ที่สามารถรักษาข้อมูลอุบัติการณ์ของจุดยอด ขอบและใบหน้าได้ เช่น แผนที่ระนาบ รูปทรงหลายเหลี่ยม หรือทิศทางแบบสองมิติอื่นๆ พื้นผิวที่ฝังอยู่ในมิติสุ่ม ขอบแต่ละด้านแบ่งออกเป็นสองขอบครึ่งโดยมีทิศทางตรงกันข้าม ขอบครึ่งหนึ่งแต่ละอันเก็บหนึ่งใบหน้าของเหตุการณ์และหนึ่งจุดยอดของเหตุการณ์ ครึ่งหนึ่งของเหตุการณ์ที่เกิดขึ้นจะถูกเก็บไว้สำหรับแต่ละใบหน้าและแต่ละจุดยอด รูปแบบที่ลดลงของโครงสร้างข้อมูล halfedge อาจทำให้ข้อมูลบางส่วนหายไปได้ เช่น ตัวชี้ halfedge ในใบหน้า หรือการจัดเก็บข้อมูลใบหน้าเลย

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

โครงสร้างข้อมูล halfedge ยังสามารถแสดงเป็นหนึ่งในตัวแปรของโครงสร้างข้อมูล quad-edge โดยทั่วไป 2-manifolds แบบปรับทิศทางไม่ได้สามารถแสดงด้วยข้อมูลแบบ quad-edge แต่ตัวแปรที่นี่จำกัดเฉพาะ 2-manifolds ที่ปรับทิศทางได้เท่านั้น

ตัวอย่างโปรแกรม

โครงสร้างข้อมูล Halfedge เริ่มต้น

โปรแกรมตัวอย่างต่อไปนี้ใช้โครงสร้างข้อมูล halfedge เริ่มต้นและคลาสมัณฑนากร โครงสร้างข้อมูล halfedge เริ่มต้นใช้การแสดงตามรายการ มีการอธิบายอุบัติการณ์ทั้งหมดของรายการและประเภทจุดสำหรับจุดยอด คลาสคุณสมบัติเล็กน้อยให้ประเภทที่นำไปใช้กับประเด็น โปรแกรมสร้างการวนซ้ำ ซึ่งประกอบด้วยสอง halfedges, one vertex(Vertex) และ two faces (Face1 และ Face2) และยืนยันความถูกต้อง

#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/HalfedgeDS_decorator.h>
struct Traits { typedefint Point_2; };
typedef CGAL::HalfedgeDS_default<Traits> HDS1;
typedef CGAL::HalfedgeDS_decorator<HDS> Decorator1;
int main() {
   HDS1 hds1;
   Decorator1 decorator(hds1);
   decorator.create_loop();
   CGAL_assertion(decorator.is_valid());
   return 0;
}