ברוכים הבאים ליחידת הלימוד בנושא "חיתוכי קטעי ישרים" בקורס גיאומטריה חישובית. יחידה זו עוסקת באחד הבעיות היסודיות והחשובות ביותר בתחום: מציאת כל נקודות החיתוך בין אוסף נתון של קטעי ישרים במישור. לבעיה זו יישומים רבים, החל מגרפיקה ממוחשבת ומערכות מידע גיאוגרפיות (GIS) ועד לתכנון מסלולים ורובוטיקה. נתמקד באלגוריתמים יעילים, ובראשם אלגוריתם קו-סריקה של בנטלי-אוטמן, תוך הבנה מעמיקה של מבני הנתונים הנדרשים, ניתוח מורכבות חישובית וטיפול במקרים מנוונים.
אלגוריתם קו-סריקה (Bentley-Ottmann)
הגישה הנאיבית לפתרון בעיית מציאת כל החיתוכים בין N קטעי ישרים היא לבדוק כל זוג קטעים אפשרי, מה שמוביל למורכבות זמן של O(N^2). אלגוריתם קו-סריקה של בנטלי-אוטמן מציע פתרון יעיל בהרבה, המבוסס על פרדיגמת קו-הסריקה.
הרעיון המרכזי
האלגוריתם מדמה קו אנכי (קו-סריקה) הנע משמאל לימין על פני המישור. לאורך תנועתו, קו-הסריקה "פוגש" נקודות אירוע שונות. בכל נקודת אירוע, האלגוריתם מעדכן את מצבו ומבצע בדיקות מקומיות לגילוי חיתוכים. הרעיון הוא שחיתוך בין שני קטעים יכול להתרחש רק כאשר הם הופכים לשכנים ברשימת הקטעים החותכים את קו-הסריקה.
מבני נתונים וזרימת האלגוריתם
אלגוריתם בנטלי-אוטמן מסתמך על שני מבני נתונים עיקריים:
תור אירועים (Event Queue - Q)
מבנה נתונים המכיל את כל נקודות האירוע העתידיות, ממוינות לפי קואורדינטת ה-X שלהן (ובמקרה של שוויון, לפי Y). זהו לרוב תור עדיפויות (min-priority queue). תור האירועים מאותחל עם כל קצוות הקטעים, ונקודות חיתוך חדשות שמתגלות מתווספות אליו.
מצב קו-הסריקה (Sweep-Line Status - T)
מבנה נתונים המכיל את כל הקטעים שחותכים את קו-הסריקה במיקומו הנוכחי, ממוינים לפי קואורדינטת ה-Y שלהם בנקודת החיתוך עם קו-הסריקה. זהו לרוב עץ חיפוש בינארי מאוזן (כמו AVL או Red-Black tree) המאפשר הכנסה, מחיקה וחיפוש שכנים בזמן לוגריתמי.
טיפול בנקודות אירוע
- קצה שמאלי של קטע: הקטע מתווסף ל-T. נבדקים חיתוכים בינו לבין שכניו החדשים ב-T (מעליו ומתחתיו). אם נמצא חיתוך, הוא מתווסף ל-Q.
- קצה ימני של קטע: הקטע מוסר מ-T. נבדקים חיתוכים בין שכניו החדשים ב-T (הקטע שהיה מעליו והקטע שהיה מתחתיו). אם נמצא חיתוך, הוא מתווסף ל-Q.
- נקודת חיתוך: שני הקטעים החותכים מחליפים את סדרם ב-T. נבדקים חיתוכים חדשים בין הקטעים שהחליפו מקום לבין שכניהם החדשים ב-T.
מורכבות חישובית
מורכבות הזמן של אלגוריתם בנטלי-אוטמן היא O((N+K) log N), כאשר N הוא מספר הקטעים ו-K הוא מספר נקודות החיתוך. מורכבות המקום היא O(N+K). הגורם log N נובע מהפעולות על מבני הנתונים Q ו-T (הכנסה, מחיקה, חיפוש שכנים). האלגוריתם נחשב ל"רגיש לפלט" (output-sensitive) מכיוון שזמן הריצה שלו תלוי לא רק בגודל הקלט (N) אלא גם בגודל הפלט (K).
טיפול במקרים מנוונים
מקרים מנוונים נפוצים בבעיית חיתוכי קטעים כוללים:
- קטעים אנכיים: קו-הסריקה עצמו הוא אנכי. יש צורך בכלל עקבי לשבירת שוויון (למשל, קטע אנכי נחשב "מעל" קטע אחר אם קצהו העליון גבוה יותר).
- שלושה קטעים או יותר הנפגשים בנקודה אחת: יש לוודא שכל זוג חיתוכים נבדק רק פעם אחת, ושכל הקטעים המעורבים מטופלים נכון.
- קטעים מקבילים: לא ייפגשו אלא אם הם חופפים.
- קטעים חופפים (overlapping segments): דורש טיפול מיוחד כדי לא לדווח על אינסוף נקודות חיתוך או על חיתוכים כפולים. ניתן לטפל בהם על ידי הגדרת "נקודת חיתוך" כנקודה שבה הקטעים מתחילים או מסיימים לחפוף.
הטיפול במקרים מנוונים דורש הגדרות מדויקות של יחסים (כמו "מעל" ו"מתחת") ושבירת שוויון עקבית, כמו גם שימוש בפרדיקטים גיאומטריים חזקים (robust geometric predicates) המונעים שגיאות חישוב נקודות צפות.
שאלות לדיון
- הסבירו מדוע אלגוריתם קו-סריקה יעיל יותר מגישה נאיבית של בדיקת כל זוג קטעים. מהם היתרונות והחסרונות של כל גישה?
- כיצד הייתם משנים את אלגוריתם בנטלי-אוטמן כדי למצוא רק את נקודת החיתוך השמאלית ביותר (בעלת קואורדינטת X מינימלית) מבין כל החיתוכים?
- תארו מצב שבו טיפול לא נכון במקרים מנוונים עלול לגרום לאלגוריתם בנטלי-אוטמן לדווח על תוצאות שגויות או להיכנס ללולאה אינסופית. הציעו פתרון לאחד מהמקרים הללו.
- מהי המשמעות של "אלגוריתם רגיש לפלט" בהקשר של מורכבות זמן? תארו מקרה שבו אלגוריתם בנטלי-אוטמן יהיה מהיר מאוד, ומקרה שבו הוא יהיה איטי יחסית.
נקודות לתשובת מודל
- הבנת פרדיגמת קו-הסריקה: תיאור תנועת הקו, נקודות אירוע, ומדוע חיתוכים מתגלים רק בין שכנים.
- הכרת מבני הנתונים: תור אירועים (Q) ומצב קו-הסריקה (T), כולל תפקידם וסוגי מבני הנתונים המתאימים (תור עדיפויות, עץ חיפוש בינארי מאוזן).
- פירוט טיפול באירועים: הסבר כיצד מטפלים בקצה שמאלי, קצה ימני ונקודת חיתוך, כולל בדיקות השכנים והוספת חיתוכים חדשים ל-Q.
- ניתוח מורכבות: הבנת הגורמים ל-O((N+K) log N) בזמן ול-O(N+K) במקום, והמשמעות של "רגישות לפלט".
- מודעות למקרים מנוונים: זיהוי מקרים כמו קטעים אנכיים, חופפים, או מפגש של מספר קטעים בנקודה אחת, והצורך בפרדיקטים גיאומטריים חזקים וכללי שבירת שוויון עקביים.