שיטות חלוקה

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

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

ראו גם

עריכה