שיטות חלוקה
שיטות חלוקה במתמטיקה הוא שם כולל לשיטות מידול גאומטרי הנפוצות מאוד בתכנון גאומטרי מבוסס מחשב (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 .
את חוקי העידון קל לממש במחשב וביצועם כולל זמן ריצה ליניארי לגודל הקלט-קרי מספר הנקודות בקרה.