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

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

Когда облака были аннотациями, у каждого была вьюшка, и на тап работал viewFor-делегат: пользователь попал пальцем во вьюшку – карта сама сказала, в какую. Как только мы убрали аннотации и оставили облака просто данными в GL-слое, карта больше не знает, на что ты тапнул. У неё на экране – нарисованная средствами GPU картинка, а не объекты. На тап она отдаёт тебе только координату пальца. Дальше – твои проблемы.

Тут же вылезает вторая проблема того же сорта: из всех облаков в области надо выбрать те, что вообще стоит показать (рисовать ауру под каждым из тысячи – это снова каша). Оба вопроса – «на какое облако я попал» и «какие показать» – это пространственные запросы. И оба нельзя решать перебором.

Наивно: перебрать все

Самое прямое решение тапа:

func cloud(at tap: CLLocationCoordinate2D) -> Cloud? {    allClouds.lazy        .filter { $0.coordinate.distance(to: tap) < someRadius }        .min { $0.coordinate.distance(to: tap) < $1.coordinate.distance(to: tap) }}

Работает. Пока облаков сотни. Но:

• это O(n) на каждый тап и на каждое обновление видимой области;

• distance между координатами – это не вычитание, а тригонометрия (про неё ниже), то есть каждый из n шагов ещё и недешёвый;

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

На тысячах точек и при активном панорамировании это превращается в постоянную нагрузку на главный поток. Нужен пространственный индекс, который отвечает на «дай объекты в этом прямоугольнике» за O(log n), а не за O(n). Классический выбор для точек на плоскости – QuadTree.

QuadTree: рекурсивно делим пространство на четыре

Идея дерева простая. Есть квадрат – весь мир. Кладём в него точки. Как только в узле накопилось больше порога – узел делится на 4 равных квадранта, и точки расходятся по детям. Поиск «кто в этом прямоугольнике» спускается только в те ветки, что пересекаются с запросом, и не трогает остальные.

Порог разбиения у меня – 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   // 0..3 – северо-запад / северо-восток / юго-запад / юго-восток}

А поиск отсекает целые поддеревья, которые не пересекаются с запросом:

