В прошлой части мы научились рисовать на карте тысячи облаков, не убивая 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 = 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
}
// порог превышен – разбиваемся: раскидываем накопленные точки по детям
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 + big
for 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), потому что пользователь оценивает не «показали ли самые важные», а «живая ли карта целиком»