אלגוריתם דה-קסטלז'ו

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

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

למרות שהוא איטי יותר במרבית הארכיטקטורות בהשוואה לגישה הישירה, הוא יציב יותר מבחינה נומרית.

הגדרה[עריכת קוד מקור | עריכה]

עקומת בזייר B (בדרגה n, עם נקודות הבקרה ) יכולה להיות כתובים בעזרת פולינומי ברנשטיין כדלקמן

,

כאשר b הוא פולינום בסיס מתצורת ברנשטיין

.

העקומה בנקודה t0 ניתנת להערכה בעזרת נוסחת נסיגה

אז, בנקודה יכול להיות מוערך ב השלבים של האלגוריתם. התוצאה נתונה על ידי:

יתר על כן, עקומת בזייר יכולה להתפצל בנקודה לשתי עקומות עם נקודות בקרה, בהתאמה:

הערות[עריכת קוד מקור | עריכה]

כאשר עושים את החישוב באופן ידני, שימושי לכתוב את המקדמים במשולש כ:

בעת בחירת נקודה t0 כדי להעריך את פולינום ברנשטיין אנחנו יכולים להשתמש בשני האלכסונים של המשולש כדי לבנות חלוקה של פולינום

ל:

ו

דוגמה[עריכת קוד מקור | עריכה]

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

בנקודה t0

אנחנו מתחילים את הרקורסיה עם

עם איטרציה שנייה הרקורסיה מפסיקה עם

אשר הוא הפולינום ברנשטיין הצפוי מדרגה 2.

עקומת בזייר[עריכת קוד מקור | עריכה]

בעת הערכת עקומת בזייר מדרגה n במרחב 3-ממדי עם n+1 נקודות בקרה, Pi

עם

.

אנחנו מחלקים את עקומת בזייר לשלוש משוואות נפרדות.

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

פרשנות גאומטרית[עריכת קוד מקור | עריכה]

האינטרפולציה הגאומטרית של דה-קסטלז'ו הוא ברור וישיר.

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

התמונה הבאה מראה את התהליך הזה עבור עקומת בזייר מעוקבת:

DeCasteljau1.svg

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

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

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

ויקישיתוף מדיה וקבצים בנושא אלגוריתם דה-קסטלז'ו בוויקישיתוף