حافة مجنحة

في مجال رسومات الحاسوب ، تُعدّ بنية بيانات الحواف المجنحة طريقةً لتمثيل شبكات المضلعات في ذاكرة الحاسوب . وهي نوع من تمثيل الحدود ، وتصف كلاً من هندسة وطوبولوجيا النموذج. تُستخدم ثلاثة أنواع من السجلات: سجلات الرؤوس، وسجلات الحواف، وسجلات الأوجه. عند إعطاء مرجع لسجل حافة، يُمكن الإجابة على أنواع عديدة من استعلامات التجاور (استعلامات حول الحواف والرؤوس والأوجه المجاورة) في وقت ثابت . يُعدّ هذا النوع من معلومات التجاور مفيدًا لخوارزميات مثل خوارزمية تقسيم الأسطح . ^{[ 1 ]}

يصف هيكل بيانات الحافة المجنحة بوضوح هندسة وطوبولوجيا الأوجه والحواف والرؤوس عندما تلتقي ثلاثة أسطح أو أكثر عند حافة مشتركة. ويكون الترتيب بحيث تُرتّب الأسطح عكس اتجاه عقارب الساعة بالنسبة للاتجاه الأصلي لحافة التقاطع. علاوة على ذلك، يسمح هذا التمثيل بحالات غير مستقرة عدديًا كما هو موضح أدناه.

تتيح بنية بيانات الحافة المجنحة التنقل السريع بين الأوجه والحواف والرؤوس بفضل البنية المرتبطة بشكل واضح للشبكة. وتُنفذ استعلامات التجاور في وقت ثابت مع استهلاك ضئيل للتخزين. هذا الشكل الغني لتحديد شبكة غير منتظمة يتناقض مع المواصفات الأبسط لشبكات المضلعات ، مثل قائمة العقد والعناصر، أو الاتصال الضمني للشبكة المنتظمة . وتُعد بنية بيانات نصف الحافة بديلاً لبنية بيانات الحافة المجنحة .

تعتبر سجلات الوجه والرأس بسيطة نسبيًا، بينما تكون سجلات الحواف أكثر تعقيدًا.

• لكل رأس، يخزن سجله موضع الرأس فقط (مثل الإحداثيات) وإشارة إلى حافة متصلة به. ويمكن العثور على الحواف الأخرى من خلال تتبع المزيد من الإشارات في الحافة.
• وبالمثل، لا يخزن كل سجل وجه سوى مرجع إلى أحد الحواف المحيطة به. ولا حاجة لتخزين اتجاه الحافة بالنسبة للوجه (عكس عقارب الساعة أو مع عقارب الساعة)، إذ يمكن مقارنة الوجه بسهولة مع وجهي الحافة الأيمن والأيسر للحصول على هذه المعلومة.
• وأخيرًا، يكون هيكل سجل الحافة كما يلي. يُفترض أن الحافة موجهة. يحتوي سجل الحافة على مرجعين للرؤوس التي تشكل نقاط نهاية الحافة، ومرجعين للوجوه على جانبي الحافة، وأربعة مراجع للحافتين السابقة واللاحقة المحيطتين بالوجه الأيسر والأيمن.

باختصار، يحتوي سجل الحافة على مراجع لجميع سجلاته المجاورة، سواء عند المرور حول رأس مجاور أو حول وجه مجاور.

فئة الحافة { Vertex *vert_origin, *vert_destination; وجه *الوجه_اليسار، *الوجه_اليمين؛ الحافة *edge_left_cw، *edge_left_ccw, *edge_right_cw, *edge_right_ccw; } فئة الرأس { float x, y, z; حافة *حافة؛ } وجه أنيق { حافة *حافة؛ }

• بنية بيانات رباعية الحواف
• الخرائط التوافقية
• قائمة الحواف المتصلة ثنائياً
• قائمة الوجوه المرتبطة بشكل مزدوج
• بنية بيانات نصف الحافة