Аппроксимация окружности кубической кривой Безье

[Алексей К.]

_Ivana в сообщении #762136 писал(а):

Это готовый рецепт для ТС, не содержит формул

Dyx,
подтвердите, что Вы поняли этот рецепт (я пока не понял, но с утра наверняка смогу понять). Если не поняли, изложим попроще, с картинкой.

-- 09 сен 2013, 23:43:23 --

_Ivana,

если Вы следовали нотации, которую я предложил, и не поленились решить, напишите плииз тупо формулу для $p$, не жадничайте.

-- 09 сен 2013, 23:45:30 --

Пока балаболил с ребятами, сам десять раз решил бы. Тем более, что раз пять уже было...

[_Ivana]

Алексей К. простите, я не вникал в ваши формулы и не решал аналитически, я как завещал ТС сделал без формул, сейчас выложу картинку из геогебры.

http://s018.radikal.ru/i516/1309/63/c0f23e13a759.png

$I, J$ - опорные точки, находятся как пересечение касательных $BI$, $DJ$ перпендикуляром к $EG$ в точке $H$, $GH = EG/3$

[Алексей К.]

Dyx в сообщении #762133 писал(а):

Я ещё в школе учусь.

Тогда будем считать, что я не на Вас ту бочку накатил , а на тех которые...
Успехов!

-- 10 сен 2013, 00:03:43 --

А хотя бы тригонометрия, которую я использовал, пися выше формулы для $P_{0,1,2,3}$, Вам, Dyx, известна? Понятна?

[Dyx]

_Ivana Спасибо Вам большое! Это я понимаю.) Сейчас сделаю, и посмотрю как оно на самом деле.
Ну а завтра начну читать статьи и прочее для того, чтобы вернуться и продолжить тему с уравнениями.
Так как вычислить опорные точки - это одно, а высчитывать саму кривую - это не менее важно для меня.
И спасибо за геогебру! не когда о ней не слышал! Очень рад, что повстречал этот форум. Спасибо!

-- 10.09.2013, 00:09 --

Цитата:

выше формулы для , Вам, Dyx, известна? Понятна?

Копирую теги из другой вкладки. Да, понятна.

[Алексей К.]

Алексей К. в сообщении #762137 писал(а):

Нет, не очевидно, тем, кто не ел эту собаку.

_hum_,

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

Средняя (интегрально) кривизна кривой Безье, видимо, близка к (постоянной) кривизне аппроксимируемой окружности. Но она несомненно имеет экстремум в средней точке, просто в силу симметрии. Два соседних экстремума кривизны находятся где-то поблизости от двух точек, экстремально удалённых от окружности (поблизости, но наверняка не точно там). И, конечно, на концах есть локальные "концевые" минимумы-максимумы кривизны, которые, кажется, не принято называть "экстремумами"). Имеем такие вот колебания кривизны около некого среднего значения.

Совпадения кривизн (т.е. касания второго порядка) в тех трёх точках, где мы имеем касание первого порядка, в таких "синусоидальных" условиях ожидать не приходится. Т.е. именно там кривизны НЕ совпадают. Что никак не мешает вполне приличной интерполяции.

Не знаю, понятно ли слова подобрал... Картинку надо, конечно.

[_Ivana]

http://s020.radikal.ru/i710/1309/8e/8d9b0d57bc96.png
Точнее даже вот так, с опорными точками
http://i069.radikal.ru/1309/3a/962bb96cd22a.png

4 кривых - четвертинки окружности по моей геометрической реализации алгоритма Алексей К., без формул, просто параметрическим проездом по отрезкам. Черная - окружность, красная - кривая Безье. Аналитическое выражение координаты опорных точек при единичном радиусе окружности $4(sqrt(2) - 1)/3$

UPD - по двум полуокружностям, координаты опорных точек $4/3$
http://i020.radikal.ru/1309/c7/5c1f7865c2c4.png

