परिचय (Introduction)
टेम्पलेट पैरामीटर्स के लिए HDS या हाफएज डेटा स्ट्रक्चर (Halfedge Data Structure - संक्षिप्त HalfedgeDS) को एक एज-केंद्रित डेटा स्ट्रक्चर (Edge-centered Data Structure) के रूप में परिभाषित किया जाता है जो वर्टेक्स, एज और फेसेस (Vertices, Edges and Faces) की घटना जानकारी (Incidence Information) को बनाए रखने में सक्षम है, जैसे प्लेनर मैप्स (Planar Maps), पॉलीहेड्रा (Polyhedra), या अन्य ओरिएंटेबल, दो-आयामी सतहें जो यादृच्छिक आयाम में एम्बेडेड हैं। प्रत्येक एज को विपरीत ओरिएंटेशन (Opposite Orientations) के साथ दो हाफएज (Halfedges) में विभाजित किया जाता है। प्रत्येक हाफएज एक घटना फेस (Incident Face) और एक घटना वर्टेक्स (Incident Vertex) स्टोर करता है। प्रत्येक फेस और प्रत्येक वर्टेक्स के लिए एक घटना हाफएज स्टोर किया जाता है। हाफएज डेटा स्ट्रक्चर के कम किए गए संस्करण (Reduced Variants) इस जानकारी में से कुछ को समाप्त कर सकते हैं, जैसे फेस में हाफएज पॉइंटर्स या फेस के स्टोरेज को पूरी तरह से।
हाफएज डेटा स्ट्रक्चर को एक कॉम्बिनेटोरियल डेटा स्ट्रक्चर (Combinatorial Data Structure) के रूप में परिभाषित किया जाता है, ज्यामितीय व्याख्या (Geometric Interpretation) को हाफएज डेटा स्ट्रक्चर के शीर्ष पर बनी क्लासेस द्वारा जोड़ा जाता है। ये क्लासेस हाफएज डेटा स्ट्रक्चर से सीधे लागू करने के लिए अधिक जानी जा सकती हैं, क्योंकि हाफएज डेटा स्ट्रक्चर को एक कार्यान्वयन परत (Implementation Layer) माना जाता है।
हाफएज डेटा स्ट्रक्चर को क्वाड-एज डेटा स्ट्रक्चर (Quad-edge Data Structure) के वेरिएंट्स में से एक के रूप में भी प्रदर्शित किया जा सकता है। सामान्य तौर पर, नॉन-ओरिएंटेबल 2-मैनिफोल्ड्स (Non-orientable 2-manifolds) को क्वाड-एज डेटा द्वारा दर्शाया जा सकता है, लेकिन यहां का संस्करण केवल ओरिएंटेबल 2-मैनिफोल्ड्स तक सीमित है।
उदाहरण प्रोग्राम्स (Example Programs)
डिफ़ॉल्ट हाफएज डेटा स्ट्रक्चर (The Default Halfedge Data Structure)
निम्न उदाहरण प्रोग्राम डिफ़ॉल्ट हाफएज डेटा स्ट्रक्चर और डेकोरेटर क्लास (Decorator Class) को लागू करता है। डिफ़ॉल्ट हाफएज डेटा स्ट्रक्चर एक सूची-आधारित प्रतिनिधित्व (List-based Representation) लागू करता है। आइटम्स की सभी घटनाएं और वर्टेक्स के लिए एक पॉइंट टाइप समझाया गया है। ट्रिवियल ट्रेट्स क्लास (Trivial Traits Class) वर्टेक्स के लिए उपयोग किए जाने वाले टाइप को देता है। प्रोग्राम एक लूप बनाता है, जिसमें दो हाफएज, एक वर्टेक्स (Vertex) और दो फेस (Face1 और Face2) होते हैं, और इसकी वैधता (Validity) की जांच करता है।
#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/HalfedgeDS_decorator.h>
struct Traits {
typedef int 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;
}
