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

[Pavia]

_hum_

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

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

Если бы выбор был произволен то произвольную кривую мы бы и получили. А по задаче надо найти наилучшее приближение к дуге окружности.
Это не строгое условие и опорные точки можно брать произвольно.
Для примера несколько условий
1) При построение можно взять условие что-бы производные на концах кривой были равны производным на концах дуги.
2) Что-бы кривая проходила точно через вершину. Но этого условия явно не достаточно поэтому, _Ivana предложил дополнить касательными.
4) Взять произвольные 2 точки на окружности.
3) Можно пойти по методу наименьших квадратов,
4) А ещё лучше принцип максимального правдолюбия.
Можно придумать ещё много условий.

_Ivana

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

_hum_, я тоже не спец, но тут то все просто и понятно. Вы обращались с вопросами к конкретным участникам форума, но если интересуют мои рассуждения, то:

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

[Алексей К.]

Pavia в сообщении #762776 писал(а):

что-бы производные на концах кривой были равны производным на концах дуги

Вы, наверное, имеете в виду равенство (единичных) касательных векторов, а не каких-то абстрактных производных (по безликому параметру).

[_hum_]

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

_hum_,

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

Да все прозаичнее. В моем понимании исходная задача аппроксимации плоской кривой $\gamma$ (в нашем случае дуги $\gamma_{r,\alpha}$ окружности радиуса $r$, с опорным углом $\alpha$) некоторой кривой из семейства кривых Безье третьей степени $\mathrm{Be}_3$ есть задача поиска кривой, минимизирующей некоторый заранее заданный функционал ошибки аппроксимации $d = d(\gamma_1, \gamma_2)$.
При нашей беседе вроде бы сошлись на том, что для начала можно в качестве такового выбрать максимум относительного расстояния между кривыми. Итого, задача сводится к задаче поиска:

$$\gamma^* = \arg \min_{\gamma \in \mathrm{Be}_3} d(\gamma_{r,\alpha}, \gamma).$$

Вы предложили рассмотреть более узкую задачу - поиска оптимальной аппроксимации не в множестве всех возможных кривых из $\mathrm{Be}_3$, а в более узком множестве, элементы которого должны удовлетворять след. условиям:

1) начала и окончания кривых должны совпадать с таковыми для дуги;
2) кривые должны иметь общую точку с вершиной дуги;
3) опорные точки кривой должны быть симметричны относительно оси симметрии дуги;
4) опорные точки должны лежать на касательных к дуге, проходящих через ее начальную и конечные точки.

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

[Алексей К.]

Я, может и переборщил с "очевидностями".
Условия 1) и 4) я накладывал, мысленно предполагая сопряжения с некими другими элементами. Об этом следовало, видимо, явно заявить. Я "очевидничал", например, с симметрией, предполагая, что все собеседники рассматривают задачу в условиях 1) и 4).
Условие 2) я не накладывал, и взял как легко исследуемое на экстремальные расстояния, и как базовое для поиска других решений. Шевеление верхней точки я явно допустил, но обозвал мелочью.

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

[Dyx]

В день обращения, долго не могу заснуть из-за мысли, что не потяну я эту задачу, а так хочется...
Следующий день решил начать с изучения этой задачи, но с обратной стороны. Прежде чем рассчитывать опорные точки, решил сначала построить саму кривую. Получилось, нарисовал её.
И тут я начал интересоваться, как сделать обратное и мне сказали, что особо фантазировать не чего, не нужны углы и прочее. Если известны начало, конец и максимум и в придачу ещё, что отрезок этих опорных точек параллелен отрезку из точки начало\конец, то этого более чем достаточно. Теперь сижу думаю, как это сделать.

[Алексей К.]

Тему симметричности я всё же обсуждаю в рамках задачи с фиксированными концами и касательными на концах. Тогда у нас есть две степени свободы --- длина плеча $p=P_0P_1$, и длина плеча $q=P_2P_3$, которую я приравнял к $p$. Я, вообще-то никак не математик, таковым себя не позиционировал, Вашу, _hum_, нотацию про $\arg\ldots$ пока не понял, и мне, например, трудно писать слова "пространство параметров". Но почему-то мне кажется очевидным, что в пространстве параметров $(p,q)$ минимум любого разумного функционала будет достигаться при $p=q$. Да, мне действительно трудно подбирать правильные слова.

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

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

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

Теперь, что означает наше желание максимально приблизить интерполянт к окружности, т.е. к кривой постоянной кривизны $k$. Это, очевидно(!), означает, что график кривизны нашего интерполянта будет некой функцией, колеблющейся около $k$. (В реальности кубических кривых эти колебания довольно велики, кому-то могут показаться неожиданно огромными, с фактором типа 2 или 1/2 при дуге в 90 градусов, точно не помню). Хотелось бы получить график кривизны типа нужной нам константы, сложенной с чем-то типа синусоиды, дать синусоиде амплитуду поменьше, и чтобы колебаний побольше.

График кривизны того симметричного решения, пусть с совпадающей средней точкой, легко себе представить. Овевидно (да, очевидно), мы будем иметь вершину (минимум кривизны) на оси симметрии. На каждой половинке интерполянт касается окружности, и между точками касаниями без вершины не обойтись. По мне, очевидно, что с монотонной кривизной устроить переход от одного касания с окружностью к другому касанию невозможно. Но здесь я с очевидностями перебарщиваю.

(ссылка на доказательство)

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

