رباعي الحواف

بنية بيانات الحواف الرباعية هي تمثيل حاسوبي لطوبولوجيا خريطة ثنائية أو ثلاثية الأبعاد ، أي رسم بياني مرسوم على سطح (مغلق) . وقد وصفها لأول مرة خورخي ستولفي وليونيداس ج. غيباس . ^{[ 1 ]} وهي شكل من أشكال بنية بيانات الحواف المجنحة السابقة .

الفكرة الأساسية وراء بنية الحافة الرباعية هي إدراك أن الحافة الواحدة، في بنية الشبكة المضلعة المغلقة، تقع بين وجهين بالضبط ورأسين بالضبط.

تمثل بنية بيانات الحواف الرباعية حافةً، بالإضافة إلى الحواف المتصلة بها حول الرؤوس والوجوه المجاورة لترميز طوبولوجيا الرسم البياني. فيما يلي مثال على تطبيق نوع بيانات الحواف الرباعية.

typedef struct { quadedge_ref e [ 4 ]; } quadedge ;typedef struct { quadedge * next ; unsigned int rot ; } quadedge_ref ;

يحتوي كل ضلع رباعي على أربعة مراجع لأضلاع رباعية مجاورة. يشير كل مرجع من هذه المراجع الأربعة إلى الضلع التالي عكس اتجاه عقارب الساعة حول رأس أو وجه. يمثل كل مرجع من هذه المراجع إما رأس الأصل للضلع، أو الوجه الأيمن، أو رأس الوجهة، أو الوجه الأيسر. يشير كل مرجع ضلع رباعي إلى ضلع رباعي ودوران (من 0 إلى 3) "الذراع" الذي يشير إليه.

بسبب هذا التمثيل، فإن الحافة الرباعية:

• يمثل الرسم البياني، وثنائيته ، وصورته المرآوية.
• يمكن الحصول على الرسم البياني الثنائي ببساطة عن طريق عكس الاصطلاح المتعلق بما هو رأس وما هو وجه؛ و
• يمكن أن يمثل الشكل الأكثر عمومية للخريطة، حيث يسمح برؤوس ووجوه من الدرجة 1 و 2.

يستمد هيكل الحواف الرباعية اسمه من الآلية العامة التي تُخزَّن بها. يخزن هيكل الحافة الواحد، من الناحية النظرية، مراجع لما يصل إلى وجهين ورأسين وأربعة حواف . الحواف الأربعة المخزنة هي الحواف التي تبدأ من الرأسين المتصلين بالوجهين المخزنين .

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

باستخدام بنية رباعية الحواف، يصبح التكرار عبر الطوبولوجيا سهلاً للغاية. غالبًا ما تكون واجهة طوبولوجيات رباعية الحواف عبر حواف موجهة. يسمح هذا بتسمية الرأسين بشكل صريح (بداية ونهاية)، كما يسمح بتسمية الأوجه بشكل صريح أيضًا (يسار ويمين، بالنسبة لشخص يقف على نقطة البداية وينظر في اتجاه النهاية). تُسمى الحواف الأربعة أيضًا، بناءً على الرؤوس والأوجه: بداية-يسار، بداية-يمين، نهاية-يسار، ونهاية-يمين. يمكن عكس اتجاه الحافة الموجهة لتوليد حافة في الاتجاه المعاكس.

إن التكرار حول وجه معين لا يتطلب سوى وجود حافة موجهة واحدة يكون هذا الوجه على يسارها (حسب الاتفاقية) ثم المرور عبر جميع الحواف التي تبدأ من اليسار حتى يتم الوصول إلى الحافة الأصلية.

• حافة مجنحة
• الخرائط التوافقية
• قائمة الحواف المتصلة ثنائياً

• https://www.cs.cmu.edu/afs/andrew/scs/cs/15-463/2001/pub/src/a2/quadedge.html تطبيق رباعي الحواف بلغة C++ .
• http://www.ic.unicamp.br/~stolfi/EXPORT/software/c/2000-05-04/libquad/ تطبيق رباعي الحواف بلغة C.