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

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

Но у этой победы быстро нашлась довольно неприятная цена.

Пока облака были обычными аннотациями, Mapbox сам понимал, куда тапнул пользователь. Есть вьюшка, есть хит-тест, есть делегат — нажал пальцем в облако, получил объект. Удобно.

А когда облако стало просто нарисованной картинкой внутри GL-слоя, для карты оно перестало существовать как интерактивный объект. На экране пользователь видит облако, а внутри у нас — просто набор точек и GPU-рендер. В момент тапа 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) }}

На маленьком количестве объектов это даже не выглядит проблемой: перебрали массив, посчитали расстояния, выбрали ближайшее. Проблема начинается не сразу. Она начинается, когда точек становится не сто, а несколько тысяч, и когда пользователь не просто один раз тапнул, а двигает карту, меняет зум, возвращается назад, снова двигает. В этот момент линейный перебор превращается в постоянную фоновую работу на главном потоке.

И ещё неприятный момент: расстояние между двумя CLLocationCoordinate2D — это не просто расстояние между двумя точками – sqrt(dx * dx + dy * dy). Координаты лежат на сфере, поэтому нормальный расчёт дистанции — это тригонометрия, а тригонометрические вычисления существенно дороже нам обходятся.

В общем, перебор всех облаков — это нормальный MVP, но плохая архитектура для живой карты.

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

QuadTree: режем карту на прямоугольники

Идея QuadTree довольно бытовая. Берём большой прямоугольник, в котором лежит весь мир. Начинаем складывать туда точки. Пока точек мало, храним их прямо в узле. Как только их стало слишком много — делим прямоугольник на четыре части и раскидываем точки по детям.

Получается дерево, где каждый узел отвечает за свой прямоугольный кусок пространства. Если нам потом нужны точки в каком-то прямоугольнике, мы не обязаны обходить всё дерево. Мы можем сразу отбросить ветки, которые с запросом вообще не пересекаются.

У меня порог разбиения — 10 точек на узел:

private let MaxItemsInSquare = 10func add(item: QuadItem) -> Node {    // если у узла уже есть дети — спускаемся в нужный квадрант    if !emptyChildren {        return addItemToChild(item)    }    // пока точек мало или квадрат уже слишком мелкий — храним точки здесь    if items.count < MaxItemsInSquare || rect.width < 10 || rect.height < 10 {        items.append(item)        return self    }    // точек стало слишком много — делим узел и переносим накопленные элементы в детей    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. Это не попытка заранее усложнить код «на всякий случай». Он реально пригодился позже, когда понадобилось искать облака не просто в прямоугольнике, а в кольце вокруг видимой области карты. До этого места ещё дойдём.

Сразу важная оговорка про сложность. В заголовке и в разговорной речи удобно говорить «O(log n)», но QuadTree не даёт магическое гарантированное O(log n) на любой набор точек и любой запрос. Если все точки лежат в одном месте или запрос покрывает половину карты, дерево не спасёт чудом, если все точки окажутся в одном месте – тысяча чатов на футбольном поле – мы, к сожалению, получим перебор за O(n).

Более честная формулировка такая: при нормальном распределении точек и небольшом прямоугольнике запроса QuadTree позволяет обойти маленькую часть дерева и обработать только найденных кандидатов. То есть вместо «каждый раз смотреть все n точек» мы смотрим только релевантные ветки плюс k найденных объектов. Для карты с тысячами облаков этого уже достаточно, чтобы разница была очень заметной.

Почему дерево не должно жить в latitude/longitude

Казалось бы, можно было положить в QuadTree сами координаты: широту и долготу. Вроде бы есть latitude, есть longitude, чем не двумерная плоскость?

Проблема в том, что это не плоскость. Один градус долготы у экватора и один градус долготы ближе к полюсу — это разное расстояние в метрах. Если делить такой «прямоугольник» пополам, дерево формально будет работать, но геометрически начнёт врать. Особенно неприятно это становится, когда радиусы тапа и видимые области завязаны на экранные пиксели.

Поэтому принято хранить точки в той же системе координат, в которой живёт сама карта, — в проекции сферического Меркатора.

func add(item: QuadItem) {    item.mapPoint = projection.point(for: item.coordinate)    ...}

То есть в дерево попадает не CLLocationCoordinate2D, а CGPoint в плоскости карты. Весь мир для дерева — это квадрат mWorldWidth × mWorldWidth. Его уже можно честно делить на четыре части, пересекать с прямоугольниками и использовать для быстрых spatial query.

Координаты остаются в объекте тоже, потому что они нужны для расчёта настоящей дистанции, но индекс строится именно по mapPoint.

Тап: палец в пикселях, облака в проекции, Земля круглая

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

Я хочу простую вещь: пользователь тапнул по карте, а я ищу облака примерно в радиусе 25 экранных пикселей от пальца. Не 25 метров, не 25 координатных единиц, а именно пикселей на экране — потому что UX должен ощущаться одинаково на разных зумах.

Но внутри всё устроено не так просто:

• палец даёт CLLocationCoordinate2D;

• дерево ищет по CGPoint в проекции карты;

• радиус задан в экранных пикселях;

• количество метров в одном пикселе зависит от зума и широты.

Поэтому путь получается такой:

1. берём координату тапа;

2. переводим её в точку дерева;

3. считаем, сколько метров сейчас занимает 25 пикселей;

4. сдвигаем координату тапа на это расстояние;

5. переводим сдвинутую координату в точку дерева;

6. получаем радиус поиска уже в единицах QuadTree.

В коде это выглядит так:

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)    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, если можно просто прибавить число к latitude

