Параметрические сплайны на плоскости
Рассмотрим задачу: на плоскости дан набор точек и по ним надо, при помощи параметрических сплайнов, построить кривую (замкнутую или незамкнутую).
Обычно в таких случаях применяют кубические сплайны, я же рекомендую квадратичные, как более простые.
Итак, нам надо построить многочлен P (t) = A ·t2 + B · t + C. Здесь и далее будем обозначать вектора большими буквами, а скаляры — малыми. Параметр t меняется от 0 до 1.
Для построения отдельного сплайна нам понадобятся крайние точки P0 и P1 и направления нормалей к кривой в этих точках: N0 и N1. Длина N0 и N1, как увидим позже, может быть произвольной. Главное — ненулевой.
Из условий непрерывности находим:
С = P0
A + B = P1 — P0
А из условий гладкости следует (касательная должна быть перпендикулярна нормали):
N0 · B = 0
N1 · (2·A + B) = 0
Подставляем выражение для A из первой системы во вторую получим:
N0 · B = 0
N1 · B = 2 · N1 · (P1 — P0)
Это СЛАУ второго порядка, решив которую, найдём неизвестный вектор B, а зная его, определим вектор A. Система имеет решение только в случае, если нормали не параллельны (выражение N0x · N1y — N0y · N1x не равно нулю). Иначе считаем вектор A равным нулю, а B = P1 — P0, то есть сплайн вырождается в отрезок прямой. Решать систему даже второго порядка, я рекомендую методом Гаусса с выбором ведущего элемента, а не методом Крамера. В случае почти вырожденной матрицы разница может быть заметной.
Применим эти сплайны к аппроксимации единичной окружности. Получим:
Для 10 равномерных точек максимальное отклонение от окружности получается равным 1.26·10–3, а для 20 точек = 7.67·10–5
В тех случаях, когда направление нормалей неизвестно, я поступаю следующим образом. Для текущей точки проводим отрезок между предыдущей точкой и следующей. Затем строим перпендикуляр к этому отрезку:
Можно придумать что-то другое, но так получается совсем просто:
Ni, x = Pi+1, y — Pi-1, y
Ni, y = Pi-1, x — Pi+1, x
Добавлю, что в одну сторону смотрит нормаль или в противоположную — разницы нет.
Ниже показана кривая построенная на случайном наборе точек и с нормалями определёнными указанным методом:
