DCEL
פעולות נוספות
רשימת צלעות מקושרת כפולה (באנגלית: Doubly Connected Edge List ובקיצור DCEL), המכונה גם מבנה נתונים חצי-צלע (Half-edge data structure), היא מבנה נתונים המשמש לייצוג שיכון של גרף מישורי במישור, וכן לייצוג פאונים במרחב תלת-ממדי. מבנה נתונים זה מאפשר מניפולציה יעילה של המידע הטופולוגי הקשור לאובייקטים הנדונים (צמתים, צלעות ופאות). הוא נמצא בשימוש באלגוריתמים רבים בגאומטריה חישובית לטיפול בחלוקות פוליגוניות של המישור, המכונות לרוב גרף קווי ישר מישורי (PSLG). לדוגמה, דיאגרמת וורונוי מיוצגת בדרך כלל באמצעות DCEL בתוך תיבה תוחמת.
מבנה נתונים זה הוצע במקור על ידי מולר ופרפרטה (Muller ו-Preparata)[1] לצורך ייצוג של פאונים קמורים בתלת-ממד. גרסאות פשוטות של מבנה הנתונים, כפי שמתוארות כאן, מתייחסות רק לגרפים קשירים, אך ניתן להרחיב את מבנה ה-DCEL לטיפול גם בגרפים שאינם קשירים על ידי הוספת צלעות דמה ("dummy edges") בין רכיבי קשירות שונים.[2]
מבנה הנתונים עריכה
DCEL הוא יותר מאשר סתם רשימה מקושרת דו-כיוונית של צלעות. במקרה הכללי, ה-DCEL מכיל רשומה עבור כל צלע, צומת ופאה בחלוקה. כל רשומה עשויה להכיל מידע נוסף; למשל, רשומת פאה יכולה להכיל את שם האזור. כל צלע תוחמת בדרך כלל שתי פאות, ולכן נוח להתייחס לכל צלע כשתי "חצי-צלעות" (המיוצגות על ידי שתי צלעות בעלות כיוונים מנוגדים בין שני צמתים, כפי שניתן לראות באיור משמאל).
כל חצי-צלע "משויכת" לפאה אחת בלבד ולכן מחזיקה מצביע לאותה פאה. כל חצי-הצלעות המשויכות לפאה מסוימת מכוונות בכיוון השעון או נגד כיוון השעון. לדוגמה, באיור משמאל, כל חצי-הצלעות המשויכות לפאה האמצעית (כלומר, חצי-הצלעות ה"פנימיות") מכוונות נגד כיוון השעון. לחצי-צלע יש מצביע לחצי-הצלע הבאה ולחצי-הצלע הקודמת באותה פאה. כדי להגיע לפאה השנייה, ניתן לעבור לחצי-הצלע ה"תאומה" (twin) של חצי-הצלע הנוכחית, ואז לסרוק את הפאה האחרת. כל חצי-צלע מחזיקה גם מצביע לצומת המקור שלה (ניתן להשיג את צומת היעד על ידי שאילתת המקור של התאומה שלה, או של חצי-הצלע הבאה).
כל צומת מכיל את הקואורדינטות שלו ומאחסן מצביע לצלע שרירותית שיוצאת ממנו (כלומר, שהצומת הוא המקור שלה). כל פאה מאחסנת מצביע לחצי-צלע כלשהי בגבולה החיצוני (אם הפאה אינה חסומה, המצביע יהיה null). כמו כן, היא מחזיקה רשימה של חצי-צלעות, אחת עבור כל חור שעשוי להימצא בתוך הפאה. אם הצמתים או הפאות אינם מכילים מידע רלוונטי, אין צורך לאחסן אותם, ובכך ניתן לחסוך במקום ולצמצם את מורכבות מבנה הנתונים.