Введение Одиночного Узла

Дана последовательность n +1 контр. точек p ₀, p ₁,..., p _n, узловой вектор из m +1 узлов U = { u ₀, u ₁,..., u_m } и степень p, нам нужно ввести новый узел t в узловой вектор без изменения формы кривой B-spline.

Пусть новый узел t лежит на узловом интервале [ u_k, u_{k +1}). Из свойства сильного огранич. многоугольника p (t) лежит в огранич. многоугольнике контр. точек p _k, p _{k -1},..., p _k-p, а все остальные базисные функции равны нулю. Отсюда, расчет введения узла можно ограничить контр. точками p _k, p _{k -1},..., p _k-p. Способ введения t - это нахождение p новых контр. точек q _k на сегменте p _{k -1} p _k, q _{k -1} на сегменте p _{k -2} p _{k -1},..., и q _{k-p +1} на сегменте p _k-p p _{k-p +1}, чтобы старая ломаная от p _k-p до p _k (показана черным) заменилась на p _k-p q _{k-p +1}... q _k p _k (показана оранжевым) путем отсечения углов в вершинах p _{k-p +1},..., p _{k -1}. Все остальные контр. точки остаются без изменений. Заметьте, что p -1 контр. точек исходной ломаной удаляются и змаеняются на p новых контр. точек.

К счастью, положения новых контр. точек q _i легко рассчитать. Формула для вычисления новой контр. точки q _i на сегменте p _{i -1} p _i следующая:

,

где отношение a_i определяется так:

В итоге, чтобы ввести новый узел t, мы сначала находим узловой интервал [ u_k, u_{k +1}), на котором лежит этот новый узел. С найденным k можно найти p новых контр. точек q _{k-p +1},..., q _k по вышеуказанной формуле. В конце концов, исходная ломаная от p _k-p до p _k заменяется на новую, построенную по точкам p _k-p, q _{k-p +1}, q _{k-p +2},..., q _{k -1}, q _k и p _k. Заметьте, что после введения нового узла узловой вектор становится равен u ₀, u ₁,..., u_k, t, u_{k +1},..., и u_m. Если новый узел t равен u_k, то множественность u_k увеличивается на единицу.

Вышеуказанную схему вычислений можно проиллюстрировать с помощью следующей диаграммы. Сначала переписываем все зависимые точки в столбец слева. Затем рассчитанные новые контр. точки пишем во второй столбец. Заметьте, их количество меньше на единицу. Для вычисления новой контр. точки q _i, где k-p +1 <= i <= k, нужно две исходных точки p _{i -1} и p _i с коэффициентами 1- a_i и a_i, соответственно. После вычисления мы будем использовать точки, окруженные синей точечной линией, чтобы заменить те, которые вне области. Все не зависмиые от этого точки сохраняются. Таким образом, исходная последовательность точек p _k-p, p _{k-p +1},..., p _{k -1}, p _k заменяется на p _k-p, q _{k-p +1},..., q _{k -1}, p _k.

Посмотрим на геометрическую интерпретацию a_i. Из определения a_i - это отношение, в котором разделен интервал [ u_i, u _i+p) значением t, как показано ниже:

Есть k значений a_i, каждое из которых покрывает p узловых интервалов (т.e. [ u_i, u _i+p)). Если соединить эти интервалы вместе и выровнять [align at] в значении t, получим следующую диаграмму:

Таким образом, положение t делит узловые интервалы [ u_k, u_k+p), [ u_{k -1}, u_{k+p -1}),..., [ u_{k-p +1}, u_{k +1}) в отношениях a_k, a_{k -1},..., a_{k-p +1}, которые, в свою очередь, дают те же отношения в делении сегментов p _k p _{k -1}, p _{k -1} p _{k -2},... p _k-p p _{k-p +1}.

Дата добавления: 2015-10-29