Сортировать POI по расстоянию от текущего местоположения
Trover - это замечательное приложение: оно показывает вам поток открытий (POI), которые люди загрузили - отсортированные по расстоянию от любого местоположения, которое вы укажете (обычно ваше текущее местоположение). Чем дальше вы прокручиваете канал, тем дальше отображаются отображаемые открытия. Индикатор достаточно точно показывает, насколько далеко находятся показанные в настоящее время открытия (см. Скриншоты на веб-сайте).
Это отличается от большинства других приложений на основе определения местоположения, которые предоставляют свои результаты (POI) на основе фиксированных областей (например, дают мне все пиццерии с радиусом 10 км), которые могут быть реализованы с использованием одной пространственной структуры данных (или механизма SQL, поддерживающего пространственные типы данных)., Доставка результатов, как это делает Trover, значительно сложнее:
Вы можете запросить POI для произвольных местоположений. Дайте Trover место на Дальнем Востоке России, и оно доставит открытия, где первое находится в 2000 км и непрерывно увеличивается оттуда.
Список результатов POI не ограничен некоторым пространственным диапазоном. Если вы прокручиваете ленту достаточно долго, вы, вероятно, увидите открытия, которые находятся на другой стороне земного шара.
Вышеупомянутые пункты требуют полужесткого заказа их POI для любого местоположения. Тот факт, что вы можете прокрутить вниз и перезагрузить больше открытий, подразумевает, что они могут доставлять определенные разделы отсортированных данных (например, дать мне следующие 20 открытий, которые находятся по крайней мере в 100 км от моего текущего местоположения).
Это быстро, индикация получения и расстояния мгновенная. Открытия должны быть предварительно отсортированы. Я не знаю, сколько открытий у них есть в их БД, но это должно быть больше, чем то, что вы хотите отсортировать ad hoc.
Я нахожу эти характеристики весьма замечательными и удивляюсь, как это реализовано. Любые предложения, какие структуры данных, алгоритмы или кэширование могут быть использованы?
1 ответ
Я не понимаю вопрос. На что хотите получить ответ?
Редактировать: они могут использовать базу данных графа, где один край представляет расстояние между узлами. Таким образом, вы можете получить расстояние по отношениям соседних POI. Вы бы рассчитали расстояние и создали ребра для соседних узлов. Чтобы получить расстояние от произвольной точки, вы просто производите вычисление расстояния по кругу, для другого узла вы просто складываете значение ребер, поскольку они представляют расстояние (это в случае получения расчета ходьбы, езды на велосипеде или автомобиля). Суммирование, возможно, не самый близкий путь, но даст относительную индикацию, которую, кажется, они используют.