Алгоритм сглаживания дуг - нужна помощь

[Гармонист]

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

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

цитата отсюда

поэтому подумал решить проблему сглаживания ж-кода и уменьшение кол-ва сегментов
опять же на основании работ Xunnian Yang (а так же Guozhao Wang)
1. Planar point set fairing and fitting by arc splines (2000)
Аппроксимация и сглаживание набора точек на плоскости - дуговыми сплайнами.
Используется формула подсчета минимальной энергии деформации кривой и алгоритм фильтрации нижних частот...

Fairing the disturbed points sampled from a Bezier curve:
(a) the fitting arc spline within tolerance 0.04;
(b) circle curvature plots before (uniform dash) and after (non-uniform dash) fairing and curvature plot for arc spline (solid) by the circle-based method;
(c) circle curvature plot after fairing (non-uniform dash) and curvature plots of fitting arc splines before (uniform dash) and after (solid) fairing by the arc-based method

2. Efficient circular arc interpolation based on active tolerance control (2001)
Аппроксимация дугами - набора точек, контролирую "активную" погрешность.
Вот так это выглядит:

Xunnian Yang сглаживание набора точек используя "активную" погрешность

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

или использую работу Hyungjun Park(спасибо Nike-у ):
3. Optimal Single Biarc Fitting and its Applications

Hyungjun Park approximating

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

[michael-yurov]

У меня фильтр похож на фильтр нижних частот.
Получилось, что на перемещения с равномерным ускорением и замедлением фильтр практически не оказывает влияния, а если ему скормить ломаную траекторию с резкими изменениями вектора направления и не останавливаться с замедлением/ускорннием в вершинах - он ее сделает плавной.

[Гармонист]

к теме имеет опосредованное отношение, но все же:
нарисовал напоминалку

Геометрический способ построения биарки по 2м точкам, 2м касатальным в этих точках
и 3ей опорной точке, лежащей на одной из окружностей биарки

1. этот способ используется при аппроксимации набора точек - биарками

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

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

[verser]

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

вот для него тело цикла итераций

Код: Выделить всё

	// sum of first 4 samples , PIR_BUFF_SIZE_4B = 4
	sum0 += new_value;
	sum0 -= buff0[ix % PIR_BUFF_SIZE_4B];
	// following sum of next 4 samples 
	sum1 += buff0[ix % PIR_BUFF_SIZE_4B];
	sum1 -= buff1[ix % PIR_BUFF_SIZE_4B];
	buff1[ix % PIR_BUFF_SIZE_4B] = buff0[ix % PIR_BUFF_SIZE_4B];
	buff0[ix % PIR_BUFF_SIZE_4B] = new_value;
	// differention between two following sums
	if(sum0 > sum1)
	diff = (Word)(sum0 - sum1);
	else
	diff = (Word)(sum1 - sum0);
	ix++;

[Гармонист]

Если я правильно понял, нужно сгладить "пляшущие точки".

все верно. Но не только отдельные точки, а целые группы(рядомстоящих) точек.

очень эффективный фильтр для похожей цели

ты забыл указать что источник взять отсюда

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

не нашел
в таксте сказано

Filtration of the signal from the PIR sensor is a necessary condition for the correct detection of movement. The most
important feature of the filtration is the removal of spurious signals (peaks and noise).
The first element of the motion filtration is the use of two four-byte buffers for continuously saving the data in a one-second time range. The next step creates moving averages by using the two sums of the values stored in in each buffer and calculating the difference between these sums. This calculated value is compared with the static threshold which corresponds to the maximum output noise from the PIR sensor.

Перевод

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

т.е. фильтр работает как скользящие средние
Скользящие средние подразумевают "дофига" вычислений - и как следствие медленную работу. У меня картинка 1000 на 4000 точек...

Хотелось бы все же разобраться с алгоритмами Янга - тк он оптимизирует уже посроенные биарки(биарки строит скрипт authors.py - использует алгоритм Дугласс-Пэккера - в котором уже присутствует фильтр нижних частот)