приближение последовательности точек на плоскости кривой

[PAV]

Привет всем,

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

Я решаю такую задачу. Имеется последовательность точек на плоскости (немного). Они более-менее укладываются на отрезок, соединяющий первую с последней. В некоторых случаях они лучше могли бы быть приближены некоторой кривой, что-то вроде окружности или эллипса, проходящего через первую и последнюю точки. Мне не очень важно конкретное семейство кривых, только хотелось бы, чтобы кривая сначала удалялась бы от отрезка, а затем обратно бы к нему возвращалась. Я могу попытаться приблизить точки окружностью, но хотелось бы что-то более общее, не обязательно симметричное. Может кто-нибудь посоветовать какое-нибудь достаточно простое решение? Дополнительное пожелание состоит в том, чтобы параметры могли бы быть вычислены за один проход по точкам. Типа насчитать какие-нибудь интегральные характеристики точек и затем все вычислить.

Заранее спасибо.

[photon]

PAV, выложите образец массива

[PAV]

Лучше я выложу картинку, только позже, сейчас технически не могу.

[ewert]

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

[PAV]

Вот пример для затравки, позже еще покажу несколько.



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

ewert, мне как раз модель и хочется придумать.

[photon]

я бы попробовал просто аппроксимацию полиномом

[Утундрий]

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

[PAV]

Вот еще несколько примеров.






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

[ewert]

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

[PAV]

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

Не пытайтесь найти здесь строгую законченную математическую постановку. Это прикладная задача с исходно нечеткой формулировкой.

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

Поясню, почему мне кажется, что сплайны не пойдут. Характер поведения кривой меняется, причем достаточно резко. Например, идет достаточно прямая линия - затем излом - затем прямая под другим углом. Глаз это видит, человек не станет сглаживать этот излом. А сплайн его уничтожит.

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

[ewert]

Так ведь, понимаете ли. Вот тут упоминался в частности эллипс.

Если этот эллипс далёк (в пределах расположения точек) от своих "острых" вершин -- то хоть это эллипс, хоть парабола -- аппроксимация примерно одинаково адекватной окажется.

Если же близок -- то надо проверить, насколько точки симметричны относительно соотв. "оси". И потом -- насколько они правильно "загибаются".

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

[PAV]

Они не обязаны ложиться на эллипс. Мне просто нужна одна или несколько несложных моделей. Я проверю их на моих данных.

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

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

[e2e4]

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

[PAV]

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

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

e2e4 в сообщении #195483 писал(а):

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

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

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

Уточню постановку. Будем считать, что концевые точки помещены в точки с координатами $(0,0)$ и $(1,0)$. Таким образом, хочется подобрать удобное для работы семейство кривых $y=y(x)$, таких что $y(0)=y(1)=0$.

Я думал над трехпараметрическим семейством вида $y(x)=cx^\alpha(1-x)^\beta$, где $\alpha>0$ и $\beta>0$. Фактически это один из частных случаев плотности бета-распределения. Но мне не нравится то, что производные в концевых точках равны либо $0$, либо $\infty$, за исключением вырожденного случая $\alpha=\beta=1$. А мне бы хотелось, чтобы производные на концах могли бы принимать произвольные значения.

Сейчас мне видится наилучшим с точки зрения содержания следующее 4-х параметрическое семейство. Каждая кривая склеена из двух, первый параметр $0<\gamma<1$ - точка склейки. Берем степенную кривую $y=x^\alpha$, $\alpha\ge1$, и дважды отражаем ее относительно горизонтальной и вертикальной осей, получая $y=1-(1-x)^\alpha$. И наконец сжимаем так, чтобы точке $\gamma$ соответствовала 1. Получаем $y(x)=1-\left(1-\frac{x}{\gamma}\right)^\alpha$ как аппроксимацию при $0\le x\le \gamma$. Аналогичным образом строим аппроксимацию при $\gamma\le x\le 1$ со своим показателем степени $\beta$. Последний параметр - это общий множитель $c$, на который все умножаем, получится $y(\gamma)=c$.

Это семейство мне нравится по всем своим свойствам. При $c=0$ получаем линейное приближение $y(x)=0$. При $\alpha=\beta=1$ имеем негладкую склейку двух линейных аппроксимаций. При $\alpha>1$ и $\beta>1$ имеем гладкую кривую. Производные на концах и кривизны каждой из двух частей могут быть произвольными.

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

[e2e4]

Вопрос в том, какую цель Вы преследуете, аппроксимируя набор точек кривыми? Какое минимальное кол-во точек должна содержать аппроксимирующая кривая, чтобы удовлетворять Вашим потребностям?

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