יחידה 4: טריאנגולציה של מצולעים

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

הגדרת טריאנגולציה ומאפיינים בסיסיים

לפני שנדון בטריאנגולציה, עלינו להגדיר מצולע פשוט.

מאפיינים חשובים של טריאנגולציה:

• לכל מצולע פשוט עם n קודקודים קיימת טריאנגולציה.
• בכל טריאנגולציה של מצולע פשוט עם n קודקודים, מספר המשולשים הוא תמיד n-2.
• מספר האלכסונים הפנימיים (צלעות המשולשים שאינן צלעות המצולע המקורי) הוא תמיד n-3.

אלגוריתם אוזניים (Ear Clipping) לטריאנגולציה

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

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

1. אתחל רשימה של קודקודי המצולע בסדר מסוים (למשל, נגד כיוון השעון).
2. מצא את כל הקודקודים שהם "אוזניים". קודקוד v_i הוא אוזן אם:
   • הוא קודקוד קמור (הזווית הפנימית קטנה מ-180 מעלות).
   • האלכסון v_{i-1}v_{i+1} אינו חותך אף צלע אחרת של המצולע (פרט לצלעות v_{i-1}v_i ו-v_iv_{i+1}).
   • אין אף קודקוד אחר של המצולע בתוך המשולש v_{i-1}v_iv_{i+1}.
3. בחר אוזן אחת, v_i. הוסף את המשולש v_{i-1}v_iv_{i+1} לטריאנגולציה.
4. הסר את הקודקוד v_i מרשימת הקודקודים של המצולע. המצולע הופך למצולע פשוט חדש עם n-1 קודקודים.
5. עדכן את מצב ה"אוזן" של הקודקודים השכנים v_{i-1} ו-v_{i+1} (ייתכן שהם הפכו לאוזניים או הפסיקו להיות כאלה).
6. חזור על שלבים 2-5 עד שנותרים 3 קודקודים בלבד (המשולש האחרון).

מורכבות זמן: במקרה הגרוע, אלגוריתם אוזניים יכול להיות O(N^2), מכיוון שבכל שלב איתור אוזן דורש בדיקה של כל שאר הקודקודים.

מצולעים מונוטוניים וטריאנגולציה יעילה

סוג מסוים של מצולעים פשוטים, המצולעים המונוטוניים, מאפשר טריאנגולציה יעילה יותר.

מצולעים מונוטוניים קלים יותר לטריאנגולציה מכיוון שניתן להשתמש בגישת קו-סריקה (sweep-line) פשוטה. האלגוריתם הנפוץ לטריאנגולציה של מצולע מונוטוני פועל בזמן O(N). הוא בדרך כלל משתמש במבנה נתונים של מחסנית כדי לשמור על קודקודים "פתוחים" ולחבר אותם לאלכסונים.

אסטרטגיות לטריאנגולציה של מצולעים פשוטים כלליים

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

שלבי האסטרטגיה:

1. פירוק למצולעים מונוטוניים: שלב זה כולל מציאת קודקודים מסוימים (לרוב קודקודים מסוג "split" או "merge") וחיבורם באמצעות אלכסונים מתאימים, כך שהמצולע המקורי מתחלק למספר מצולעים מונוטוניים. אלגוריתם קו-סריקה מורכב יותר יכול לבצע שלב זה בזמן O(N log N).
2. טריאנגולציה של מצולעים מונוטוניים: לאחר הפירוק, כל מצולע מונוטוני מטוארגל בנפרד בזמן O(N) (כאשר N הוא מספר הקודקודים של המצולע המונוטוני הספציפי).

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

שאלות לדיון

• הגדר מהו מצולע פשוט ומהי טריאנגולציה. ציין שני מאפיינים כמותיים של כל טריאנגולציה של מצולע פשוט עם n קודקודים.
• תאר בפירוט את אלגוריתם אוזניים (Ear Clipping) לטריאנגולציה. הסבר מדוע הוא מבטיח טריאנגולציה חוקית עבור כל מצולע פשוט.
• השווה בין מצולעים פשוטים כלליים למצולעים מונוטוניים בהקשר של טריאנגולציה. מה היתרון של מצולע מונוטוני?
• כיצד ניתן לבצע טריאנגולציה של מצולע פשוט שאינו מונוטוני? ציין את השלבים העיקריים ואת מורכבות הזמן הכללית.

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

• הגדרות ומאפיינים: הגדרה מדויקת של מצולע פשוט (שפה לא חותכת את עצמה, פנים/חוץ). הגדרה מדויקת של טריאנגולציה (כיסוי, אי-חפיפה, קודקודים). מאפיינים: n-2 משולשים, n-3
  מצאתם טעות או שחסר משהו? ✏️ הציעו תיקון או תוספת