Надо же, оказывается, мне уже три года стыдно за этот должок. Пообещал и не сделал.
Но меня просят (через ЛС) развить тему, рассказать, что я знаю про эту задачу.
И я постараюсь довести это до ума.
Литературы в своём бумажном архиве я не нашёл. По жизни следил я за журналами
CAD,
CAGD,
JCAM. Теперь журналов развелось много; и я уже почти не слежу. Гуглить можно "circular spline", "arc spline (approximation)".
Задачу, которую я намерен осветить, можно сформулировать так:
Найти кривую с кусочно-постоянной кривизной, аппроксимирующую заданную кривую 
с заданной точностью.Предлагаемое решение идёт чисто из моей головы; других (решений) не знаю. Результирующая кривая с кусочно-постоянной кривизной состоит, понятно, из гладко сопряжённых кусочков прямых и окружностей.
Так что речь идёт не только о сплайнах:
--- произвольная достаточно приличная кривая, о которой мы знаем или можем узнать всё. Из этого всего понадобятся наклон касательной
, кривизна
и решения уравнения
, т.е. экстремумы кривизны (вершины кривой). Функция
не обязана быть непрерывной.
Мы разбиваем кривую на достаточно малые отрезки-дуги следующим образом:
(1) выделяем вершины кривой; таким образом, кривизна на каждом участке будет монотонна, что впоследствии и позволит сгаранатировать точность аппроксимации;
(2) разбиение кривой внутри каждого участка должно быть как минимум таким, чтобы каждая дуга однозначно проектировалась на свою хорду (будет там внутри перегиб или нет --- нам до лампочки); уже на этом этапе мы сможем определить точность будущей аппроксимации и, если она недостаточна, вставить промежуточную точку.
Пункт (2) можно реализовать в виде сканированя кривой с неким мелким шагом
, с выбором очередного узла
будущего circular spline исходя из наперёд заданной точности
. Замечу, что нам не нужны точки перегиба кривой и узлы оригинального сплайна.
Нижеприведённая картинка нарисована по несколько иному поводу, и не является иллюстрацией предлагаемого алгоритма (он даст несколько б
ольшую точность). Но кое-что она проясняет и иллюстрирует.
а) Заданная кривая, представленная мелкими точечками, --- спираль Корню. У неё, как известно, нет вершин: кривизна --- линейная функция длины дуги. Поэтому первый этап разбиения отменяется, и мы начали со второго. Выбрали 11 точек, соблюдя условие однозначного проектирования на хорду.
b) Серенькие области --- некие оценки точности интерполяции/аппроксимации (повторяю --- это некий другой алгоритм). Здесь важно то, что монотонность кривизны не позволяет никакой аппроксимирующей кривой (тоже с возрастающей или тоже с убывающей кривизной, с некими граничными условиями на закреплённых концах) выйти за эти пределы.
c) Количество узлов увеличено с 11 до 15. При увеличении количества точек в n раз ширина области уменьшается в n^3 раз.
Писать буду по частям: так мне психически проще. Это была интродукция; вопрошавшие пусть видят, что я начал отвечать.
update: 05.01.2011 - переместил рисунок
Сейчас займусь реализацией. Чтобы каждый раз все не пересчитывать, попробую отдельно рассчитывать максимально возможную длину для каждого следующего участка.
и 
с наклонами касательных 
и 
в этих точках. Имеется, как видно, одна степень свободы, можно минимизировать, например, скачок кривизны в точке сопряжения двух дуг. 
и 
; к координатам мы присовокупили известные наклоны касательных и крив
превращается в точку 
, а точка 
--- в точку 
. Вычисляя наклоны касательных в этой системе координат, 
, надо привести их к интервалу 
(равенство (1) это, естественно, предполагает).
).
из 
. Понятно, что в предельных положениях 
и 
эти дуги совпадают с границами линзы. Можно доказать, что если кривизна кривой изменяется монотонно, то дуги 
, 
сидит в этой линзе. 
Это и есть гарантированная точность нашей будущей аппроксимации. А в роли кривой с монотонной кривизной, которой мы подменим нашу заданную кривую (Безью, Корню, etc), выступит 
, то мы получаем линзу нулевой ширины. Единственная кривая с монотонной(=постоянной) кривизной, удовлетворяющая таким граничным условиям, есть дуга окружности (
). И вообще, 
имеет наклоны касательных на концах 
; кривизны двух её участков, 
и 
, равны 
и 
. При этом, очевидно, мы можем выбрать свободно одну из кривизн. Вторая однозначно определяется уравнением 
двух дуг определяются так: 
Пригодится и наклон касательной к бидуге в точке сопряжения ![$$
\begin{array}{l}
\cos\tau_{_T} =\hphantom{-}\dfrac{p^2\cos\alpha + 2p\cos\omega + \cos\beta}{p^2+2p\cos\gamma+1},
\\[6pt]
\sin\tau_{_T} =-\dfrac{p^2\sin\alpha + 2p\sin\omega + \sin\beta}{p^2+2p\cos\gamma+1},
\end{array}
\quad
\tan\dfrac{\tau_{_T}}{2}={-}\dfrac%
{p\sin\frac{\alpha}2+\sin\frac{\beta}2}
{p\cos\frac{\alpha}2+\cos\frac{\beta}2}\,.\quad\eqno(3)$$](https://dxdy-04.korotkov.co.uk/f/b/e/4/be4c3ddb1b37f4dfa16fd0020eb793a382.png "$$
\begin{array}{l}
\cos\tau_{_T} =\hphantom{-}\dfrac{p^2\cos\alpha + 2p\cos\omega + \cos\beta}{p^2+2p\cos\gamma+1},
\\[6pt]
\sin\tau_{_T} =-\dfrac{p^2\sin\alpha + 2p\sin\omega + \sin\beta}{p^2+2p\cos\gamma+1},
\end{array}
\quad
\tan\dfrac{\tau_{_T}}{2}={-}\dfrac%
{p\sin\frac{\alpha}2+\sin\frac{\beta}2}
{p\cos\frac{\alpha}2+\cos\frac{\beta}2}\,.\quad\eqno(3)$$")
Бидуги с 
будут располагаться внутри линзы (бидуги с 
и 
легко проассоциировать с границами линзы). 
. Так, 
даст бидугу с точкой сопряжения "посредине" (на локальной оси ординат). Рекомендую, однако, использовать значения граничных кривизн 
нашей заданной кривой, и выбрать 
в пределах 
, где 
(эти значения получены из уравнений 
и 
). Например, взять 
Такой выбор связан с тем, что имеется более жёсткая граница на расположение кривых с монотонной кривизной.
такой границей является вышеупомянутая линза.
границу можно сузить до более сложной конструкции (зелёненькой):
, часть бидуги 
, имеет кривизну 
, ту самую, что и наша оригинальная кривая в точке 
, часть бидуги 
, имеет кривизну 
, ту самую, что и наша оригинальная кривая в точке 
и 
) и есть эта более жёсткая граница. Неулучшаемая.
. Для наклона касательной преобразование имеет вид 
. Мы таким образом в имевшееся разбиение 
навставляли аналогичных промежуточных точек. Новая конструкция вполне описывается новой последовательностью 
При восстановлении кривой по этим данным мы для любой 
-той точки строим дугу окружности, выходящую из неё под углом 
и приходящую в точку 
. Такая дуга единственна и неповторима. 
появится какая-нибудь гадость вроде 
с двумя вершинами.