Имейте в виду, что эта проблема растет экспоненциально с каждым добавляемым пользователем, так как количество вычислений расстояний связано с квадратом количества пользователей (на самом деле это N*(N-1) расстояний ... так что 2000 пользователей означаютпочти 4 миллиона вычислений расстояния на каждом проходе. Имейте это в виду при выборе необходимых вам ресурсов
Хотите ли вы сгруппировать их по прямому (на самом деле большому кругу) расстоянию или по пешеходной / дорожной дистанции??
Если первое, расстояние по большому кругу может быть аппроксимировано простой математикой, если вы можете допустить небольшой предел погрешности и хотите предположить, что земля - это сфера. Из GCMAP.com:
Гипотетическая форма Земли называется геоидом и аппроксимируется эллипсоидом или сплюснутым сфероидом. Более простая модель - использовать сферу, которая довольно близка и намного упрощает математику. Предполагая сферу радиуса6371,2 км, преобразовать долготу и широту в радианы (умножить на pi / 180) aЗатем используйте следующую формулу:
theta = lon2 - lon1
dist = acos(sin(lat1) × sin(lat2) + cos(lat1) × cos(lat2) × cos(theta))
if (dist < 0) dist = dist + pi
dist = dist × 6371.2
Полученное расстояние выражено в километрах.
Теперь, если вам нужны точные расчеты и вы готовы потратитьциклы процессора, необходимые для сложной математики, вы можете использовать формулы Винсенти, в которых используется эталонная эллипсоидная модель Земли WGS-84, которая используется для навигации, составления карт и тому подобного.Подробнее ЗДЕСЬ
Что касается самого алгоритма, вам необходимо построить матрицу to-from с результатом каждого вычисления.Каждая строка и столбец будут представлять каждый узел.Вы можете рассмотреть два упрощения:
- Расстояние не зависит от направления движения, поэтому
$dist[n][m] == $dist[m][n] (не нужно вычислять всю матрицу, только половину ее) - Расстояние отузел для себя всегда равен 0, так что нет необходимости вычислять его, но, поскольку вы собираетесь группировать по близости, чтобы избежать группирования пользователя с самим собой, вы можете захотеть всегда принудительно
$dist[m][m] принудительно определять произвольно и ненормальнобольшая константа (например, $dist[m][m] = 22000 (miles). Будет работать, пока все ваши пользователи находятся на планете)
После выполнения всех расчетов используйте метод сортировки массива, чтобы найти X ближайших узлов к каждомуузел и вот он у вас (вы можете или не хотите запретить группировку пользователей в более чем одну группу, но это просто бизнес-логика)
Фактический код будет слишком много, чтобы предоставить его в настоящее времяне видя вначале своего прогресса, но это в основном то, что вам нужно делать алгоритмически.