Метод Длины Хорды

Если интерполированная кривая довольно точно следует исходной ломаной, то длина отрезка кривой между двумя смежными точками будет очень близка к длине хорды между двумя этими точками, а длина интерполтрованной кривой будет очень близка к длине исходной ломаной. На рисунке ниже, каждый отрезок кривой интерполируемой ломаной очень близок к соответствующей ему хорде, а длина кривой близка к длине исходной ломаной. Таким образом, если поделить область, следуя распределению по длинам хорд, то параметры будут аппроксимацией (приближением) параметризации по длине дуги. Это суть метода длины хорды, или хордового метода.

Пусть исходные точки равны d₀, d₁, ..., d_n. Расстояние между d_i-1 и d_i равно |d_i-d_i-1|, а длина исходной ломаной равна сумме длин этих хорд:

Отсюда, показатель длины хорды от исходной точки d₀ до исходной точки d_k, обозначается L_k, по отношению к длине исходной ломаной, равен

Отсюда, если мы выбрали параметризацию по длине дуги для интерполированной кривой, то область нужно разбить в отношении L_k. Говоря точнее, если область - это [0,1], то параметр t_k должен быть равен значению L_k:

,

где L - это длина исходной ломаной. В этом случае параметры делят область в отношениях длин хорд.

Взгляните на пример. Путсь у нас есть четыре исходные точки (n = 3): d₀ = < 0,0 >, d₁ = < 1,2 >, d₂ = < 3,4 > и d₃ = < 4,0 >. Длина каждой хорды равна

,

а полная длина равна

В итоге получим соответствующие параметры:

Следующие рисунки показывают исходные точки и распределения параметров по методам равномерного распределения и длины хорды.

Что, если область [a,b], а не [0,1]? Заметьте, что L_k - это число между 0 и 1. Так как длина [a, b] равна b-a, L_k(b-a), 0 <= k <= n, то делим [0,b-a] в том же отношении, что и [0,1]. Таким образом, следующие параметры делят [a,b] в соответствии с длинами хорд:

Метод длины хорды широко используется и обычно хорошо работает. Так как известно, что кривые в виде многочлена не могут быть параметризованы до единичной скорости [to have unit speed] , поэтому метод длины хорды может быть только приближением. Иногда из-за большой длины хорды может получится слишком большая выпуклость. На рисунке ниже показаны черная и синяя кривые, интерполирующие 7 исходных точек. Как видите, обе кривые имеют схожую форму, кроме последнего отрезка и еще одного, немного "виляющего", вычисленного по методу длины хорды. Последние отрезки кривых очень отличаются и кривая по методу длины хорды имеет бóльшую выпуклость и отклоняется от кривой, полученной по методу равномерного распределения. Это известная проблема метода длины хорды.

Центростремительный Метод

E. T. Y. Lee предложил этот центростремительный метод. Допустим, мы ведем машину по извилистому спуску. Приходится быть очень аккуратными на крутых поворотах, чтобы ускорение по нормали (т.e. центробежная сила) не должно быть слишком большим. Иначе машина может потерять управление. Чтобы ехать безопасно, Lee предположил, что нормальная сила должна быть пропорциональна изменению угла. Центростремительный метод - это аппроксимация этой модели. Фактически, можно сказать, что центростремительный метод - это расширение метода длины хорды.

Пусть исходные точки равны d₀, d₁, ..., d_n. Во-первых, нужно выбрать положительное значение "силы" a. Обычно a = 1/2 для извлечения квадратного корня. Затем, расстояние между двумя смежными точками вычисляется как |d_k - d_k-1|^a , а не так, как обычно: |d_k - d_k-1|. Длина исходной ломаной по таким вычислениям равна

Отношение расстояний от d₀ до d_k исходной ломаной по отношению к полной длине равно

Таким образом, L₀ = 0, L₁, ..., L_n = 1 делят [0,1] в соответствии с длиной исходной ломаной по новым вычислениям. Отсюда, параметры равны

Если a = 1, то центростремительный метод становится методом длины хорды и, следовательно, первый является расширением последнего. Если a < 1, скажем, a = 1/2 (т.e. квадратный корень), |d_k - d_k-1|^a меньше, чем |d_k - d_k-1|. Следовательно, влияние более длинной хорды (т.e. длина > 1) на длину исходной ломаной уменьшается, а влияние более короткой (т.e. длина < 1) - увеличивается. Из-за этой характеристики Lee решил, что центростремительный метод лучше подходит для прохождения крутых поворотов, чем метод длины хорды.

Давайте повторим пример, обсужденный в методе длины хорды. Имеем четыре исходные точки (n = 3): d₀ = < 0,0 >, d₁ = < 1,2 >, d₂ = < 3,4 > и d₃ = < 4,0 >. Возьмем a = 1/2 и длина каждой хорды по таким вычислениям будет

Полная длина равна

Таким образом, параметры равны

Далее идет распределения трех наборов параметров, вычисленных по методам равномерного распределения, длины хорды и центростремительному.

Взглянем на еще один пример. Далее показаны четыре исходных точки, интерполированные в три кривых B-spline по методу равномерного распределения (черный цвет), длины хорды (синий), и центростремительному (красный). Как видите, в методе равномерного распределения получается острый пик, а в методе длины хорды получается две больших выпуклости и две очень близких смежных точки хорошо интерполируются.

Можно ли сказать, что центростремительный метод лучше двух других? Следующий пример показывает, что не всегда. Имеем 7 исходных точек и черную, синюю и красную кривую, полученные соответственно по методам равномерного распределния, длины хорды и центростремительному методу. В данном случае метод равномерного распределения дает очень близкую интерполяцию. Центростремительный метод немного отстает от хорошего результата, который дает метод равномерного распределения. Ну а метод длины хорды вообще слишком выдается наружу.