ברוכים הבאים לשיעור המבוא ליסודות גיאומטריים בגיאומטריה חישובית. יחידה זו מהווה את אבן הפינה להבנת אלגוריתמים גיאומטריים מורכבים יותר. נתמקד בהגדרת אובייקטים גיאומטריים בסיסיים, בייצוגם הממוחשב, ובכלים חישוביים חיוניים שישמשו אותנו לאורך כל הקורס. הבנה יסודית של מושגים אלו היא קריטית להצלחה במבחן וביכולת לפתור בעיות גיאומטריות חישוביות.
מושגי יסוד גיאומטריים וייצוגם
גיאומטריה חישובית עוסקת בבעיות גיאומטריות מנקודת מבט אלגוריתמית. לשם כך, עלינו להגדיר ולייצג אובייקטים גיאומטריים בצורה שניתן יהיה לעבד אותה באמצעות מחשב.
ייצוג אובייקטים גיאומטריים במחשב
- נקודה: מבנה נתונים פשוט המכיל שני שדות מסוג float/double עבור x ו-y.
- קטע: מבנה המכיל שתי נקודות (P1, P2) המגדירות את קצותיו.
- מצולע: רשימה או מערך של נקודות (קודקודים) בסדר מסוים (לרוב נגד כיוון השעון עבור מצולע פשוט).
חישובים גיאומטריים בסיסיים
יכולת לבצע חישובים בסיסיים על אובייקטים גיאומטריים היא חיונית לאלגוריתמים מתקדמים יותר.
חישוב מרחק
המרחק האוקלידי בין שתי נקודות P1=(x1, y1) ו-P2=(x2, y2) מחושב באמצעות נוסחת המרחק:
מרחק(P1, P2) = sqrt((x2 - x1)^2 + (y2 - y1)^2)
חישוב שטח
שטח מצולע הוא גודל קריטי. עבור משולש, ניתן לחשב שטח באמצעות מכפלה וקטורית.
עבור משולש עם קודקודים P1, P2, P3, השטח הוא 0.5 * |(P2-P1) x (P3-P1)|, כאשר 'x' מסמן מכפלה וקטורית דו-ממדית. עבור מצולע כללי, ניתן להשתמש בנוסחת השרוך (Shoelace Formula).
מבחני אוריינטציה ופניות
מבחן אוריינטציה קובע את הכיוון היחסי של נקודה P3 ביחס לישר המכוון מ-P1 ל-P2. הוא מבוסס על סימן המכפלה הוקטורית של וקטורים (P2-P1) ו-(P3-P1).
אם P1=(x1, y1), P2=(x2, y2), P3=(x3, y3), אז הביטוי לחישוב הוא:
(x2 - x1)(y3 - y1) - (y2 - y1)(x3 - x1)
פנייה שמאלה (Left Turn)
אם התוצאה חיובית (> 0), הנקודה P3 נמצאת משמאל לישר המכוון מ-P1 ל-P2. שלושת הנקודות יוצרות פנייה שמאלה.
פנייה ימינה (Right Turn)
אם התוצאה שלילית (< 0), הנקודה P3 נמצאת מימין לישר המכוון מ-P1 ל-P2. שלושת הנקודות יוצרות פנייה ימינה.
קולינאריות (Collinear)
אם התוצאה אפס (= 0), הנקודות P1, P2, P3 הן קולינאריות (נמצאות על אותו ישר).
מבחנים אלו קריטיים לאלגוריתמים כמו בניית קמור (Convex Hull), בדיקת חיתוך קטעים, וטריאנגולציה של מצולעים.
שאלות לדיון
- כיצד הייתם מייצגים מצולע עם חור (polygon with a hole) במבנה נתונים, וכיצד הדבר משפיע על חישוב שטחו?
- בהינתן שלוש נקודות P1=(1,1), P2=(3,3), P3=(2,4), קבעו באמצעות מבחן אוריינטציה האם הן יוצרות פנייה שמאלה, ימינה או שהן קולינאריות. הציגו את החישוב המלא.
- מדוע דיוק נקודה צפה (floating-point precision) מהווה אתגר משמעותי במבחני אוריינטציה, וכיצד ניתן להתמודד עם בעיה זו?
- תארו מצב שבו מבחן אוריינטציה הוא כלי הכרחי לפתרון בעיה גיאומטרית חישובית.
נקודות לתשובת מודל
- ייצוג מצולע עם חור: מצולע חיצוני (outer boundary) המיוצג כרשימת קודקודים נגד כיוון השעון, ורשימה של מצולעים פנימיים (holes) שכל אחד מהם מיוצג כרשימת קודקודים עם כיוון שעון. חישוב השטח יהיה שטח המצולע החיצוני פחות סכום שטחי המצולעים הפנימיים.
- מבחן אוריינטציה ל-P1=(1,1), P2=(3,3), P3=(2,4):
- וקטור P2-P1: (3-1, 3-1) = (2, 2)
- וקטור P3-P1: (2-1, 4-1) = (1, 3)
- חישוב המכפלה הוקטורית: (2 * 3) - (2 * 1) = 6 - 2 = 4.
- התוצאה חיובית (> 0), ולכן הנקודות יוצרות פנייה שמאלה.
- דיוק נקודה צפה: חישובים עם מספרים ממשיים (float/double) עלולים להוביל לשגיאות עיגול קטנות. במבחני אוריינטציה, שגיאה קטנה עלולה לשנות את סימן התוצאה (למשל, מ-0.0000001 ל--0.0000001), ובכך לשנות את ההחלטה (למשל, מקולינארי לפנייה). פתרונות כוללים שימוש באריתמטיקה מדויקת (exact arithmetic) או הגדרת סף קטן (epsilon) לבדיקת שוויון לאפס, כלומר, אם התוצאה קרובה מאוד לאפס (בטווח אפסילון), נתייחס אליה כאל אפס.
- חשיבות מבחן אוריינטציה: לדוגמה, באלגוריתם בניית קמור (Convex Hull) בשיטת ג'רוויס (Jarvis March / Gift Wrapping), מבחן אוריינטציה משמש לבחירת הקודקוד הבא שיוצר את הפנייה השמאלית ביותר מהקודקוד הנוכחי, ובכך מבטיח שהקמור נבנה נגד כיוון השעון. דוגמה נוספת היא בדיקת חיתוך קטעים, שם מבחני אוריינטציה קובעים האם קצוות קטע אחד נמצאים משני צידי הקטע השני.