בעיית הנקודה במצולע

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

דוגמה של מצולע פשוט.

על אף שהבעיה נראית טריוויאלית במבט ראשון, היא נעשית סבוכה (מבחינת כוח חישוב) כאשר מתייחסים למצולעים שחותכים את עצמם ובעלי מספר עצום של צלעות. החל מ-1974 קיימות שתי גישות אלגוריתמיות נפוצות בשימוש: מעקב קרן (Ray casting) וסיכום זוויות. הגישה הראשונה במהותה מתבססת על משפט עקומת ז'ורדן, ואילו השנייה מתבססת על המושג של אינדקס ליפוף.

אלגוריתם מעקב קרן (Ray casting algorithm)

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

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

אלגוריתם זה ידוע לעיתים קרובות בשם אלגוריתם מספר החציות (crossing number algorithm) או אלגוריתם כלל הזוגיות (even–odd rule algorithm) והוא ממומש בעולם המחשוב כבר מ-1962. הוא מבוסס על האבחנה הפשוטה שאם נקודה נעה מהאינסוף עד לנקודה הנתונה אז היא חוצה את השפה של המצולע, לעיתים מספר רב של פעמים, כאשר בכל חציה היא עוברת מחלקו הפנימי של המצולע לחלקו החיצוני, לסירוגין. כתוצאה, אחר שתי חציות עוקבות, היא תימצא באותו תחום של המישור. אבחנה זו מבוססת מתמטית על משפט עקומת ז'ורדן, שבפשטות קובע שכל עקומה מישורית סגורה שאינה חותכת את עצמה מחלקת את המישור ל"תחום פנימי" ו"תחום חיצוני".

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

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

אלגוריתם אינדקס הליפוף

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

קישורים חיצוניים

מדיה וקבצים בנושא בעיית הנקודה במצולע בוויקישיתוף