Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Сплин қисықтарын бағалау әдісі
Method of evaluating spline curves
Сандық талдау математикасының бір саласында де Бур алгоритмі – B сплин түріндегі сплин қисықтарын бағалау үшін полиномиалдық уақыт пен сандық тұрақтылықты қамтамасыз ететін алгоритм. Бұл де Кастельжоның Безиер қисықтарына арналған алгоритмінің жалпыланған түрі. Алгоритмді неміс-американдық математигі Карл Р. де Бур жасаған. Де Бур алгоритмінің жеңілдетілген, ықтимал жылдам нұсқалары құрастырылған, бірақ олар салыстырмалы түрде төмен тұрақтылыққа ұшырайды.
In the mathematical subfield of numerical analysis, de Boor's algorithm is a polynomial time and numerically stable algorithm for evaluating spline curves in B spline form. It is a generalization of de Casteljau's algorithm for Bézier curves. The algorithm was devised by German American mathematician Carl R. de Boor. Simplified, potentially faster variants of the de Boor algorithm have been created but they suffer from comparatively lower stability.
Кіріспе
B сплинелер туралы жалпы түсінік негізгі мақалада берілген. Мұнда біз де Бур алгоритмін талқылаймыз, ол spline қисығын белгілі бір позицияда бағалаудың тиімді және сандық тұрақты схемасы. Бұл қисық B сплине функцияларының қосындысынан, векторлық шамалармен көбейтілген басқару нүктелерінен құралады.
A general introduction to B splines is given in the main article. Here we discuss de Boor's algorithm, an efficient and numerically stable scheme to evaluate a spline curve at position The curve is built from a sum of B spline functions multiplied with potentially vector valued constants , called control points,
Кез келген реттің B сплинелері – бұл түйіндердің торында анықталған, дәрежесі бірдей полиномдық функциялардың бөлік-бөлікке қосылуы. (Келесіде біз әрқашан нөлдік негізгі индекстерді қолданамыз). Де Бур алгоритмі spline қисығын бағалау үшін O(p²) + O(p) операцияларын қолданады. Ескерту: B сплиндері туралы негізгі мақала және классикалық жарияланымдарда басқа белгілеу қолданылады: B сплині индексімен белгіленеді, мұнда .
B splines of order are connected piece wise polynomial functions of degree defined over a grid of knots (we always use zero based indices in the following). De Boor's algorithm uses O(p2) + O(p) operations to evaluate the spline curve. Note: the main article about B splines and the classic publications use a different notation: the B spline is indexed as with .
Жергілікті қолдау
B сплиндары шекті қолдауға ие, яғни көпмүшелер тек шекті доменде ғана оң, ал қалған жерде нөлге тең. Кокс де Бур рекурсиялық формуласы осыны көрсетеді:
B splines have local support, meaning that the polynomials are positive only in a finite domain and zero elsewhere. The Cox de Boor recursion formula shows this:
индекс позицияны қамтитын түйін аралығын анықтасын. Рекурсиялық формуладан тек белгілі бір түйін аралығы үшін B сплиндері нөлден өзгеше екенін көреміз. Осылайша, қосынды келесіге дейін қысқартылады:
Let the index define the knot interval that contains the position, We can see in the recursion formula that only B splines with are non zero for this knot interval. Thus, the sum is reduced to:
Осыдан келіп, рекурсияда ең жоғары сұралған түйін орны индексте екенін көреміз. Бұл, нақты қолданылатын кез келген түйін аралығының алдында және артында кем дегенде қосымша түйіндер болуы керек екенін білдіреді. Компьютерлік бағдарламада бұл әдетте бірінші және соңғы қолданылған түйін орнын белгілі бір рет қайталау арқылы жүзеге асырылады. Мысалы, егер және нақты түйін орны болса, түйін векторына қосымша түйіндер қосылады.
It follows from that Similarly, we see in the recursion that the highest queried knot location is at index This means that any knot interval which is actually used must have at least additional knots before and after. In a computer program, this is typically achieved by repeating the first and last used knot location times. For example, for and real knot locations , one would pad the knot vector to .
Алгоритм
Осы анықтамалармен біз де Бур алгоритмін сипаттай аламыз. Алгоритм B-сплайн функцияларын тікелей есептемейді. Оның орнына, ол эквивалентті рекурсиялық формула арқылы оларды анықтайды. үшін келесі рекурсия қолданылады:
With these definitions, we can now describe de Boor's algorithm. The algorithm does not compute the B spline functions directly. Instead it evaluates through an equivalent recursion formula. Let be new control points with for For the following recursion is applied:
Итерациялар аяқталғаннан кейін , яғни – ізделінді нәтиже. Де Бур алгоритмі Кокс-де Бур рекурсиялық формуласымен B-сплайнды тікелей есептеуге қарағанда тиімдірек, себебі ол нөлге көбейтілетіні анық терминдерді есептемейді.
Once the iterations are complete, we have , meaning that is the desired result. De Boor's algorithm is more efficient than an explicit calculation of B splines with the Cox de Boor recursion formula, because it does not compute terms which are guaranteed to be multiplied by zero.
Оңтайландырулар
Жоғарыдағы алгоритм компьютерде іске асыру үшін оңтайландырылмаған. Ол уақытша басқару нүктелері үшін жадты қажет етеді. Әрбір уақытша басқару нүктесі бір рет жазылады және екі рет оқылады. Итерацияны кері бағытта орындау арқылы (көтерілудің орнына төмен санау арқылы) алгоритмді тек уақытша басқару нүктелеріне арналған жадпен іске асыруға болады, бұл жадты қайта пайдалануға мүмкіндік береді. Сондай-ақ, әр қадамда тек бір ғана мән қолданылады, сондықтан жадты қайта пайдалануға болады. Бұдан әрі, уақытша басқару нүктелері үшін нөлдік индекс пайдалану ыңғайлы. Алдыңғы индекспен байланыс: Осылайша, біз жақсартылған алгоритмді аламыз: үшін болсын. : итерациялаңыз.
The algorithm above is not optimized for the implementation in a computer. It requires memory for temporary control points Each temporary control point is written exactly once and read twice. By reversing the iteration over (counting down instead of up), we can run the algorithm with memory for only temporary control points, by letting reuse the memory for Similarly, there is only one value of used in each step, so we can reuse the memory as well. Furthermore, it is more convenient to use a zero based index for the temporary control points. The relation to the previous index is Thus we obtain the improved algorithm:
Let for Iterate for :
Note that j must be counted down. After the iterations are complete, the result is .
J-ді төмен санау керек екенін ескеріңіз. Итерациялар аяқталғаннан кейін нәтиже болады.
The algorithm above is not optimized for the implementation in a computer. It requires memory for temporary control points Each temporary control point is written exactly once and read twice. By reversing the iteration over (counting down instead of up), we can run the algorithm with memory for only temporary control points, by letting reuse the memory for Similarly, there is only one value of used in each step, so we can reuse the memory as well. Furthermore, it is more convenient to use a zero based index for the temporary control points. The relation to the previous index is Thus we obtain the improved algorithm:
Let for Iterate for :
Note that j must be counted down. After the iterations are complete, the result is .