func findItems(in rect: CGRect, exceptRect: CGRect = .zero) -> [QuadItem]? {    if exceptRect.contains(rect) { return nil }          // вся ветка внутри исключения – пропускаем    if emptyChildren {                                    // лист – фильтруем его точки        return self.rect.intersects(rect)            ? items.filter { rect.contains($0.mapPoint) && !exceptRect.contains($0.mapPoint) }            : nil    }    return children.compactMap { $0?.findItems(in: rect, exceptRect: exceptRect) }.flatMap { $0 }}

Обратите внимание на exceptRect – про него ещё пойдёт речь ниже, это не просто украшение.

Важная деталь: дерево живёт не в широте/долготе

Соблазнительно строить QuadTree прямо в координатах (latitude, longitude). Так делать нельзя: градус долготы у экватора и у полюса – это разное количество метров, прямоугольники получаются кривыми, деление пополам врёт. Поэтому точки в дерево кладутся не как координаты, а как точки на плоскости сферического меркатора (та же проекция, в которой нарисована сама карта):

func add(item: QuadItem) {    item.mapPoint = projection.point(for: item.coordinate)  // lat/lng → плоскость Меркатора    ...}

Весь мир – это квадрат mWorldWidth × mWorldWidth в пикселях проекции, и дерево делит именно его. Тогда «разделить квадрат пополам» – честная операция, а прямоугольные запросы соответствуют прямоугольникам на экране.

Тап как пространственный запрос (где вылезает геометрия)

Теперь собственно тап. Палец дал координату. Я хочу: «верни облака в пределах ~25 пикселей от пальца, ближайшее первым». Звучит просто, но смотрите, сколько здесь стыков систем координат:

• дерево живёт в метрической проекции;

• «25 пикселей» – это экранные пиксели, и сколько это метров на местности, зависит от зума и широты;

• значит, надо: 25 px → метры → сдвинуть координату пальца на это расстояние → перевести в плоскость дерева → получить размер квадрата поиска.

Вот как это выглядит в коде (тот самый metersPerPixel – из прошлой части):

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                                        // 25 экранных пикселей → метры    // сдвигаем координату пальца на maxMeters на север и смотрим, на сколько    // это сдвинуло точку в плоскости дерева – это и есть радиус поиска в её единицах    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) }}

То есть «попадание по облаку» – это не перебор всех точек, а один спуск по дереву в маленький квадрат вокруг пальца, плюс сортировка горстки кандидатов по реальной дистанции. На тысячах облаков тап остаётся мгновенным.

Сферическая геометрия: почему computeOffset, а не «прибавить метры к координате»

В коде выше мелькнул SphericalUtil.computeOffset – «сдвинуть координату на N метров в направлении heading». Нельзя просто прибавить метры к широте: Земля – не плоскость, и у долготы цена в метрах зависит от широты. Поэтому я портировал в Swift кусок геометрии из Google Maps Android Utils – честную сферическую тригонометрию:

static func computeOffset(from: CLLocationCoordinate2D, distance: Double, heading: Double) -> CLLocationCoordinate2D {    let d = distance / EARTH_RADIUS          // EARTH_RADIUS = 6 371 009 м    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 (азимут из точки A в точку B) и сам distance между координатами через гаверсинус. Это та самая «недешёвая тригонометрия», ради которой и нужен был QuadTree: чтобы считать её для горстки кандидатов, а не для всех точек подряд.

Вторая задача: какие облака вообще показать

Найти объекты в области – полдела. Если их там тысяча, рисовать ауру под каждой нельзя: получится сплошное свечение. Нужно выбрать ограниченный «топ». Наивно – взять N самых «тяжёлых» (активных) облаков. Но тогда ауры скучкуются в паре горячих точек, а остальная карта останется голой.

Поэтому отбор устроен хитрее. Кандидаты сортируются по весу, и из них набираются три группы: 20% – самые тяжёлые, 60% – самые лёгкие, и 20% – из середины:

items.sort { $0.weight > $1.weight }let big    = Int((0.2 * Double(maxCount)).rounded())   // 20% с головы – самые активныеlet middle = Int((0.2 * Double(maxCount)).rounded())   // 20% из серединыlet small  = maxCount - big - middle                   // остальные 60% – с хвоста, самые тихие// самые большие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) даёт хуже UX, чем намеренно «нечестный».

Подгрузка за краем экрана и трюк с «кольцом»

Чтобы при панорамировании ауры не выскакивали рывком из-за края, я считаю их не только для видимой области, но и для расширенной – с запасом вокруг вьюпорта:

let inside  = topClouds(in: visibleBounds,  max: 15)    // в кадре – 15 аурlet outside = topClouds(in: extendedBounds,  except: visibleBounds, max: 100)  // в кольце вокруг – ещё 100

Здесь и пригодился exceptRect в findItems: «облака в расширенной области, кроме уже посчитанных в видимой» – это запрос по кольцу (большой прямоугольник минус внутренний). Дерево просто отбрасывает поддеревья, целиком попавшие во внутренний прямоугольник, – без всякого постфильтра. Inside считается с лимитом 15, outside – со 100, всё это – в фоновой OperationQueue, чтобы не трогать главный поток во время движения карты.

Итог

Как только маркеры на карте перестают быть объектами UIKit (а ради производительности они перестают – см. прошлую часть), всю «геометрию взаимодействия» приходится брать на себя. Выручают тут две вещи:

• QuadTree на плоскости меркатора превращает «кто рядом с пальцем» и «кто в кадре» из O(n)-перебора в спуск по дереву;

• сферическая геометрия (computeOffset/computeHeading/гаверсинус) даёт честный перевод «пиксели ↔ метры ↔ координаты», без которого запрос «в пределах 25 px» не выразить.

А отбор «что показать» – отдельный приятный урок: оптимальный по метрике алгоритм (top-N по весу) проиграл намеренно неравномерному (20/60/20), потому что пользователь оценивает не «показали ли самые важные», а «живая ли карта целиком»