Реализация функции "Найти близлежащих пользователей" на сервере

Question

Предположим, у меня есть база данных, хранящая 1000000 геолокаций разных пользователей в городе. Было бы больно, если сервер выполнит команду SearchNearbyUsers(myLocation, 50), если я использую список или массив для хранения всех геолокаций и сравнения расстояний один за другим.

Сервер закодирован на C# с веб-интерфейсом API 2. Есть ли библиотека, предназначенная для таких расчетов с геолокациями?

Если библиотеки нет, какую структуру данных следует использовать, чтобы сделать этот расчет проще? Раньше я смотрел на R-tree, но, честно говоря, я не понимаю логику, и это кажется довольно сложным.

Это то, что класс геолокации выглядит следующим образом:

public class GeoLocation 
{ 
    public float latitude { get; set; } 
    public float longitude { get; set; } 
} 

И широта и долготы направляются клиентами. Значения получены через navigator.geolocation.getCurrentPosition().

Answer 1

Обычно эти пространственные операции выполняются с использованием пространственных индексов. R-Tress - всего лишь один из примеров этого, но вы также можете получить более простые. Просто разделите всю область на более мелкие части (например, прямоугольники) и выполните поиск в тех областях, которые соответствуют общему индексу с заданной координатой. Поэтому я предлагаю включить пространственные индексы на ваш сервер, а затем использовать пространственную библиотеку, такую ​​как GDAL.

Итак, если у вас есть координата (4,5), вы сначала посмотрите на все прямоугольники, пересекающие буфер witdh x вокруг вашей точки. И теперь вы просто выполняете поиск по всем геометриям, расположенным внутри этих прямоугольников.

EDIT: На SQL Server вы также можете использовать его пространственное расширение для извлечения тех близлежащих функций (см. here). В основном создайте буфер вокруг вашей геометрии ввода, используя STBuffer, а затем выполните пересечение в этом буфере. Используя описанный пространственный индекс, эти операции выполняются довольно быстро.

Answer 2

Если вы используете хранилище данных, такое как Mongo, геопространственные запросы довольно просты и довольно приятны. Вот Docs

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

EDIT Для нахождения местоположения в реальном мире с Lat и Long, чтобы получить правильный результат при запросе с расстоянием, вы должны использовать сферический индекс

This Question помогут Вам с рядом запросов, используя mongo C# driver.

Редактировать 2 Узнав о вас, используя MS SQL, ознакомьтесь с некоторыми полезными ссылками, чтобы перейти к одному Phillip, предоставленному в другом ответе.

Query Spatial Data For Nearest Neighbour
Spatial Data

Answer 3

Ну, если вы храните ваши данные в SQL Server вы хотите использовать пространственный индекс http://msdn.microsoft.com/en-us/library/bb934196.aspx.

Answer 4

Если вы новичок и хотите избежать использования деревьев ...

1. создать карту сеточного поддерживаемома области

   • только простая сетка 2D клеток
   • 
   • каждую ячейка имеет свои координаты i,j или индекс ix=i+j*ni где п есть число клеток на i ось
   • поэтому для каждой точки вы можете просто вычислить право собственности на ячейку
   • составить список точек в каждой ячейке
   • что-то вроде:
   • Vector<int> map[nj][ni];
   • и заполнить список с индексом точки внутри клетки ...

2. сравнения

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