Алгоритмы для нормализации данных касания пальца (уменьшение количества точек)

Question

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

Сенсорный экран обеспечивает слишком много точек для загрузки через 3G. Даже небольшие регионы могут накапливаться до ~ 500 пунктов.

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

Есть ли какие-либо известные алгоритмы для этого? Эта работа для фильтра Калмана?

Answer 1

Существует Ramer–Douglas–Peucker algorithm (википедия).

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

Answer 2

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

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

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

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

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

Answer 3

Я собирался сделать что-то это приложение, но собирался на генерировании путь из точек на лету. Я собирался использовать технику, упомянутую в этой статье Point Sequence Interpolation thread

Answer 4

Вы хотите разделить поверхность на сетку с квадрантом или кривой заполнения пробела. Sfc уменьшает сложность 2d до сложности 1d. Вы хотите посмотреть на блог с пространственным индексом квадрантов кривой Гильберта Ника.