Интерполяция: рисуем плавные графики с помощью кривых Безье. Версия 2
Доброго времени суток, харбачитатель.
Так начинается статья, которая представляет сообществу первый, опубликованный здесь, алгоритм интерполяции:
В этой статье мне хотелось бы рассказать об одном придуманном алгоритме (или скорее всего — переизобретённом велосипеде) построения плавного графика по заданным точкам, используя кривые Безье. Статья была написана под влиянием вот этой статьи…
Дело в том, что автор этой статьи пошел не прямым путем, а окольным, используя громоздкую тригонометрию половинных углов для вычисления тангенса угла φ. Кроме того автор не уделил внимание анализу длин опорных отрезков, просто приняв, что данные равномерно распределены по оси Х с фиксированным шагом, и поэтому длины опорных отрезков тоже можно взять фиксированными по оси X.
На самом деле, для того, чтобы вычислить координаты опорных точек не нужна тригонометрия, не нужно вычислять угол φ и даже не нужен коэффициент k. Всё что нужно — это знание теоремы Пифагора и немного смекалки в определении пропорций между отрезками. При этом у меня получился алгоритм, не требующий равномерности шага и даже строгой направленности вдоль оси X. Вы можете направлять данные произвольно, хоть вдоль оси Y, хоть по кругу.
Для понимания алгоритма вычисления координат опорных точек построим рисунок, аналогичный соответствующему рисунку из статьи первой версии.
Я только перенес точку D на отрезок AB таким образом, чтобы отрезок CD был также наклонён к оси X, как и отрезок B1C1. Нетрудно понять, что при этом треугольник DAC является равнобедренным. Также заметим, что длина отрезка CD равна двойной величине по длине опорного отрезка справа от точки A, при котором интерполяционная дуга будет близка к окружности. На рисунке выше такая длина обозначена двумя серыми линиями, перпендикулярными красной линии с опорными отрезками и отрезку CD. Примем длину CD в 2 относительные единицы. Также сразу заметим, что максимально возможная длина опорного отрезка слева в таких же единицах будет равна отношению |AB|/|AC|. Соответственно в случае, когда |AB|=|AC|, максимальная длина опорного отрезка слева тоже будет равна 1. Обозначим через m требуемую для построения относительную длину опорных отрезков. Обычно при использовании кубических кривых Безье m=0.333, а для квадратичных m=0.5.
Теперь мы можем написать формулы для расчета координат опорных точек слева и справа:
XB1 = XA-m*ΔXCD*|AB|/|AC|/2 | (1) | |
YB1 = YA-m*ΔYCD*|AB|/|AC|/2 | (2) | |
XC1 = XA+m*ΔXCD/2 | (3) | |
YC1 = YA+m*ΔYCD/2 | (4) |
Здесь
X и Y — это координаты, соответствующие обозначениям, точек;
ΔXCD=XС-XD и ΔYCD=YС-YD (нет модуля, значения могут быть больше или меньше нуля).
Абсолютные значения модулей длин отрезков легко определяются с помощью теоремы Пифагора. Поэтому по сути нам здесь может представлять некоторую сложность определение координат точки D.
Давайте примем всю длину отрезка AB, на которой располагается точка D, за 1. Тогда длина отрезка AD относительно AB (обозначим через d) d=|AC|/|AB| и координаты точки D:
XD = XA-d*ΔXAB | (5) | |
YD = YA-d*ΔYAB | (6) |
И несколько оптимизируем формулы (1), (2), (3) и (4) сделав замену переменных, используя d и m2=m/2:
XB1 = XA-m2*ΔXCD /d | (7) | |
YB1 = YA-m2*ΔYCD /d | (8) | |
XC1 = XA+m2*ΔXCD | (9) | |
YC1 = YA+m2*ΔYCD | (10) |
И последний штрих, который на мой взгляд надо добавить в алгоритм — это устранение завалов, которые появляются при сильных углах наклона опорных отрезков, в том числе при большой разнице масштаба по оси Y по сравнению с масштабом по оси X. В такой ситуации кривая может через чур сильно начать вытягиваться направо или налево. Разумно полагать, что всё-таки максимумы и минимумы в природе более-менее симметричны и справа и слева. Поэтому мы можем ввести более мягкое условие, чем требовать от исходных данных равномерный шаг. К тому же интерполяция зачастую и необходима для того, чтобы привести исходные данные с неравномерным шагом к равномерному шагу. Будет логично длину опорных отрезков справа и слева сделать одинаковыми, ну или близкими по величине. Для начала мы сделаем замену переменных в формулах 7 и 8, обозначив через m1=m2/d:
XB1 = XA-m1*ΔXCD | (11) | |
YB1 = YA-m1*ΔYCD | (12) |
Рассчитав m1 и m2, мы проверяем, чтобы большее из них не было слишком велико. Можно установить требование, скажем чтобы больший из опорных отрезков был не более, чем на 7% больше меньшего. Визуально разница длин опорных отрезков на 5% совсем не заметна, при разнице в 10% уже немного заметна асимметрия.
На рисунке показаны два результата интерполяции на исходных данных, которые были использованы в первой версии алгоритма, с расположением данных вдоль оси X и вдоль оси Y. При построении использовались кубические кривые Безье с m=0.33333 для средних участков, квадратичные кривые Безье с m=0.4 для крайних участков и требование асимметрии длин опорных отрезков не более 7%.
Собственно это и было моим ответом автору первой версии этого алгоритма. Работу алгоритма в режиме онлайн вы можете проверить у меня на сайте. Кстати сайт работает на https.net сервере собственной разработки под Windows.