(Оффтоп)

Кому своих улиток изучать, а мне надо ПИД регулятор стоящего на вершине куба рассчитывать, а получается отвлечение на забавную тривиальщину

[_hum_]

Алексей К., ewert, мое

_hum_ в сообщении #762118 писал(а):

И для больших размеров тоже? Просто на маленькой окружности отличия могут быть менее заметны, чем на большой.

относилось к "отлично" в

Алексей К. в сообщении #762114 писал(а):

На четвертинке окружности отлично работает.

Насколько я понял, Алексей К. построил и на глаз увидел, что кривая "отлично совпадает" с четвертью окружности. Вот я и интересовался, останется ли это "отлично" таким же для глаза, если размер увеличить до размера экрана (наверняка же ТС аппроксимация Безье нужна была именно для компьютерной графики). Меня смущало условие

Алексей К. в сообщении #762073 писал(а):

требуем, чтобы верхушка кривой совпала с верхушкой дуги окружности

которое, как мне кажется, слишком ограничивает поведение кривой, заставляя ее излишне "деформироваться". И могло оказаться, что построенные по этому методу кривые для больших (сравнимых с экраном) окружностей выглядят не очень похожими на дуги, тогда как построенные по какому-нибудь другому - вполне прилично.

[Алексей К.]

Алексей К. в сообщении #762073 писал(а):

Берём кривую Безье,

$$P_0=(-a,0),\quad P_1=(-a+p\cos\alpha,p\sin\alpha),\quad P_2=(a-p\cos\alpha,p\sin\alpha),\quad P_3=(a,0).$$

В этой нотации ($a$ --- полухорда, $r=\dfrac{a}{\sin\alpha}$ --- радиус окружности) обсуждаемый метод (касание дуги и Безьюхи в средней точке) даёт $p=\dfrac{4a}{3(1+\cos\alpha)}$. Максимальное отклонение

$$d\approx \frac{x_0^2+(y_0+a\ctg\alpha)^2-r^2}{2r}=\frac{a}{27}\cdot\frac{\tg^5{\frac{\alpha}{2}}}{1+\tg^2{\frac{\alpha}{2}}}=\frac{2r}{27}\cdot\left(\frac{\tg^3{\frac{\alpha}{2}}}{1+\tg^2{\frac{\alpha}{2}}}\right)^2,\quad x_0,y_0=x(t_0),y(t_0),\quad t_0=\dfrac12\pm\dfrac{\sqrt3}{6}. $$

Так, для полуокружности $(\alpha=90^\circ,\; r=a)$ имеем $d\approx \frac1{54}r\approx 0.0185r$, для четвертинки $(\alpha=45^\circ)$ --- $d\approx 0.00027\,r$, а для одной шестой --- в 11 раз меньше.

-- 10 сен 2013, 10:10:11 --

_hum_ в сообщении #762203 писал(а):

которое, как мне кажется, слишком ограничивает поведение кривой, заставляя ее излишне "деформироваться".

Вот я себе и проверил тогда это "кажется" вышенаписанным, "на глаз". Что касается других методов --- то, например, рациональная кривая второго порядка даёт точную окружность. Если же другие методы остаются в рамках кубических полиномов, то, очевидно, от симметричности мы никуда не денемся. И тогда всё, что остаётся --- чуть-чуть опустить верхнюю точку кривой, тем самым слегка распределив то максимальное отклонение, теперь не на два, а на три экстремальных отклонения. Также понятно, что это опускание может быть на величину порядка $d/2,d/3$. Существенного выигрыша (на порядки) от этого не происходит, и другие методы, типа минимизации площади между ними, тоже будут стрельбой из пушек по воробушкам.

[Алексей К.]

Если модераторы сочтут полезным уточнить название темы, я бы предложил "Аппроксимация окружности кубической кривой Безье".

[Deggial]

Алексей К. в сообщении #762273 писал(а):

