Ближайший объект и объекты в радиусе

Урок реализует на чистом Python два запроса-рабочие-лошадки геоанализа: «ближайший объект» и «все объекты в радиусе».

Запрос ближайшего соседа ищет объект с минимальным расстоянием до заданной точки; запрос в радиусе возвращает все объекты ближе заданного порога.

«Где ближайшая заправка?», «Сколько аптек в 1 км от дома?», «Какие города в радиусе 500 км?» — это два базовых пространственных запроса, на которых стоит половина геосервисов. Имея корректную функцию расстояния (гаверсинус из раздела 4), оба реализуются в несколько строк.

Ближайший сосед

Прямолинейно: посчитать расстояние до каждого кандидата и взять минимум. В Python это одна функция min с ключом:

import math

def haversine(lat1, lon1, lat2, lon2):
    R = 6371.0
    p1, p2 = math.radians(lat1), math.radians(lat2)
    dphi = math.radians(lat2 - lat1)
    dlam = math.radians(lon2 - lon1)
    a = (math.sin(dphi / 2) ** 2
         + math.cos(p1) * math.cos(p2) * math.sin(dlam / 2) ** 2)
    return 2 * R * math.asin(math.sqrt(a))

cities = {
    "Казань": (55.7963, 49.1088),
    "Самара": (53.1959, 50.1002),
    "Уфа":    (54.7388, 55.9721),
    "Тула":   (54.2044, 37.6184),
}
me = (55.7558, 37.6173)  # Москва

nearest = min(cities, key=lambda c: haversine(*me, *cities[c]))
dist = haversine(*me, *cities[nearest])
print(f"Ближайший город: {nearest} ({dist:.0f} км)")

Вывод:

Ближайший город: Тула (173 км)

Объекты в радиусе

Здесь фильтруем по порогу и заодно сортируем по близости:

import math

def haversine(lat1, lon1, lat2, lon2):
    R = 6371.0
    p1, p2 = math.radians(lat1), math.radians(lat2)
    dphi = math.radians(lat2 - lat1)
    dlam = math.radians(lon2 - lon1)
    a = (math.sin(dphi / 2) ** 2
         + math.cos(p1) * math.cos(p2) * math.sin(dlam / 2) ** 2)
    return 2 * R * math.asin(math.sqrt(a))

cities = {
    "Казань": (55.7963, 49.1088),
    "Самара": (53.1959, 50.1002),
    "Уфа":    (54.7388, 55.9721),
    "Тула":   (54.2044, 37.6184),
}
me = (55.7558, 37.6173)  # Москва

def within_radius(me, points, radius_km):
    result = []
    for name, (lat, lon) in points.items():
        d = haversine(me[0], me[1], lat, lon)
        if d <= radius_km:
            result.append((name, d))
    result.sort(key=lambda t: t[1])
    return result

for name, d in within_radius(me, cities, 750):
    print(f"{name}: {d:.0f} км")

Вывод:

Тула: 173 км
Казань: 718 км

В радиус 750 км попали Тула и Казань; Самара и Уфа дальше и отсеялись.

Как работает под капотом

Наивный перебор стоит $O(n)$ на запрос — нормально для сотен объектов, но катастрофа для миллионов точек и тысяч запросов. Тогда строят пространственный индекс: R-дерево или k-d-дерево раскладывает объекты по вложенным прямоугольникам, и поиск ближайшего идёт за $O(\log n)$ — алгоритм спускается только в перспективные ветви. Есть и хитрость для радиуса: дорогую гаверсинус-проверку запускают лишь для объектов, чей bounding box пересекает квадрат радиуса вокруг точки. Сначала грубый прямоугольный отсев, потом точное расстояние — этот двухступенчатый приём пронизывает всю производительную ГИС.

Тонкость с «квадратом радиуса»: чтобы перевести радиус в км в градусы для грубого фильтра, по широте делят на $111$ (км в градусе широты примерно постоянны), а по долготе — на $111\cos\phi$, потому что меридианы сходятся к полюсам.

Частые ошибки

Сравнивать евклидово расстояние в градусах. Для радиуса нужен честный гаверсинус, иначе порог «плывёт» с широтой.
Перебирать миллионы объектов в лоб. Без индекса запросы становятся неприемлемо медленными.
Считать радиус по долготе так же, как по широте. Градус долготы короче градуса широты во всех широтах, кроме экватора.

От запроса к сервису

За простыми на вид запросами «ближайший» и «в радиусе» стоит вся индустрия геосервисов. Доставка еды каждую секунду решает «ближайший свободный курьер к заказу»; каршеринг — «ближайшая машина к пользователю»; экстренные службы — «ближайшая бригада к вызову». Масштаб меняет всё: когда курьеров десятки тысяч, а заказов сотни в секунду, наивный перебор физически не успевает, и без пространственного индекса сервис просто ляжет под нагрузкой. Именно поэтому понимание разницы между $O(n)$ и $O(\log n)$ здесь не теория, а вопрос работоспособности продукта.

Есть и содержательная тонкость: «ближайший по прямой» не равно «ближайший по дороге». Заправка через реку может быть в 200 метрах по воздуху, но в пяти километрах по ближайшему мосту. Для честного ответа гаверсинус заменяют расстоянием по дорожному графу (маршрутизация из следующего раздела), а гаверсинус оставляют как быстрый предварительный фильтр: сначала отбирают кандидатов по прямой в широком радиусе, и только для них считают дорогой маршрут. Эта двухступенчатость — «грубо и быстро, затем точно и дорого» — повторяет ту же идею, что и bounding box перед точной геометрией, и пронизывает всю производительную геоинформатику.

Итог

Ближайший сосед — минимум функции расстояния; в радиусе — фильтр по порогу.
Расстояния считают гаверсинусом, а не евклидом в градусах.
Наивный перебор $O(n)$; пространственный индекс даёт $O(\log n)$.
Двухступенчатость: грубый bounding-box-отсев, затем точное расстояние.