Комментарии 16
Ну количество точек — то мы уменьшили, а как быть со скоростью обработки?
Увеличилось ли общее время обработки (предварительная обработка + время генерации для показа)?
Увеличилось ли общее время обработки (предварительная обработка + время генерации для показа)?
Время предварительной обработки 200-300 миллисекунд, а время отрисовки в JS пока не замерял.
Для ускорения есть — John Hershberger & Jack Snoeyink, «Speeding Up the Douglas-Peucker Line-Simplification Algorithm. А можно использовать другой способ упрощения — Сокращения Вершин. Если это кому-то интересно могу в следующей статьи написать.
Для ускорения есть — John Hershberger & Jack Snoeyink, «Speeding Up the Douglas-Peucker Line-Simplification Algorithm. А можно использовать другой способ упрощения — Сокращения Вершин. Если это кому-то интересно могу в следующей статьи написать.
Главное, что для клиентской стороны оно уменьшилось! Хотя алгоритм несложный, с учетом, что на сервере часть отрабатывается (бинарник с си++), то должен очень быстро просчитывать.
ЗЫЖ спасибо автору за тему, надо у себя будет применить )
ЗЫЖ спасибо автору за тему, надо у себя будет применить )
Просто сложность алгоритма O(N*log2(N)) (по предварительной прикидке), в то время как для отображения O(N).
P.S. в данном конкретном случае можно уменьшить общее число точек еще до применения алгоритма: просто удалить все точки, расстояние от которой до предыдущей менее 1 метра. Это может позволить убрать все точки, в которых мы «топтались» на месте, при этом детализация не упадет.
За счет такого «фильтра» можно местами значительно уменьшить общее количество точек, что значительно может повысить скорость работы основного алгоритма.
P.S. в данном конкретном случае можно уменьшить общее число точек еще до применения алгоритма: просто удалить все точки, расстояние от которой до предыдущей менее 1 метра. Это может позволить убрать все точки, в которых мы «топтались» на месте, при этом детализация не упадет.
За счет такого «фильтра» можно местами значительно уменьшить общее количество точек, что значительно может повысить скорость работы основного алгоритма.
Можно удалить все точки, которые лежат «почти» на прямой относительно двух соседей — время такой проверки O(1) для каждой точки (делаем в процессе получения данных). Для «путешествий» по городу — самое оно.
Алгоритм по этому принципу и работает (при этом сам определяет повороты и т.д.).
Думаю, клиентское ПО нет необходимости дорабатывать: сейчас можно получить и скорости, на которой двигался объект на участке.
Думаю, клиентское ПО нет необходимости дорабатывать: сейчас можно получить и скорости, на которой двигался объект на участке.
Что значит в процессе получения? Вы емеете ввиду при получает данные с GPS спутника — так я к этому отношения не имею.
На клиенте. Ему же надо что-то отправить на сервер, так вот перед этой отправкой происходит то, что можно назвать «процессом получения».
Хотя в более глобальном смысле мне не ясно, зачем гнать кучу данных на сервер (и «присылать громадный файл»), чтобы обратно получить часть этой же информации + карты (для получения которых достаточно было бы мизерного количества точек).
Хотя в более глобальном смысле мне не ясно, зачем гнать кучу данных на сервер (и «присылать громадный файл»), чтобы обратно получить часть этой же информации + карты (для получения которых достаточно было бы мизерного количества точек).
Очень клёвые для вашего ника рисунки :)
«все точко на сегменте»
креветко :)
креветко :)
Хочу стандартный тест с svg тигром (=
У алгоритма Дугласа-Пекера есть неприятный эффект: если его применять для упрощения контура полигона, то в результате мы можем получить контур с самопересечениями. Вот тут, например, есть описание улучшенного алгоритма, без этого недостатка: www.geovista.psu.edu/sites/geocomp99/Gc99/020/gc_020.htm
Искал решение ровно такой задачи, нужно было сделать регрессию большого количества измерений, иначе график не построить. Большое спасибо!
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Упрощение полилинии методом Дугласа-Пекера