2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

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

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4
 
 Re: Аппроксимация окружности кубической кривой Безье
Сообщение11.09.2013, 10:50 
Аватара пользователя


31/10/08
1244
_hum_
_hum_ в сообщении #762687 писал(а):
Я не спец.. но мне казалось, что выбор опорных точек в кубических кривых произволен (они никак не связаны друг с другом). Потому и непонятны ваши рассуждения, что "других вариантов и нет".

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

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

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

 Профиль  
                  
 
 Re: Аппроксимация окружности кубической кривой Безье
Сообщение11.09.2013, 11:27 


29/09/06
4552
Pavia в сообщении #762776 писал(а):
что-бы производные на концах кривой были равны производным на концах дуги

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

 Профиль  
                  
 
 Re: Аппроксимация окружности кубической кривой Безье
Сообщение11.09.2013, 13:41 


23/12/07
1757
Алексей К. в сообщении #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) опорные точки должны лежать на касательных к дуге, проходящих через ее начальную и конечные точки.

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

 Профиль  
                  
 
 Re: Аппроксимация окружности кубической кривой Безье
Сообщение11.09.2013, 14:39 


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

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

 Профиль  
                  
 
 Re: Аппроксимация окружности кубической кривой Безье
Сообщение11.09.2013, 18:27 


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

 Профиль  
                  
 
 Re: Аппроксимация окружности кубической кривой Безье
Сообщение11.09.2013, 19:15 


29/09/06
4552
Тему симметричности я всё же обсуждаю в рамках задачи с фиксированными концами и касательными на концах. Тогда у нас есть две степени свободы --- длина плеча $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]$ (реально когда-то давно проверил). И моя увернность в невозможности получить решение на порядок лучше основывалась на том, что при наших мизерных возможностях мы не в состоянии коренным образом исправить эту ситуацию с таким графиком кривизны. Мне не сможем получить ту "синусоиду" хотя бы с пятью экстремумами.

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

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

 Профиль  
                  
 
 Re: Аппроксимация окружности кубической кривой Безье
Сообщение11.09.2013, 19:27 


23/12/07
1757
Алексей К. в сообщении #762927 писал(а):
нотацию про $\arg\ldots$ пока не понял,

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

 Профиль  
                  
 
 Re: Аппроксимация окружности кубической кривой Безье
Сообщение11.09.2013, 19:37 


29/09/06
4552
Алексей К. в сообщении #762927 писал(а):
Теперь, что означает наше желание максимально приблизить интерполянт к окружности, т.е. к кривой постоянной кривизны $k$. Это, очевидно(!), означает, что график кривизны нашего интерполянта будет некой функцией, колеблющейся около $k$.
Но это-то понятно? Очевидно?

 Профиль  
                  
 
 Re: Аппроксимация окружности кубической кривой Безье
Сообщение11.09.2013, 19:59 


23/12/07
1757
Алексей К. в сообщении #762936 писал(а):
Алексей К. в сообщении #762927 писал(а):
Теперь, что означает наше желание максимально приблизить интерполянт к окружности, т.е. к кривой постоянной кривизны $k$. Это, очевидно(!), означает, что график кривизны нашего интерполянта будет некой функцией, колеблющейся около $k$.
Но это-то понятно? Очевидно?

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

 Профиль  
                  
 
 Re: Аппроксимация окружности кубической кривой Безье
Сообщение11.09.2013, 22:27 


29/09/06
4552
_hum_ в сообщении #762943 писал(а):
Что хорошая аппроксимация в смысле максимума относительного расстояния между кривыми должна с необходимостью иметь функцию кривизны, близкую к постоянной кривизне дуги?
Хорошая аппроксимация кривой (при любом разумном смысле критерия хорошести) с необходимостью имеет функцию кривизны, как бы колеблющуюся относительно функции кривизны аппроксимируемой кривой. И амплитуда колебаний, --- да, может быть довольно большой.

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

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

 Профиль  
                  
 
 Re: Аппроксимация окружности кубической кривой Безье
Сообщение11.09.2013, 22:50 


23/12/07
1757
Алексей К.

(Оффтоп)

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

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

 Профиль  
                  
 
 Re: Аппроксимация окружности кубической кривой Безье
Сообщение11.09.2013, 23:04 


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

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

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

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

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

_hum_ в сообщении #763025 писал(а):
и получается, что на графике функции кривизны мы видим выброс, а на деле траектория все равно хорошо аппроксимирует дугу окружности
С этим я соглашался и без ускорений, и рассказывал, как неожиданно велики эли выбросы.

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

 Профиль  
                  
 
 Re: Аппроксимация окружности кубической кривой Безье
Сообщение12.09.2013, 17:40 


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

 Профиль  
                  
 
 Про ТС совсем забыли.
Сообщение12.09.2013, 21:24 


29/09/06
4552
Dyx в сообщении #762920 писал(а):
В день обращения, долго не могу заснуть из-за мысли, что не потяну я эту задачу, а так хочется...
........
Теперь сижу думаю, как это сделать.
Ответ я привёл целиком. Если Вы хотите его понять и получить решение самостоятельно, мы Вам охотно поможем. Это полезное упражнение. Но надо не картинки рисовать, а надо научиться формулы писать, по Правилам форума.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 59 ]  На страницу Пред.  1, 2, 3, 4

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group