גיאומטריה חישובית — מרחב למידה אישי

ברוכים הבאים לשיעור בנושא טריאנגולציות דלוני, אחד המושגים המרכזיים והשימושיים ביותר בגיאומטריה חישובית. טריאנגולציות דלוני מהוות בסיס לאלגוריתמים רבים בתחומי הגרפיקה הממוחשבת, מערכות מידע גיאוגרפיות (GIS), סימולציות מדעיות ועוד. בשיעור זה נצלול לעומק ההגדרה, נבין את הקשר ההדוק שלהן לדיאגרמות וורונוי, נלמד על הקריטריון המאפיין אותן ונבחן שיטות לבנייתן, תוך התמקדות בבנייה אינקרמנטלית. הבנה יסודית של נושא זה חיונית להצלחה בקורס.

הגדרת טריאנגולציית דלוני ותכונותיה הבסיסיות

טריאנגולציית דלוני היא סוג ספציפי של טריאנגולציה של קבוצת נקודות במישור, המאופיינת בתכונה אופטימלית ייחודית. היא קרויה על שם המתמטיקאי בוריס דלוני.

טריאנגולציית דלוני (Delaunay Triangulation): עבור קבוצת נקודות נתונה P במישור, טריאנגולציית דלוני היא טריאנגולציה של הקמור של P, כך שאף נקודה מ-P אינה נמצאת בתוך המעגל החוסם של אף משולש בטריאנגולציה.

תכונה זו ידועה כ"קריטריון המעגל הריק" והיא הליבה להבנת טריאנגולציות דלוני.

קריטריון המעגל הריק (Empty Circle Criterion): מעגל חוסם של משולש בטריאנגולציית דלוני אינו מכיל אף נקודה אחרת מקבוצת הנקודות המקורית P בפנימו. נקודות על ההיקף מותרות, אך רק אם הן קודקודי המשולש או קודקודים של משולשים סמוכים החולקים את אותה קשת.

תכונות אופטימליות:

מקסימום זווית מינימלית: טריאנגולציית דלוני ממקסמת את הזווית המינימלית מבין כל הזוויות בכל המשולשים בטריאנגולציה, ובכך נמנעת ככל הניתן מיצירת משולשים "צרים" או "שטוחים" (slivers). תכונה זו חשובה מאוד ביישומים מספריים.
קשתות דלוני: קשת היא קשת דלוני אם קיים מעגל העובר דרך קצותיה ואינו מכיל אף נקודה אחרת מ-P. כל הקשתות בטריאנגולציית דלוני הן קשתות דלוני.

טריאנגולציית דלוני

עומדת בקריטריון המעגל הריק. ממקסמת את הזווית המינימלית, ולכן מייצרת משולשים "שמנים" יותר. שימושית מאוד ביישומים הדורשים איכות משולשים גבוהה.

טריאנגולציה שרירותית

כל חלוקה של הקמור של P למשולשים שקודקודיהם הם נקודות מ-P, ללא חיתוך קשתות. אינה בהכרח עומדת בקריטריון המעגל הריק ועלולה להכיל משולשים צרים מאוד.

הקשר לדיאגרמת וורונוי

טריאנגולציית דלוני ודיאגרמת וורונוי הן מבנים דואליים בגיאומטריה חישובית. הבנת הקשר ביניהן חיונית להבנת שתיהן.

דיאגרמת וורונוי (Voronoi Diagram): עבור קבוצת נקודות P, דיאגרמת וורונוי מחלקת את המישור לתאים, כאשר כל תא מכיל את כל הנקודות במישור הקרובות ביותר לנקודה מסוימת מ-P מאשר לכל נקודה אחרת מ-P.

הקשר הדואלי בין דלוני לוורונוי: נושא זה הוא ליבת ההבנה של שני המבנים ומופיע רבות במבחנים! חשוב להבין שקודקודי דיאגרמת וורונוי הם מרכזי המעגלים החוסמים של משולשי דלוני, וקשתות דיאגרמת וורונוי הן קטעים המחברים בין מרכזי מעגלים חוסמים של משולשי דלוני סמוכים. קיימת התאמה חד-חד-ערכית בין קודקודים, קשתות ופאות של מבנה אחד לאלו של השני.

כיצד הקשר מתבטא:

קודקודי דיאגרמת וורונוי הם נקודות הנמצאות במרחק שווה משלוש (או יותר) נקודות מקבוצת P. נקודות אלו הן בדיוק מרכזי המעגלים החוסמים של משולשי דלוני.
קשתות דיאגרמת וורונוי הן קטעים של אנכים אמצעיים המחברים בין מרכזי מעגלים חוסמים של משולשי דלוני סמוכים.
שתי נקודות P_i ו-P_j מחוברות בקשת בטריאנגולציית דלוני אם ורק אם תאי וורונוי שלהן סמוכים (חולקים קשת משותפת).

