Тап по тысяче точек за O(log n): QuadTree и сферическая геометрия в гео-соцсети

vientooscuro4 часа назад

Тап по тысяче точек за O(log n): QuadTree и сферическая геометрия в гео-соцсети

Время на прочтение8 минОхват и читатели3.3KiOS*Swift*КейсИз песочницы9 лет назад я разрабатывал геолокационную соц.сеть на заказ, где мы отображали чаты на карте. До релиза не дошло, но интересного опыта было получено много. В очередной статье из серии рассказываю про то, как обрабатывать нажатия на MapBox и любой другой карте (Google, Yandex – не важно) и находить нужные объекты на ней, привязанные к координатам.

В прошлой части я рассказывал, как я отказался от UIView-аннотаций на карте и перенёс отрисовку облаков на GL-слои. С производительностью я тогда выиграл: FPS вырос, карта перестала тормозить от тысяч тестовых UIView, скролл и зум наконец-то стали плавными.

Но у этого решения обнаружилась неприятная обратная сторона.

Пока облака оставались обычными аннотациями, Mapbox «из коробки» понимал, куда именно нажал пользователь. С UIView работают методы hitTest и pointInside, соответственно. нажал – получил view от UIKit, а к ней привязанный объект

Как только облако превратилось в обычную картинку внутри MapBox-слоя, для карты оно перестало существовать как интерактивный элемент, так что теперь при тапе MapBox выдает только координату точки касания.

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

• Какие облака находятся в радиусе тапа
• Какие объекты попали в текущий экран
• Что находится сразу за границами экрана, чтобы при сдвиге карты элементы не появлялись из ниоткудаПо сути, всё это упирается в пространственный поиск.

Вариант «в лоб»: перебираем массив

Самое очевидное решение для обработки тапа выглядит так:

func cloud(at tap: CLLocationCoordinate2D) -> Cloud? {
return allClouds
.filter { $0.coordinate.distance(to: tap) < someRadius }
.min { $0.coordinate.distance(to: tap) < $1.coordinate.distance(to: tap) }
}Когда на карте живет сотня объектов, это работает. Пробежались по массиву, посчитали дистанцию, нашли минимум. Проблем нет, всё работает быстро.

Проблемы начинаются, когда база разрастается до нескольких тысяч точек, а пользователь активно двигает карту, меняет масштаб и спамит тапами. Линейный перебор за O(n) можно делать только в фоне, но пользователь будет получать всё равно результат с большой задержкой, даже если ничего не будет тормозить.

К тому же расстояние между точками CLLocationCoordinate2D — это не просто школьная формула sqrt(dx² + dy²). Наша планета — сфера, так что приходится возиться с тригонометрией. На единичных операциях это незаметно, но если гонять математические операции тысячу раз на каждое движение пользователем карты, упремся в потерю производительности, а юзер наш будет грустить :)

Стало понятно, что перебор — тупиковый путь. Нужен был пространственный индекс, позволяющий отсекать заведомо далекие участки мира. Для работы с двумерными координатами удобно использовать QuadTree.

Как устроен QuadTree

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

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

Я выставил лимит в 10 точек на один узел:

private let MaxItemsInSquare = 10

func add(item: QuadItem) -> Node {
// Если у узла уже есть дети — спускаемся глубже
if !emptyChildren {
return addItemToChild(item)
}

// Если лимит не превышен или прямоугольник стал слишком маленьким — сохраняем здесь
if items.count < MaxItemsInSquare || rect.width < 10 || rect.height < 10 {
items.append(item)
return self
}

// Лимит превышен: бьем узел на 4 части и переносим старые точки вниз
for existing in items {
addItemToChild(existing)
}

addItemToChild(item) items.removeAll()

return self
}Определить нужный квадрант для точки — дело двух проверок: выясняем, левее она или правее центра, и выше или ниже.

func quad(in rect: CGRect, for point: CGPoint) -> Int {
let x = point.x > rect.midX ? 1 : 0
let y = point.y > rect.midY ? 1 : 0

return 2 * y + x
}Для поиска объектов в заданной области рекурсивно обходим дерево:

func findItems(in rect: CGRect, exceptRect: CGRect = .zero) -> [QuadItem]? {
if exceptRect.contains(self.rect) {
return nil
}

if emptyChildren {
guard self.rect.intersects(rect) else {
return nil
}

return items.filter { rect.contains($0.mapPoint) && !exceptRect.contains($0.mapPoint) } }

return children
.compactMap { $0?.findItems(in: rect, exceptRect: exceptRect) }
.flatMap { $0 }
}Обратите внимание на параметр exceptRect. Он нужен для исключения определенной зоны из результатов поиска. Позже объясню, как это помогло нмнем при расчете объектов за пределами экрана. QuadTree хорошо тем, что в наиболее частом случае поиск у нас за O(log n). Если все точки на карте окажутся на одном стадионе, мы, конечно, получим O(n), так как получим просто связный список вместо дерева. Но при более-менее равномерном распределении объектов QuadTree спасает от необходимости перебирать тысячи точек, сужая выборку до нескольких десятков кандидатов.

