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

Question

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

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

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

Существуют ли хорошо известные алгоритмы для этого? Это работа для фильтра Калмана?

Answer 1

Существует алгоритм Рамера-Дугласа-Пекера (википедия).

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

Answer 2

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

Answer 3

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

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

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

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

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

Answer 4

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