רוב המערכים הדו מימדיים הנלמדים והמחושבים כיום הם במישור.
למרות זאת, לעיתים אנו צריכים מערכים דו מימדיים על משטחים עקומים.
לדוגמא, מפות גאוסיניות של פוליטופים שיכולות
לשמש לחישוב סכום מינקובסקי של פוליטופים.
לפניכם קטע קצר מסרט קודם שמראה
איך סכומי מינקובסקי כאלה יכולים להיות מחושבים בעזרת
שישה מערכים מקובעים על שש פאות של קוביה.
למרות שטכניקה זו הוכחה כיעילה,
היא הפיקה קודקודים נוספים בקצוות הפאות,
והיא הצריכה זיהוי והתאמה של קודקודים
של פאות השכנות.
ששת המערכים המישוריים נוצרים על ידי קטעים ישרים,
שיכולים להיות מטופלים בעזרת חשבון רציונלי.
כמובן שלטכניקה יריבה שמשתמשת
במערך מקובע על כדור בלי
קודקודי הקצה הנוספים, אבל עדיין
משתמשת בחשבון רציונלי יש סיכוי טוב לעבור
את המתחרה שלה.
עוד דוגמא שמדגימה את השימושיות
של מערכים על משטחים עקומים היא הצורך
לבנות ולתחזק מערכים שנוצרים מחיתוכים
של משטח אחד עם אוסף של משטחים אחרים.
פיתחנו מסגרת כללית לחישוב מערכים
על משטחים פרמטריים דו מימדיים, שמטפלת
במגוון טופולוגיות כולל: גליל, טורוס, וכדור.
היא מבוססת על החבילה הקיימת שמחשבת
ומתחזקת מערכים מישוריים.
המרחב הוא מלבן פרמטרי דו מימדי עם
שפה תחתונה, עליונה, שמאלית וימנית.
עקום זיהוי הוא עקום רציף שהוא מיפוי של
שפות סגורות נגדיות של המרחב.
נקודת כיווץ היא נקודה סינגולרית שהיא המיפוי של
שפה שלמה של המרחב.
שימוש חוזר בקוד נעשה על ידי אימוץ של האלגוריתמים
והמימוש שלהם. לדוגמא, איתור נקודה יעיל.
קוד מוכלל מטפל באובייקטים על משטח פרמטרי מותאם
שמוגדר מעל מרחב פרמטרי מותאם כאשר
השפה, עקומי הזיהוי, נקודות הכיווץ
וקודקודים באינסוף נזרקים.
קוד מיוחד שמטפל באובייקטים שמגיעים
לשפת המרחב הוסף בכדי ליצור מימוש שלם.
בזמן הטאטוא של המרחב, שמתבצע כדי ליצור
מבנה נתונים שמתאר את המערך של העקומים,
אנו חייבים להתחשב בטופולוגיה של המשטח.
למרות שזרקנו את השפה של המרחב הפרמטרי, אנו
צריכים להתחשב בעובדה שמספר קשתות עוברות דרך
הקוטב הצפוני, שהוא נקודת כיווץ.
כשקו הטאטוא מגיע לסוף המרחב הפרמטרי,
אנו מדביקים את אובייקטי המערך עם המתאימים להם
שנוצרו ממש בתחילת תהליך הטאטוא.
רוב המנגנונים המפותחים ב CGAL
עבור מערכים מישוריים יכולים לשמש גם עבור
מערכים על משטחים, בתנאי שהמשתמש יספק
את החיבור לטופולוגיה של המשטח והגיאומטריה
של העקומים על המשטח. כעת ניתן לראות
איך שני מערכים מכוסים (אחד על השני) על כדור.
החלוקה של הכדור האמצעי היא תוצאה של
כיסוי של שאר המערכים הכדוריים מסביבו.
אנו יכולים לחשב מעטפות תחתונות
של משטחים מעל הכדור, שמשמשים אותנו לחישוב
דיאגרמות וורונוי מעל הכדור. כעת ניתן לראות
דוגמא, בה אתרי הנקודות מצויירים באדום והדיאגרמה
עצמה מצוירת בכחול. המחלק של שני אתרי נקודות
הוא קשת גיאודזית.
כעת ניתן לראות דיאגרמת פאוור על הכדור.
במקרה זה, האתרים הם מעגלים שמצוירים באדום.
דיאגרמות התוצאה מיוצגות כמערכים שיכולים
להיות מועברים כקלט לפעולות עוקבות הנתמכות
על ידי החבילה. כעת אפשר לראות כיסוי של מערך שנוצר
על ידי יבשות כדור הארץ ודיאגרמת הוורונוי של 9 הערים
שאירחו את הסימפוזיון בגיאומטריה חישובית באלף הזה.
עוד מידע ניתן למצוא במאמר:
Sweeping and Maintaining Two-Dimensional Arrangement on Surfaces: A
First Step, which was presented at ESA 2007 או באתרים הבאים.