לפני שבוע פרסמתי כאן את הפיתרון של החלק הראשון של יום 10 מ Advent Of Code האחרון בסקאלה, בו ראינו איך למצוא מעגל בגרף באמצעות DFS. החלק השני של התרגיל הציג בעיה מעניינת שנקראת Point In Polygon. בואו נראה איך זה עובד ואיך לפתור אותה עם אלגוריתם Ray Casting.

1. האתגר - חיפוש נקודות בתוך המעגל

בחלק הראשון של התרגיל ראינו איך למצוא מעגל בגרף, לדוגמה גילינו את המעגל הזה:

...........
.S-------7.
.|F-----7|.
.||.....||.
.||.....||.
.|L-7.F-J|.
.|..|.|..|.
.L--J.L--J.
...........

האתגר בחלק השני הוא למצוא את כל הנקודות שנמצאות בתוך המעגל - בדוגמה הזאת אלה 4 הנקודות שמסומנות ב I כאן:

...........
.S-------7.
.|F-----7|.
.||OOOOO||.
.||OOOOO||.
.|L-7OF-J|.
.|II|O|II|.
.L--JOL--J.
.....O.....

2. האלגוריתם Ray Casting

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

האתגר היחיד שיש כאן במימוש הוא להבין מתי הקו יתנגש עם המעגל - למשל אם נחשוב על שורה כזאת:

|F|F-JF---7F7-L7L|7|

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

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

  def insideLoop(point: (Int, Int),
                 loop: Set[(Int, Int)],
                 map: Map[(Int, Int), Char]): Boolean =
    val crossings = point._2
      .to(0, -1)
      .map(c => (point._1, c))
      .filter(p => loop.contains(p))
      .map(map(_))
      .count(Set('|', 'L', 'J').contains(_))
    !loop.contains(point) && crossings % 2 == 1