חישוב נקודה צפהגיאומטריה מדויקת (Exact Geometric Computation)טיפול במקרים מנווניםהשפעת שגיאות עיגול
יחידה זו עוסקת באחד האתגרים המרכזיים בגיאומטריה חישובית: השגת רובוסטיות ודיוק חישובי. יישום אלגוריתמים גיאומטריים על מחשבים המשתמשים בייצוג נקודה צפה מוגבל, מוביל לעיתים קרובות לשגיאות. נלמד כיצד שגיאות עיגול משפיעות על חישובים, נכיר גישות להתמודדות עם בעיות דיוק, ובפרט נתמקד בגיאומטריה מדויקת ובטיפול במקרים מנוונים.
מבוא לבעיית הדיוק בגיאומטריה חישובית
אלגוריתמים גיאומטריים רבים מסתמכים על בדיקות יחסים מרחביים מדויקים. כאשר חישובים אלו מבוצעים באמצעות חשבון נקודה צפה, שגיאות עיגול זעירות עלולות לשנות את סימן התוצאה, ובכך להוביל להחלטות שגויות המשבשות את מהלך האלגוריתם. חוסר רובוסטיות זה הוא בעיה קריטית ביישומים מעשיים.
שגיאות עיגול: שגיאות הנובעות מייצוג מספרים ממשיים בדיוק סופי במחשב, כאשר חלק מהספרות מעוגלות.
חישוב נקודה צפה והשלכותיו
עקרונות חישוב נקודה צפה
רוב המחשבים המודרניים משתמשים בייצוג נקודה צפה (Floating-Point) על פי תקן IEEE 754. ייצוג זה מאפשר טווח רחב של מספרים אך מגיע עם דיוק סופי. פעולות אריתמטיות עלולות להכניס שגיאות עיגול. חשבון נקודה צפה אינו אסוציאטיבי או דיסטריבוטיבי באופן מלא, מה שמוביל לתוצאות שונות עבור ביטויים זהים לכאורה.
חישוב נקודה צפה: שיטה לייצוג מספרים ממשיים במחשב באמצעות מנטיסה ואקספוננט, המאפשרת טווח רחב על חשבון דיוק סופי.
השוואות נקודה צפה: השוואה ישירה של שני מספרי נקודה צפה (a == b) מסוכנת ומובילה לתוצאות בלתי צפויות עקב שגיאות עיגול. יש להשוות האם ההפרש המוחלט ביניהם קטן מסף שגיאה קטן (|a - b| ). זה קריטי למניעת באגים עדינים באלגוריתמים גיאומטריים.
גיאומטריה מדויקת (EGC) כפתרון
הצורך בפרדיקטים מדויקים
הליבה של אלגוריתמים גיאומטריים רבים היא קביעת סימנם של ביטויים אלגבריים המכונים "פרדיקטים גיאומטריים". גיאומטריה מדויקת שואפת להבטיח שסימנים אלו יחושבו תמיד באופן מדויק.
גיאומטריה מדויקת (Exact Geometric Computation - EGC): פרדיגמה המבטיחה שכל ההחלטות הטופולוגיות יחושבו באופן מדויק, גם אם קואורדינטות הקלט הן מספרי נקודה צפה.
פרדיקטים גיאומטריים: פונקציות בוליאניות המקבלות קואורדינטות גיאומטריות ומחזירות מידע טופולוגי (למשל, "האם נקודה C משמאל לקו AB?").
גישות ל-EGC
חשבון דיוק שרירותי
שימוש בספריות המאפשרות ייצוג וחישוב על מספרים בדיוק אינסופי. מבטיח דיוק מלא אך עלול להיות איטי מאוד.