Заданную кривую -> Безье.

Кривая Безье – основной инструмент для построения произвольных кривых, странно что в сети проблематично найти толковую методику даже для преобразования в Безье сегмента окружности. C одной стороны это понятно - точного преобразования для сегмента окружности не существует в природе, но обзор приближённых методов с их достоинствами и недостатками имхо нужен.

 

Для построения кривой Безье, необходимо иметь 4 опорные точки (x0, y0), (x1, y1), (x2, y2), (x3, y3), причём точки (x1, y1), (x2, y2) не лежат на кривой. Имея уравнение окружности, мы можем получить только точки, лежащие на самой окружности – так и сделаем – поставим на неё две вспомогательные точки (x1', y1'), (x2', y2'), так чтобы они разделили сегмент окружности на три равные части – проще всего это естественно сделать на основе полярного представления сегмента окружности.

Затем те же точки можно представить через параметры кривой Безье и приравняв известные координаты (x1', y1'), (x2', y2') выразить через них искомые координаты точек (x1, y1), (x2, y2):
x1 = -0.8333(3)*x0 + 3*x1' - 1.5*x2' + 0.3333(3)*x3
x2 = 0.3333(3)*x0 - 1.5*x1' + 3*x2' - 0.8333(3)*x3
y1 = -0.8333(3)*y0 + 3*y1' - 1.5*y2' + 0.3333(3)*y3
y2 = 0.3333(3)*y0 - 1.5*y1' + 3*y2' - 0.8333(3)*y3
Эти формулы верны для точек (x1', y1'), (x2', y2') разбивающих дугу окружности на 3 равные части. В общем случае можно использовать любые вспомогательные точки (x1', y1'), (x2', y2'), лежащие на окружности, но коэффициенты тогда будут другими.

Достоинство этого подхода – довольно неплохое приближение, особенно в центральной части дуги и для небольших (угловой размер <= Pi/4) дуг. Недостаток в том, что линии соединяющие точки (x0, y0), (x1, y1) и точки (x3, y3), (x2, y2) не получаются касательными к исходному сегменту окружности, соответственно для преобразования окружности в комплект 4х Безье метод плохо подходит. Приближение контрольных точек (x1', y1'), (x2', y2') к начальной/конечной (x0, y0), (x3, y3) эту проблему не решает – получается «ни рыба ни мясо» - касательными к окружности направляющие линии всё равно не становятся (хоть и приближаются к ним), зато середина «портится».

Альтернатива – изначально плясать от касательных к окружности, располагая контрольные точки кривой Безье на них так чтобы середина сегмента нормально совпадала. Но как это рассчитать я пока не сообразил.

 

Y_Mur
Вот описание элипса через сплайны.
http://www.tinaja.com/glib/ellipse4.pdf

Тебе надо рабить 4 сплайна на состовляющие. Сплайн разбить нетрудно.

у нас есть параметр t который определяет точку на сплайне, а в нашем случии это угол поворота.
Мы можем разбить сплайн по этой точке и у нас будет 2 сплайна. Второй будет лишним.

 

Pavia

Тоже неплохой вариант - упрощает построение касательных к окружности, за счёт того что они направлены вдоль осей координат, но имеет и недостаток - чем короче дуга, тем точнее можно подобрать к ней Безье аналог, а если строить всегда 90°, а потом дробить уже Безье, то это преимущество коротких дуг исчезает.
Думаю всё же помедитировать над вариантом

начиная касательные не в узлах окружности 90°, а непосредтвенно на концах дуги - думаю там будут навороченные промежуточные выкладки, которые в итоге упростятся в несложные формулы типа как в #2.

 

Выигрывая в точности теряем в скорости. А спланы используются для скорости.

Там в статье дана подсказка как побить на произвольное число сплайнов. Так что там ошибка меньше. Там данны характеристики для драбления на 8 что точнее чем на 4. Но точности 4 сплайнов достаточно для большинства программ.

 