Почему нельзя строить дерево на широте и долготе

Первое, что приходит в голову – закинуть в дерево напрямую latitude и longitude, но Земля не плоская, один градус долготы на экваторе по протяженности в метрах сильно отличается от градуса долготы где-нибудь под Мурманском. Если резать такую координатную сетку пополам, математика внутри дерева начнет разъезжаться, а радиусы тапов на карте будут визуально деформироваться в зависимости от удаления от экватора.

Чтобы избежать этого, мы переводим координаты в проекцию сферического Меркатора. Это та самая система, в которой MapBox и другие провайдеры карт рендерят карту.

func add(item: QuadItem) {
item.mapPoint = projection.point(for: item.coordinate)
...
}В дерево уходит обычный CGPoint. Весь мир для индекса превращается в стабильный прямоугольник — в частном случае квадрат — размером mWorldWidth × mWorldWidth. Его можно безболезненно делить, пересекать с экраном и использовать для расчетов. Сами CLLocationCoordinate2D мы сохраняем внутри объектов — они еще понадобятся для финального вычисления точных расстояний.

Обработка тапа: пиксели, проекции и кривизна Земли

Задача звучит просто: пользователь тапает по экрану, и нам нужно найти облака в радиусе, скажем, 25 пикселей от пальца. Именно пикселей, а не метров, чтобы чувствительность интерфейса не менялась при изменении масштаба.

Но под капотом данные постоянно конвертируются:

• Точка нажатия приходит в CLLocationCoordinate2D.
• Индекс ищет по CGPoint в Меркаторе.
• Радиус задан в экранных пикселях.
• Физический размер пикселя в метрах плавает в зависимости от текущего зума и широты.Алгоритм сбора данных получился следующим:

func items(at location: CLLocationCoordinate2D) -> [Cloud]? {
let point = quadTree.point(for: location)

// Выясняем, сколько метров в пикселе на данной широте
let mpp = CloodsUtils.metersPerPixel(at: location.latitude, zoom: currentZoom)
let maxMeters = 25 * mpp

// Сдвигаем координату на нужное расстояние в метрах
let offset = SphericalUtil.computeOffset(from: location, distance: maxMeters, heading: 0)
let offsetPoint = quadTree.point(for: offset)

// Считаем радиус в единицах проекции QuadTree
let r = max(abs(offsetPoint.y - point.y), abs(offsetPoint.x - point.x))

let searchRect = CGRect(x: point.x - r, y: point.y - r, width: 2 * r, height: 2 * r)

// Запрашиваем кандидатов у дерева и сортируем по реальной дистанции
return quadTree.findItems(in: searchRect)?
.sorted {
$0.coordinate.distance(to: location) < $1.coordinate.distance(to: location)
}
}Здесь есть компромисс: QuadTree ищет объекты не в круге, а в прямоугольной — квадратной — области вокруг точки тапа. Так банально быстрее. И уже эту отфильтрованную «кучку» кандидатов мы сортируем по точной тригонометрической формуле расстояния. Поскольку на этом этапе точек остается всего ничего, тяжелая геометрия не бьет по перформансу.

Зачем нужен computeOffset, если можно просто прибавить дельту к широте?

Проблема тут, что на одном зуме радиус кнопки кажется нормальным, на другом — схлопывается, а ближе к полюсам область клика начинает вести себя непредсказуемо., поэтому для смещения координат используется честный computeOffset. Код адаптирован из библиотеки Google Maps Android Utils. Он рассчитывает положение точки на сфере, зная исходную позицию, расстояние и азимут:

static func computeOffset(
from: CLLocationCoordinate2D,
distance: Double,
heading: Double
) -> CLLocationCoordinate2D {
let d = distance / EARTH_RADIUS
let h = toRadians(heading)
let fromLat = toRadians(from.latitude)

let sinLat = cos(d) * sin(fromLat) + sin(d) * cos(fromLat) * cos(h)

let dLng = atan2(
sin(d) * cos(fromLat) * sin(h),
cos(d) - sin(fromLat) * sinLat
)

return CLLocationCoordinate2DMake(
toDegrees(asin(sinLat)),
toDegrees(toRadians(from.longitude) + dLng)
)
}Этот расчет точен, но прогонять его через весь массив данных на каждый сдвиг карты слишком дорого. QuadTree как раз и решает эту проблему: мы используем “дорогую” математику только на узкой выборке объектов.

Фильтрация данных: боремся с визуальным шумом