Vogt W., Über monotongekrümmte Kurven, J. reine und angew. Math., 144, 1914, 239--248).

Установлено, что имеется три экстремума кривизны. А почему не 5? Анализ кривизны это допускает (там производная от кривизны имеет полином пятой степени в числителе). Но я почему-то давно вбил себе в голову, что кубическая кривая Безье имеет не более трёх экстремумов кривизны на всем своём протяжении, $t\in[-\infty,\+\infty]$ (реально когда-то давно проверил). И моя увернность в невозможности получить решение на порядок лучше основывалась на том, что при наших мизерных возможностях мы не в состоянии коренным образом исправить эту ситуацию с таким графиком кривизны. Мне не сможем получить ту "синусоиду" хотя бы с пятью экстремумами.

Только повышения порядка кривой позволит нам это сделать.

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

[_hum_]

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

нотацию про $\arg\ldots$ пока не понял,

см. wiki/Arg_max.
А насчет остального, попробую вникнуть, но, признаюсь, с первого прочтения ничегошеньки не понял :)

[Алексей К.]

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

Теперь, что означает наше желание максимально приблизить интерполянт к окружности, т.е. к кривой постоянной кривизны $k$. Это, очевидно(!), означает, что график кривизны нашего интерполянта будет некой функцией, колеблющейся около $k$.

Но это-то понятно? Очевидно?

[_hum_]

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

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

Теперь, что означает наше желание максимально приблизить интерполянт к окружности, т.е. к кривой постоянной кривизны $k$. Это, очевидно(!), означает, что график кривизны нашего интерполянта будет некой функцией, колеблющейся около $k$.

Но это-то понятно? Очевидно?

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

[Алексей К.]

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

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

Хорошая аппроксимация кривой (при любом разумном смысле критерия хорошести) с необходимостью имеет функцию кривизны, как бы колеблющуюся относительно функции кривизны аппроксимируемой кривой. И амплитуда колебаний, --- да, может быть довольно большой.

Я уже начал было писать, что на бОльшее я не способен ( в смысле объяснений), но гости набежали, и я переключился на любимое дело --- подавание вкусной еды приятным мне людям.
Кривизна --- локальная карактеристика, но я привлекал нечто более глобальное, график кривизны.

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

[_hum_]

Алексей К.

(Оффтоп)

Я не математик, просто тесно с этой областью пересекался :)

Я имел в виду следующие соображения: кривизна - величина, пропорциональная ускорению точки, траекторию движения которой мы рассматриваем в качестве кривой. Так вот ничто нам вроде бы не мешает сделать так, чтобы на очень малом отрезке времени ускорение было очень большим, а затем опять становилось прежним почти постоянным. Поскольку отрезок времени мал, то траектория точки не должна успеть значительно отклониться от своего положения. Ну и получается, что на графике функции кривизны мы видим выброс, а на деле траектория все равно хорошо аппроксимирует дугу окружности (и значит, требование малого колебания кривизны как бы необязательное для хорошей аппроксимации в смысле максимума относительного расстояния между кривыми).

[Алексей К.]

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

PDF-версия.

Хороший пример упомянутых колебаний --- на третьей странице этого файла. Там кривыми Безье интерполируется спираль Корню: кривизна --- линейная функция длины дуги. Остальные страницы, если интересно, обсуждаются в процитированной теме.

Ваше новое сообщение, о появлении которого меня сейчас известили, пока не изучил.

-- 12 сен 2013, 00:34:53 --

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

Я имел в виду следующие соображения: кривизна - величина, пропорциональная ускорению точки, траекторию движения которой мы рассматриваем в качестве кривой.

Я не умею мыслить в терминах ускорений, тем более после визита гостей (ну, понимаете, мы не только ужинали). Но, надеюсь, сумею в выходные. При этом, почти уверен, перепишу Ваше утверждение как-то так: "кривизна - величина, пропорциональная нормальному ускорению точки, движущейся по кривой равномерно (в смысле $ds/dt$, где $s$ --- длина дуги, т.е. в смысле отсутствия тангенциального ускорения; может и не так, но додумаю, соображу).

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

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

С этим я соглашался и без ускорений, и рассказывал, как неожиданно велики эли выбросы.

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

и значит, требование малого колебания кривизны как бы необязательное для хорошей аппроксимации

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

[_Ivana]

Ощущение, что все всё понимают, но почему-то консенсуса нет
Интересующимся могу предложить простейший эксперимент: берем один полупериод (шляпку) косинуса (для четности функции) и хотим ее аппроксимировать полиномом степени $n$ - по разным критериям, например по МНК, по условиям прохождения полинома через крайние точки и совпадение производных в них же плюс прохождение полинома через вершину и (возможно) равенство там производной нулю и т.п. И можно играться как угодно, хоть четности-симметричности не требовать, хоть вообще совпадения кривых где бы то ни было А потом качественно сравнить результаты различных способов аппроксимации при одном и при разных $n$. Мой скромный опыт во многом согласуется с мнением Алексей К.

[Алексей К.]

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

В день обращения, долго не могу заснуть из-за мысли, что не потяну я эту задачу, а так хочется...
........
Теперь сижу думаю, как это сделать.

Ответ я привёл целиком. Если Вы хотите его понять и получить решение самостоятельно, мы Вам охотно поможем. Это полезное упражнение. Но надо не картинки рисовать, а надо научиться формулы писать, по Правилам форума.

Вот, для начала, я там выше точки контрольные определил, $P_{0,1,2,3}$. Вам всё в этом понятно?