Если модераторы сочтут полезным уточнить название темы, я бы предложил "Аппроксимация окружности кубической кривой Безье".

Название изменил

[_hum_]

Алексей К.
Что-то, если честно, перестал понимать, почему точки $P_1$ и $P_2$ выбираются таким специфичным образом - лежащими на прямых $x = -a \pm y \,\mathrm{ctg} \alpha$ (где $a$ и $\alpha$ заранее фиксированы, поскольку задают дугу). Ведь это ограничение степеней свободы (было по две на каждую точку, стало по одной).
Далее, если опять же я правильно понимаю, у вас дуга и кривая Безье совпадают в трех точках: начале, окончании и вершине. Спрашивается, а если это условие снять, не получится лучше аппроксимация (максимальная относительная ошибка аппроксимации будет меньше)? Опять же, а если пойти дальше и снять еще условие на симметричность, не может ли точность аппроксимации улучшиться и почему?

[_Ivana]

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

(Оффтоп)

Да, я в курсе, что можно просто взять больше секторов меньшего углового размере

[_hum_]

_Ivana в сообщении #762686 писал(а):

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

(Оффтоп)

Да, я в курсе, что можно просто взять больше секторов меньшего углового размере

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

[_Ivana]

_hum_, я тоже не спец, но тут то все просто и понятно. Вы обращались с вопросами к конкретным участникам форума, но если интересуют мои рассуждения, то:
1) внутренние опорные точки должны лежать на касательных к окружности в крайних точках - чтобы касательные кривой и окружности в крайних точках совпадали и кривые хорошо склеивались друг с другом. Если это условие убрать, возможно можно повысить точность, но цена больно дорогА, а эффект обещает быть мизерным (если вообще будет). Итого - минус 2 степени свободы из 4-х.
2) если избавимся от симметрии, тоже ничего хорошего не добьемся. Строго показать это я затрудняюсь. Можно промоделировать и рассмотреть минимум функции ошибки от 2 переменных (оставшихся 2 степеней свободы).
3) итого остается одна степень свободы, которая может определяться прохождением кривой через вершину дуги - это дешево, надежно и практично. А про возможную ловлю блох и уменьшение погрешности при варьировании этой степенью свободы Алексей К. уже писал в посте про пушку и воробьев.

[Алексей К.]

_hum_ в сообщении #762671 писал(а):

Что-то, если честно, перестал понимать, почему точки $P_1$ и $P_2$ выбираются таким специфичным образом

_hum_,

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

А зацепившись за какие-то другие точки, будем иметь вообще всё не так. Может даже симметрии где-то как-то пропадут, во что мне даже утром трудно поверить. Тут надо думать и мудрить.

Я же изначально думал о дуге окружности, которую неизвестно с чем будут сопрягать.

А может, и не будут сопрягать? Может она будет сама по себе? Если это заранее известно, то да, наверняка и очевидно существует лучший вариант, со всеми степенями свободы. И симметрию можно не навязывать, решение само по себе будет симметричным (типа "уверен, окажется симметричным").

Но не намного лучше результат будет (если модель не менять). Максимум чего, может добьёмся --- три "свободных" интерполянта на полной окружности дадут тот же эффект, что раньше давали четыре "зажатых".

(Оффтоп)

В общем, лично я в такого рода задачках ценю простоту.
Некие усложнения хороши как экзерсисы для студентов. На них я, собственно, и осваивал премудрости этого ремесла, к сожалению, в далеко не студенческом возрасте. А когда ЧПУ-шники стали приставать с вопросами.

Лет 7-14 назад я регулярно просматривал содержание журналов типа Computer-Aided (Geometric) Design. Могу заверить, что эта тема звучала в публикациях. Но я не сохранил ссылок, а мог и не заинтересоваться. Они нередко позволяют себе статейки уровня хорошей курсовой (на ихнее pHD, наверное тоже надо чего-то публиковать. Сам даже пару раз отметился.