Pavia
Что точности достаточно в общем согласен, уточнение больше из "любви к искусству" Что работать универсальное преобразование будет медленее чем с фиксированными 4/8 точками и последующей разбивкой не уверен - выведу формулы сравню. Но даже если медленнее - это не приципиально ведь оно делается не во время отрисовки сплайна, а при его создании, что достаточно экзотическая операция, выполняемая либо по щелку мыши на кнопке "преобразовать окружность в кривую", либо вообще на этапе проектирования программы, так что скорость там точно не критична Точность конечно тоже не слишком критична, но с учётом того что сплайн создаётся один раз, а отрисовывается потом многократно и в общем случае при разном масштабе, то точность точно не помешает и ничего не замедлит - сплайн-то тот же самый, только опорные точки чуть сдвинуты.

 

для скорости считаем предварительно массив из 44 чисел 0x10000*sin(al) и 44 0x10000*cos(al) где al = 1..45 градусов. через градус. если надо круглее - квадратичный б сплайн подходит (все точки на линии).

 

_basmp_
В том та и суть что круглее не надо. Через безье проще, а скороть очень хорошая. У меня вся окружность(элипс) разбивается на 16-26 линий через безье.
Правда виндос разбивает лучше (я все варианты перепробовал, а у виндоуса лучше).

 

Y_Mur
Перечитал первый пост только сейчас понял что тебе нужно. Тебе немного теории не хватает.

Это не так.
Сплайн имеет прямую связь с Эрмитовой интерполяцией. И если знать 4 точки на кривой то можно найти коэфициенты Безье.
Или зная 2 точки и две производные.

А это мы знаем.

Немного теории
Уравнение Бузье. Опорные точки P0 P1 P2 P3
B(t)=P0*(1-t)^3+P1*3*(1-t)^t*t+P2*3*(1-t)*t^2+P3*t^3
Перепишем уравнение возведя в степень
B(t)=P0*(1-t)^3+P1*3*(1-t)^t*t+P2*3*(1-t)*t^2+P3*t^3=
= P0*(1-3*t+3*t^2-t^3)+ P1*(3*t-6*t^2+3*t^3)+P2(3*t^2-3*t^3)+P3*t^3=
перегрупируем по t
=(-P0+3*P1-3*P2+P3)*t^3+(3*P0-6*P1+3*P2)*t^2+(-3*P0+3*P1)*t+P0
=a*t^3+b*t^2+c*t+d
Что ничто иное как полином. А он применяется в Эрмитовой интерполяции.

Зная 4 точки легко найти решение пусть они равны T0 T1 T2 T3.
при t=0 подставляем в предыдущее уравнение имемм первая точка d=T0=P0
При t=1 последняя точка равна a+b+c+d=T3=P3
При t=1/3 будем иметь a/9+b/6+c/3+d=T1=8*P0/27+4*P1/9+2*P2/9+P3/27
При t=2/3 будем иметь 8*a/9+4*b/6+2*c/3+d=T2=P0/27+2*P1/9+4*P2/9+8*P3/27

Откуда опорные значение P1 и P2 легко найти.
P1=T3/3-3*T2/2+3*T1-5*T0/6
P2=T0/3-3*T1/2+3*T2-5*T3/6

Или через производные
Если нам известны две опорные точки и производные в них. P0 P3 - точки S0 S3 - значение производных в этих точках
Аналогично
P1=S0/3+P0
P2=P3-S3/3

 

Pavia

Имено так я и получил уравнения в #2, описав недостатки этого подхода.

А это уже не понятно: S - производная от y = SQRT(R*R - x*x) ?, но она же может обращаться в 0 или оо. И вообще не понимаю как эту запись раскрыть в координатах?
Кстати ты пробовал этот вариант практически? - точки P2, P3 получаются те же что и в первом варианте или другие?

 

Какой недостаток? Уровнение точно описывает дугу.

 

Точно только в точках t = 0, t = 1/3 и t = 2/3 и t = 1
В остальных местах приблизительно, но это не главное - середина от t = 1/3 до t = 2/3 получается хорошо, а вот начало/конец намного хуже и главное, что линия соединяющая P0-P1 явно не является касательной к окружности.

Хочу добиться чтобы направление этих линий P0-P1 и P3-P3 совпадало с касательными в точках P0 и P3, а уже длина этих линий определяло остальное совпадение наилучшим из возможного образом - как это посчитать пока не сообразил.

 

У меня почти один в один. У тебя ошибки в округлениях(из за округления)

