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

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

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

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

הגדרה

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

,

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

.

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

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

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

הערות

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

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

ל:

ו

דוגמה

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

בנקודה t0

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

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

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

עקומת בזייר

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

עם

.

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

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

פרשנות גאומטרית

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

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

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

DeCasteljau1.svg

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

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

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

ראו גם

קישורים חיצוניים

ויקישיתוף מדיה וקבצים בנושא אלגוריתם דה-קסטלז'ו בוויקישיתוף
Logo hamichlol 3.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0