Когда мы научились быстро собирать точки в текущей области видимости, возникла продуктовая задача. Если в видимую область попадают сотни облаков, подсвечивать их все нельзя – экран превратится в сплошное яркое пятно.

Первая мысль – отбирать топ-N по весу, то есть показывать только самые популярные или активные. Идея хороша в мире, где “богатые богатеют, а бедные беднеют”, так как чем больше активность у чата, тем больше шансов ему быть замеченным. При нескольких активных чатах все неактивные тут же теряются на их фоне.

Карта должна ощущаться «живой». Пользователю важен общий контекст активности в пространстве. Поэтому мы перешли на пропорциональную схему отбора объектов 20/60/20: берем немного самых тяжелых, чуть-чуть из середины и плотную пачку мелких точек, чтобы дать им тоже шанс выйти в топ.

items.sort { $0.weight > $1.weight }

let big = Int((0.2 * Double(maxCount)).rounded())
let middle = Int((0.2 * Double(maxCount)).rounded())
let small = maxCount - big - middle

// Самые активные for i in 0..<big { result.append(items[i]) }

// Самые тихие
for i in 0..<small {
result.append(items[items.count - 1 - i])
}

// Из середины списка
let offset = (items.count - big - middle) / 2 + big
for i in 0..<middle {
result.append(items[offset + i])
}Мы намеренно отдали приоритет middle-сегменту, так как за счет этого они равномерно распределяются по площади экрана, создавая ощущение заполненности мира, вместо того чтобы стягивать все внимание в пару ярких кластеров.

Работа на опережение: кэш за границами экрана

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

Чтобы сгладить этот эффект, мы делим область поиска на два контура:

let inside = topClouds(in: visibleBounds, max: 15)
let outside = topClouds(in: extendedBounds, except: visibleBounds, max: 100)• visibleBounds — то, что видит пользователь прямо сейчас.
• extendedBounds — буферная зона вокруг экрана.Для буферной зоны как раз и пригодился параметр exceptRect. Мы просим дерево: “Найди нам всё в большом прямоугольнике extendedBounds, исключая внутренний прямоугольник visibleBounds”. QuadTree отсекает ветки, целиком лежащие внутри экрана, избавляя нас от лишней пост-фильтрации элементов.

Все эти расчеты мы вынесли из главного потока в фоновую OperationQueue. Пользователь постоянно крутит карту, генерируя кучу жестов. Если повесить пространственные запросы на main thread, интерфейс гарантированно начнет собирать микрофризы.

Итоги

В итоге наша архитектура взаимодействия с картой выглядит так:

• QuadTree структурирует точки в проекции Меркатора и отвечает за быстрые выборки по регионам.
• Тап по экрану конвертируется в локальный поисковый запрос вокруг точки нажатия.
• Сферическая геометрия связывает пиксели интерфейса с реальными метрами на поверхности Земли.
• Тонкая фильтрация по правилу 20/60/20 спасает экран от визуальной перегрузки.
• Буферизация зон убирает резкие скачки графики при перемещении по карте.

Замечание:

QuadTree – не единственный способ связывать пиксели с координатами. Есть ещё как минимум два метода:

• хэширование Идея: вместо дерева с переменным разрешением — фиксированная сетка ячеек одного размера, и каждая точка кладётся в ячейку по простому хэшу координат:cellX = floor(x / cellSize)
cellY = floor(y / cellSize)
key = hash(cellX, cellY) // напр. cellX * 73856093 ^ cellY * 19349663
bucket[key].append(point)Вставка/поиск ячейки за O(1), без спуска по дереву. Точность по построению: если cellSize ≥ радиуса коллизии r, то любой объект ближе r гарантировано лежит в текущей ячейке или одной из 8 смежных. Минус – на сильно неравномерной плотности (пустой океан + плотный город) тратит память на пустые ключи и теряет преимущество над деревом для range-запросов общего вида. Но для моей задачи в целом это то, что нужно: дёшево, точно, тривиально параллелится.

• k-d дерево Представьте, что у вас много точек, и вы постоянно делите пространство пополам: сначала по x, потом по y, потом снова по x, и так далее. В каждом узле дерева хранится одна точка и правило: всё, что левее/ниже неё, идёт в одну ветку, всё, что правее/выше — в другую. Поэтому, когда нужно найти ближайшую точку или все точки в области, можно не проверять все точки подряд, а быстро отбрасывать целые куски пространства. То есть k-d дерево — это как аккуратно разложенная карта точек, где поиск идёт не “по всем”, а “только туда, где может быть ответ”. Для поиска ближайших точек в абстрактном пространстве k-d дерево часто удобнее, чем QuadTree.Теги:• MapBox
• QuadTree
• производительность
• поиск на картеХабы:• iOS
• Swift