преобразование точек на карте в полигоны

Question

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

Есть ли хорошие быстрые алгоритмы для такой вещи?

Answer 1

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

Если человек перемещается в какой-либо области (например, водитель доставки, покрывающий часть города), то вы можете приблизить его «покрытую область» выпуклой оболочкой точек. Это замкнутый выпуклый многоугольник с где-то между 3 и N углами, если у вас есть N точек в наборе данных.

Определение

http://mathworld.wolfram.com/ConvexHull.html

Алгоритмы

http://en.wikipedia.org/wiki/Convex_hull_algorithms

Если вы хотите сделать аппроксимацию пути , а не какой-либо покрытой области , вы всегда можете сделать грубый алгоритм LOD, скажем, рисуя каждые 7 точек, затем каждый 5, затем каждые 3 балла, когда пользователь увеличивает масштаб дальше. Более сложный алгоритм LOD может начинаться с точек p0 и p1, использовать направление через эти точки и смотреть на расстояние от линии направления до p2. Если p2 достаточно близко к линии, она пропускается, и p3 исследуется. Если изменение направления движения достаточно велико, отметьте последние две точки как текущий курс и повторите. Допустимым изменением направления будет параметр LOD, определяющий, сколько точек нарисовано. Этот алгоритм будет пытаться аппроксимировать «важные» точки на пути (где меняется направление).

Answer 2

Для кластеризованных точек вы можете использовать шестигранный слой gls колоды, из документов -> Слой шестиугольника отображает тепловую карту шестиугольника на основе массива точек.Он принимает радиус шестиугольной корзины, проецирует точки в шестиугольные корзины.Цвет и высота шестиугольника масштабируются по количеству точек, которые он содержит.

https://github.com/uber/deck.gl/blob/master/docs/layers/hexagon-layer.md

очень крутой пример этого -> http://deck.gl/#/examples/core-layers/hexagon-layer

Answer 3

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