А кто сказал что должны?

 

Если взять 1/4 окружности. Так только один пиксель вылез.

 

Не должны, но желательны хотя бы потому, что если хочешь разбить целую окружность на набор дуг, то в местах их стыковки получится не гладкий узел, а узел-стык под углом. Согласен, что для грубой экранной отрисовки это совершенно непринципиально, а вот если хочешь в векторном графическом редакторе выполнить для окружности действие "преобразовать в кривую", то эта нестыковка весьма неприятна. Так как там и масшабирование возможно и угловой стык сегментов на окружности совершенно неуместен с точки зрения дальнейшего редактирования объекта - во всяком случае "по умолчанию" там точно должен получаться гладкий-симметричный, а не угловой стык.

 

Кстати у меня не ошибки округления, а просто масштаб больше и дуга длиннее, я их специально такими выбрал для наглядности (картинка после копипастинга с экрана уменьшена, чтобы тут лишнего не захламлять).

 

Я вот что подумал у нас есть Sin и Cos так вот
Коэфициенты описывают уравнения вида.
=a*t^3+b*t^2+c*t+d

Вспомнир разложение в ряд Sin и cos он кончается вторым членом.

Это и будут эти коэфициенты. Откуда можно найти P.

Тогда ошибка будет примерно такая интеграл Sin(t)-t+(t)^3/6=0.02 около 0.02*150*Pi~9 пикселей не попадут на место при радиусе 150. Точнее будет если взять сплайн высшего порядка или разбить на несколько сплайнов. Лучше разбить так как точность возрастает быстрее.
При разбиении окружности на 8 сплайна ошибка 3.224*10^-4.

Чем меньше угол дуги тем точнее.

 

PS. Забыл написать. Точнее скорее всего не будет. Производные ты можешь выравнить, но окружность тогда не будет корректной.
Отсюда вывод делаем не одну кривую безье, а сплайн из 8 Тогда у тебя все совпадат. Нужно тачнее дели на большее число кривых.

 

Pavia
C sin и cos твою мысль не понял - это "доказательство точности"? или альтернативный метод построения?
Хотя подсказка интересная в том плане, что можно представить окружность параметрически через sin и cos, возможно это как раз и позволит найти решение через касательные - нужно помедитировать.

Ты же сам в #3 сослался на методику где разбивка окружности идёт через построение касательной и подбор их длины, но там частный случай для 90° - хочу тоже самое, но универсально для произвольного угла и сразу (без дробления/объединения промежуточных сплайнов). Так что это как минимум возможно ) А кроме того, обрати внимание - на рис в #12 Безье пересекает окружность в двух точках, а в остальных "идёт рядом". Играя с Безье в графическом редакторе очень легко добиться того-же эффекта (пересекает в двух точках, а в остальных "идёт рядом") но на основе линий P0-P1 и P2-P3 выравненнных по касательным. В этих двух точках пересечения опять имеем точное совпадение, можно добиться и того, чтобы эти точки располагались в позициях t=1/3 и t=2/3 но опорные точки получаются другие (расположены на касательных), и расчёт этого случая через уравнения вида #2 невозможен в принципе. Какой вариант точнее - первый (#2) с заведомо неправильными касательными или этот второй подход пока сказать не могу, поскольку не знаю как его сунуть в свою программу чтобы протестировать, но этот второй вариант с касательными удобнее с практической точки зрения и за это ему небольшую потерю точности по сравнению с первым вариантом можно и простить, если конечно она действительно есть - может оказаться всё наоборот с касательными будет точнее

 

Это альтернотивный метод он должен быть максимально точным(или около того). Он позволил мне сделать оценку точности. Я ее распростроняю на другии методы. Причем хорошо ложиться к примеру на твоем рисунки отклонение от косательной состовляет 15 пикселей при дуге 3/4*Pi. В моем 3 пикселя при дуге 1/2*Pi что вполне хорошо ложиться на эту теорию.

Возможен при дугах длиной Pi/3 и меньше точности хватает чтобы линии совпадали с касательными. Смотри рисунок 2.png

Что касается с выравненными косательными и нет, то потеря точности не велика. С этим согласен, но оценку получить не удалось.