Структура данных для хранения точек на карте

Question

[Артём]

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

Апдейты местоположения могут быть от 1 раза в секунду, до 1 раза в минуту. Количество объектов примерно 1000-1500, на карте видно обычно 5-7 только.

Какую структуру данных лучше использовать для хранения этих объектов чтобы быстро получать точки, которые ближе всего?

Сейчас всё хранится в обычном массиве, и при каждом обновлении местоположения обычным циклом прохожу все точки, вычисляю расстояние и азимут, сохраняю в объект и иду дальше.

Не уверен, что это самый оптимальный способ. Может, есть какие-то другие варианты? Думал сначала про очередь, но чем она лучше варианта с, например, более маленьким массивом, где будут хранится X точек на расстоянии Y?

Answer 1

[KEKSOV]

Что бы что-нибудь ускорить, нужно что-нибудь заранее посчитать и запомнить :) В Вашем случае необходимо сделать т.н. пространственную индексацию данных. Крупными блоками это выглядит следующим образом:

1. Определяем для себя географическую проекцию, в которой можно работать с картой. Например Меркатор, как у Гугла.
2. Зная проекцию, разбиваем карту на географическую сетку фиксированного размера, оптимальный размер определяем опытным путем, исходя из плотности точек и размера карты.
3. Для каждой точки заранее вычисляем индекс соответствующей ей ячейки сетки.
4. Для отрисовки точек вычисляем номера ячеек, которые видны на текущем экране (по координатам углов экрана с учетом текущего масштаба)
5. Имея список отображаемых ячеек, обрабатываем точки, находящиеся только в этих ячейках.

Да, и GDAL Вам в помощь…

Comments

[bay73]

Если плотность точек сильно неравномерна и требуется обеспечить их просмотр в разных масштабах (например, Сибирь хочется обозревать целиком, а Москву порайонно), то разбиение на области можно сделать адаптивным. Можно про k-d tree почитать.

Answer 2

[Лолшто]

В принципе, можно построить граф связей между точками, таким образом, что каждая точка будет связана только с ближайшими соседями. Пользователь находится ближе всего к некоторой вершине графа Р, считаем, что он привязан к ней. При каждом обновлении нужно проверить, не оказался ли пользователь ближе к какой нибудь из вершин графа, связанной с Р. В последнем случае, нужно изменить вершину привязки. Если связей между любой P и другими вершинами значительно меньше, чем число вершин, то обновлять приходится меньше.

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

А вообще, обновлять вектор из 1500 объектов раз в секунду — не такая сложная задача. Если не требуется экномия вычислительных ресусрсов (какое-нибудь встравиваемое оборудование или работа от аккумулятора), то я бы не стал заморачиваться.

Comments

[Артём]

С графом звучит немного сложновато. Ниже предложили способ, который, по-моему, довольно просто реализовать и использовать.

Answer 3

[Wataru]

Для вашей задачи подойдет и квадродерево: ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%...
Поиск ближайшей точки к заданной выполняется рекурсивным перебором с отсечениями (не стоит рассматривать квадрат, если он целиком дальше, чем имеющийся промежуточный ответ).
Поиск всех точек, которые надо вывести делается так же рекурсивно.

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