Упрощение линии Android

Question

Я ищу советы по лучшей практике.

Я создал приложение (очень похожее на mytracks), которое собирает измерения GPS и отображает их на карте. Я хочу иметь возможность записывать данные GPS в течение 24 часов с интервалом 10 секунд. Это много данных, поэтому я не храню его в памяти, я храню его в SQLiteDB по мере его поступления. Внутри функций draw() я выбираю все и рисую его как объект Path.

Мой подход выше отлично работает до тех пор, пока у меня не будет данных за 4 часа. Затем выполняется функция draw для выполнения, что делает приложение очень медленным.

Я думаю, что мне нужно сделать, это нарисовать упрощенную траекторию на карте. Мой вопрос - лучший способ сделать это.

i) Процессор тяжелый: В draw() выберите все из SQLiteDB, постройте упрощенную траекторию, нарисуйте ее на карте.

ii) Память тяжелая: поддерживать упрощенную траекторию в памяти, обновлять ее по мере поступления новых данных, в draw() просто нарисовать ее на карте.

iii) Магия: используйте специальный специальный слой OverlayLay, о котором я не знаю, для чего упрощается упрощение линии.

С наилучшими пожеланиями, Cathal

Answer 1

Мои первые полу-случайные мысли:

1. Вы не говорите, что вы на самом деле сделать это, но делать не хранить один сэмпл на строка таблицы базы данных. 24 часа образцов с интервалом в 10 секунд, это 8640 образцов. Каждый образец имеет 2 удвоения, т. Е. 16 байт. В день стоимость данных составляет 135 КБ, сумма, которая может легко полностью вписываться в память. Вероятно, ваша стратегия базы данных должна позволить одной строке таблицы соответствовать одному периоду выборки, максимальная длина которой составляет один день. Излишне говорить, что данные образца должны быть в поле BLOB.

2. Рисование пути: это зависит от текущего увеличения карты и какой части набора образцов видно. Первое, что вы делаете, это повторить выборку пробной коллекции (макс. 8640) и определить подмножество, которое видно при текущем масштабировании. Это должно быть довольно быстрой операцией. Допустим, что для примера 5000 видны. Затем вы выбираете максимальное количество выборок для пути, основанное на предположениях h/w ... выбирая номер из тонкого воздуха, скажем, не более 500 выборок, используемых для пути (т. Е. Устройство не будет пытаться нарисовать путь с 500 очками). Поэтому вы строите путь, используя каждый 10-й образец (5000/500 = 10), и обязательно включайте первый и последний образец видимого набора.

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

Answer 2

Как ни странно, я просто смотрел на код, который я написал, чтобы сделать что-то подобное, около 5 лет назад.

Вот шаги, которые я прошел через:

• Simplify набор данные только видимые детали.Я разработал несколько сменных стратегий упрощения, но общий интерфейс для допусков и подачи/вывода точек для рендеринга. Подробнее о том, как его создать ниже.

• Кэш компактный, быстрый доступ к упрощенной версии списка точек доступа. Для больших наборов данных полезно использовать примитивы как можно больше, вместо объектов Point. С точными местоположениями double вам нужно 128 байт на точку или ~ 1,3 МБ памяти на 10 000.

• Render эффективно и без создания мусора. Итерация через int/float/double массивы координат x и y лучше всего, с жестким циклом рендеринга, который делает как можно больше вне цикла. Вы будете AMAZED, сколько очков вы можете отобразить сразу, если это просто «постройте этот путь».

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

Упрощение интерфейса: Там куча способов реализации этого. Самый лучший (для огромных наборов точек) - это подать его Iterator<Point> и позволить алгоритму упрощения работать с этим. Таким образом, точки не все должны быть в памяти, и вы можете подать их из запроса БД. Например, Iterator может обернуть JDBC ResultSet. Усилители также должны иметь значение «допуска», чтобы определить, насколько близки точки, прежде чем они будут проигнорированы.

Как упростить наброски/ломаные линии: Существует множество алгоритмов.

• Самый простой способ - удалить точки, которые меньше, чем $ допуск от последней включенной точки. Это реализация O (n).

• Алгоритм Douglas-Peucker обеспечивает превосходное упрощение многоугольника на большом узле. Слабость в том, что вам нужно работать с точками в памяти; используйте его по партиям, скажем, по 10 000 очков за раз. Выполняется в O (n log n) в среднем, O (n^2) наихудший случай

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

Дополнительные советы:

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

• Используйте свои примитивы. Серьезно, я не могу сказать этого достаточно. Если вы используете объекты для хранения памяти, 128 байтов/точек могут удвоиться, и увеличить использование памяти И он не может быть скомпилирован с таким оптимальным кодом.

Используя эти стратегии, можно произвести миллионы очков сразу (в уменьшенной форме). Если я правильно помню, я мог бы запускать процедуру упрощения в режиме реального времени, работая по 10k + points за раз, используя хороший код. Это могло быть 100k + points. Если вы можете сохранить хэш-таблицу с одним слотом на пиксель, реализация хэширования будет смехотворно быстрой (я знаю, это было мое самое быстрое решение)