בנייה אינקרמנטלית של טריאנגולציית דלוני

אחת הגישות הנפוצות והאלגנטיות לבניית טריאנגולציית דלוני היא בנייה אינקרמנטלית, שבה מוסיפים נקודות אחת-אחת ומעדכנים את הטריאנגולציה הקיימת.

בנייה אינקרמנטלית (Incremental Construction): אלגוריתם שבו מוסיפים נקודות לקבוצה בהדרגה, ועם כל הוספת נקודה, מעדכנים את המבנה הגיאומטרי (במקרה זה, טריאנגולציית דלוני) כדי לשמור על תכונותיו.

שלבי האלגוריתם הבסיסי:

הכנה: מתחילים עם "משולש על" (super-triangle) גדול מספיק שמכיל את כל נקודות הקלט. משולש זה אינו חלק מהטריאנגולציה הסופית וקודקודיו יוסרו בסוף.
הוספת נקודה: עבור כל נקודה P_new בקבוצת הקלט (בסדר אקראי לרוב):
- איתור משולש: מוצאים את המשולש T בטריאנגולציה הנוכחית שמכיל את P_new.
- פיצול משולש: מחלקים את T לשלושה משולשים חדשים על ידי חיבור P_new לקודקודי T.
- תיקון (Edge Flipping): בודקים את קריטריון המעגל הריק עבור כל הקשתות שנוצרו או שונו. אם קשת מסוימת אינה עומדת בקריטריון (כלומר, המעגל החוסם של אחד משני המשולשים הסמוכים לה מכיל את הקודקוד הרביעי), מבצעים "היפוך קשת" (edge flip). תהליך זה ממשיך באופן רקורסיבי או איטרטיבי עד שכל הקשתות עומדות בקריטריון.
סיום: מסירים את כל המשולשים המחוברים לקודקודי ה"משולש על" המקורי.

היפוך קשתות (Edge Flipping): פעולה שבה קשת משותפת לשני משולשים (יוצרת מרובע קמור) מוחלפת בקשת האלכסונית השנייה של אותו מרובע, במטרה לשמר את קריטריון המעגל הריק. היפוך קשת מבטיח שהזווית המינימלית במרובע תגדל או תישאר זהה.

מורכבות:

המורכבות הממוצעת של בנייה אינקרמנטלית היא O(N log N) עבור N נקודות, כאשר איתור המשולש נעשה ביעילות (למשל, באמצעות מבנה נתונים למיקום נקודות). במקרה הגרוע, המורכבות יכולה להיות גבוהה יותר.

שאלות לדיון

הסבר את קריטריון המעגל הריק וכיצד הוא מבטיח את התכונה האופטימלית של טריאנגולציית דלוני.
תאר את הקשר הדואלי בין טריאנגולציית דלוני לדיאגרמת וורונוי. כיצד ניתן לבנות אחת מהשנייה?
פרט את השלבים העיקריים באלגוריתם לבנייה אינקרמנטלית של טריאנגולציית דלוני. הדגש את תפקיד פעולת "היפוך הקשתות".
מדוע טריאנגולציית דלוני עדיפה על פני טריאנגולציה שרירותית ביישומים מסוימים, כגון מידול שטח או שיטות אלמנטים סופיים?

נקודות לתשובת מודל

להלן נקודות מפתח לתשובה מקיפה לשאלה על הקשר בין דלוני לוורונוי:

הגדרה של כל מבנה: הגדרת טריאנגולציית דלוני (קריטריון המעגל הריק) והגדרת דיאגרמת וורונוי (תאי הקרבה).
דואליות: הדגשת העובדה שהם מבנים דואליים, כלומר, יש התאמה בין רכיבי האחד לרכיבי השני.
קודקודים: קודקודי וורונוי הם מרכזי המעגלים החוסמים של משולשי דלוני. כל קודקוד וורונוי הוא נקודה הנמצאת במרחק שווה משלוש (או יותר) נקודות מקבוצת הקלט.
קשתות: קשתות וורונוי הן קטעים של אנכים אמצעיים המחברים בין מרכזי מעגלים חוסמים של משולשי דלוני סמוכים. קשת דלוני מחברת P_i ו-P_j אם ורק אם תאי וורונוי של P_i ו-P_j חולקים קשת משותפת.
פאות: פאות וורונוי הן תאי וורונוי המוקצים לכל נקודה P_i. פאות דלוני הן המשולשים.
בנייה הדדית: ניתן לבנות את דיאגרמת וורונוי על ידי מציאת המעגלים החוסמים של משולשי דלוני וחיבור המרכזים שלהם. ולהיפך, ניתן לבנות את טריאנגולציית דלוני על ידי חיבור נקודות שקיימת קשת משותפת בין תאי וורונוי שלהן.

מצאתם טעות או שחסר משהו?