שיטות חלוקה

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

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

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

דוגמה פשוטה
תהליך "חיתוך הפינות" של צ'יקין (1969) הוא תהליך היוצר מידול של פולינום B-ספליין ממעלה 2.

תיאור התהליך: בהינתן נקודות בקרה {f0} המפוזרות על השלמים נבצע את חוקי העידון הבאים:

(fk+1(2j)=3/4*fk(j)+1/4*fk(j+1

(fk+1(2j+1)=1/4*fk(j)+3/4*fk(j+1

k מייצג את רמת העידון הנדרשת ו־j את מיקום הנקודה בסדרת הנקודות.
על הישר הנקודה ה-j-ית נמצאת במקום ה-j*2-k .

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

ראו גם
תכנון בעזרת מחשב
אינטרפולציה
אלגוריתם קירוב

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