аппроксимация_клотоидами

[kym]

Здравствуйте! Помогите, пожалуйста, разобраться!
Дано множество точек. В крайних точках даны углы наклона касательных (значения первых производных).Соединяем точки отрезками по кратчайшему расстоянию.
Задача:
Соединить точки отрезками клотоид в таком же порядке, как они соединяются отрезками по кратчайшему расстоянию. Клотоида должна строго проходить через точки без отклонения и должно соблюдаться условие равенство первой производной в точках соединения.

Какие будут предложения?

[Алексей К.]

Если под клотоидой понимается спираль Корню,

kym в сообщении #164591 писал(а):

и должно соблюдаться условие равенство первой производной в точках соединения

, если под этим понимается просто гладкость полученной составной кривой, то решений, на первый взгляд, бесконечно много.
Если дуга клотоиды выходит из точи $A=(-c,0)$ под углом $\alpha$ и имеет наклон $\beta$ в конечной точке $B=(c,0)$, то область углов, при которых решения нет, невелика. Например, нет решения при $\alpha=-\beta$ (или окружность надо считать частным случаем клотоиды). При этом $\mathrm{sign}\,(\alpha+\beta)=\mathrm{sign}\, k'$. Но и для этих углов её оычно можно построить, если допустить закручивание вокруг одной из конечных точек (чего Вы хотели бы наверняка избежать, но не упомянули об этом).
Так что, произвольно присваивая наклоны касательных в промежуточных точках, можно, поигравшись, найти кучу решений.

Концептуально несложная, утомительная для реализации (и даже для обсуждения) задача. Если дипломно-курсовая --- то сойдёт, а если по жизни, то надо подход менять. Так если Вам клотоиды нужны для монотонности кривизны, то соблюсти её в точках сопряжения будет непросто.

Добавлено спустя 46 минут 50 секунд:

(картинка делалась по другому поводу)


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

[kym]

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

Добавлено спустя 1 час 18 минут 39 секунд:

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

[Алексей К.]

kym в сообщении #164767 писал(а):

а можно тогда сделать минимизацию длины клотоиды?

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

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

[kym]

http://matlab.exponenta.ru/spline/book1/12.php#2 - вот по такому способу строились кубические сплайны. Единственное отличие - кубические уравнения - параметрические, т.е. x и y зависят от t, значения этого параметра - отношение сумм длин звеньев ломаной от начальной точки до данной точки к суммарной длине всех звеньев ломаной.

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

[Алексей К.]

kym в сообщении #164816 писал(а):

Природа задачи - просто построить кривую, максимально приближенную к имеющимся точкам,

Я имел в виду 2 основных (на мой взгляд) варианта:

(1) Ваша кривая есть график некой функции. $x$ типа время или напряжение или что угодно, $y$ типа деньги, расстояния, ток, или что угодно. Построение должно быть инварантно относительно изменения масштабов любой/обеих осей. Ни о каких поворотах речи нет. Длина хорды, кривизна --- (почти) бессмысленные величины. Привлечение клотоид, окружностных сплайнов --- бессмысленно.

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

Судя по Вашему уточнению, речь идёт о втором варианте, и "природа задачи" не сильно прояснилась (отправлено недописаным).

Добавлено спустя 1 минуту 21 секунду:

kym в сообщении #164591 писал(а):

Клотоида должна строго проходить через точки без отклонения

kym в сообщении #164816 писал(а):

просто построить кривую, максимально приближенную к имеющимся точкам,

Так строго или максимально приближенно?

Добавлено спустя 9 минут 43 секунды:

kym в сообщении #164816 писал(а):

плавное изменение кривизны

Плавное --- это как? Непрерывное? Монотонное?

kym в сообщении #164816 писал(а):

отсутствие изменения знака кривизны

А если расположение заданных точек императивно потребует изменить знак кривизны?

Всё выглядит несколько недодуманно..

[kym]

Да, второй вариант.

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

[Алексей К.]

kym в сообщении #164831 писал(а):

привязываемся к ошибкам измерений

Ну вот, "природа задачи" по крохам проясняется. Так шпион вылавливает крупицы информации...

Добавлено спустя 28 минут 3 секунды:

kym в сообщении #164591 писал(а):

В крайних точках даны углы наклона касательных (значения первых производных).

И здесь неясность. Как от заданного угла перешли к производным $x'_t, \:y'_t$?

[kym]

от заданного угла не переходили к производным. даны не значения производных отдельно, а соотношения $y'_t/\:x'_t$ в крайних точках

эти соотношения и есть угол наклона касательной

[Алексей К.]

kym в сообщении #164860 писал(а):

даны не значения производных отдельно, а соотношения $y'_t/x'_t$ в крайних точках

Теория (изложенная в приведённой Вами матлаб-ссылке), такого способа не предусматривает. Как-то реализованное, построение легко может оказаться неинвариантным относительньно поворотов. Особенно на $180^\circ$, когда производные должны чисто поменять знак, чего заданное отношение не учитывает.

[kym]

не прав я. точно - значения производных в крайних точках заданы...

но у нас речь про клотоиды. как их найти?

[Алексей К.]

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

Вас интегралы Френеля, которые ходят под ручку с клотоидой, не сильно смущают?

[kym]

сильно смущают. а какое по ним предложение?

[Алексей К.]

kym в сообщении #164890 писал(а):

не прав я. точно - значения производных в крайних точках заданы...

Всё же --- заданы как? Как от углов перешли к производным? Грамотно?

kym в сообщении #164890 писал(а):

но у нас речь про клотоиды. как их найти?

(1) Я могу представить задачу, в которой бы куб. сплайн не работал. Но недостаток информации о кривой компенсируют как-то не так, не клотоидизацией (вау!)...

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

(3) "Продумать" означает подобрать методику и критерии выбора промежуточных углов, сгондобить программу, варьирующую всё это... Выделить ту часть кода, которая потом, при переходе к клотоидам, изменится (типа $\verb). Но часть кода останется прежней.

(3а) В случе параболы (кривая Безье 2-го порядка) надо будет подбирать для каждой хорды ОДНУ контрольную точку. Т.е. построить ломаную с узлами в придуманных контрольных точках, такую, что заданные точки лежат на звеньях ломаной. (Лишь две крайние контрольные точки сразу не совсем свободны --- лежат на заданных прямых-касательных).

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

$$\begin{picture}(80,40)(0,-20) \put(20,0){\circle{40}} \put(60,0){\circle{40}} \put(0,0){\line(1,0){80}} \end{picture} $$

(4) Продумавши и до конца сделав упрощённую задачу, осмотреться: а может, хватит? И так всё ОК? Чего добавит клотоида кроме диких интегралов? Тем более, что у меня всё локально выпукло и кривизна знакопостоянна?

(5) Решив всё-таки вернуться к клотоидам, переписать курвозависимую часть кода. Интегралы Френеля Вам обеспечит и матлаб, и С++, и проч. В крайнем случае у меня есть код на PostScripte, которым я рисовал спиральки Корню на вышеприведённой картинке.

(6) Кажется, всё сказал, что знал и что удумал. Подозреваю, других советчиков (а здесь ходило много сплайнологов, я же со сплайнами мало имел дела) Вы отпугнули, замахнувшись на клотоиды... Может, правда, не надо?..

[kym]

Понятно. Спасибо большое!