Вот здесь я сначала хотел сделать проще. Есть координата, есть расстояние в метрах, можно ведь как-нибудь прикинуть сдвиг по широте? Для маленьких расстояний оно даже иногда «примерно работает».

Но «примерно» в картах быстро превращается в странные баги: на одном зуме радиус тапа комфортный, на другом слишком маленький, в одном регионе нормально, в другом начинает ощущаться криво. Особенно когда поверх этого ещё есть проекция Меркатора.

Поэтому я использую честный 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)    )}

Там же живут computeHeading и distance через гаверсинус.

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

Какие облака показывать, если их всё равно слишком много

С поиском в области карты появилась другая проблема: допустим, мы быстро нашли все облака в текущем прямоугольнике. Что дальше?

Если их мало — рисуем все. Если их сотни или тысячи — рисовать ауру под каждым нельзя. Визуально это превращается в сплошное пятно, а смысл отдельных облаков теряется.

Первый вариант был ожидаемый: взять top-N по весу. То есть показать самые активные облака. Звучит логично, но на карте выглядело хуже, чем хотелось. Если в одной зоне есть несколько очень активных точек, они забирают весь лимит на себя. В итоге пользователь видит пару ярких мест, а остальная карта кажется пустой, хотя данные там есть.

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

Поэтому я сделал менее честный, но более приятный для UX отбор: беру часть самых тяжёлых, большую часть самых лёгких и немного из середины.

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 + bigfor i in 0..<middle {    result.append(items[offset + i])}

Да, это выглядит контринтуитивно: большая часть выбранных облаков — самые тихие. Но именно они обычно лучше распределены по экрану. В результате карта не выглядит так, будто жизнь есть только в двух перегретых местах.

Это тот случай, где «правильный» алгоритм по продуктовой метрике проигрывает алгоритму, который лучше смотрится глазами. Формально top-N честнее. Визуально 20/60/20 выглядит полезнее.

Заранее считать облака за краем экрана

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

Чтобы этого не было, я считаю две области:

let inside = topClouds(    in: visibleBounds,    max: 15)let outside = topClouds(    in: extendedBounds,    except: visibleBounds,    max: 100)

visibleBounds — то, что прямо сейчас на экране.
extendedBounds — область чуть больше экрана, с запасом по краям.

Внутри экрана я беру небольшой лимит, например 15 аур. Вокруг экрана — больше, например 100, чтобы при движении карты рядом уже были подготовленные кандидаты.

Вот тут и пригодился exceptRect в QuadTree. Мне нужно не просто «найти всё в большом прямоугольнике», а «найти всё в большом прямоугольнике, кроме маленького прямоугольника внутри». То есть фактически область-кольцо.

Можно было бы сначала найти всё в extendedBounds, а потом постфильтром удалить то, что попало в visibleBounds. Но раз у дерева уже есть информация о прямоугольниках узлов, оно может отбрасывать целые поддеревья, которые полностью лежат внутри исключённой области. Это мелкая оптимизация, но приятная: меньше объектов доходит до фильтрации.

Что в итоге получилось

Пока были аннотации, карта сама знала, куда пользователь нажал. Когда остался GL-слой, у тебя на экране красивая картинка, но для приложения это уже не набор объектов. Тап, радиус, попадание, ближайший элемент, выбор видимых объектов — всё приходится обрабатывать самостоятельно.

В моём случае связка получилась такая:

• QuadTree хранит облака в плоскости Меркатора и быстро отвечает на запросы по прямоугольникам;

• тап превращается в маленький spatial query вокруг пальца;

• сферическая геометрия помогает честно переводить пиксели, метры и координаты;

• дорогой distance считается только для небольшой пачки кандидатов;

• выбор аур делается не чистым top-N, а более «визуальным» 20/60/20;

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

Всё это началось с простой идеи: «давай перестанем рисовать тысячи UIView на карте». А дальше внезапно оказалось, что вместе с UIView мы выбросили и хит-тестинг, и готовую модель взаимодействия. Немного больше работы, но оно того стоило