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

Как-то раз я разрабатывал геолокационную соцсеть. Эта статья – продолжение предыдущей, в ней описывается, как определить, на что на карте нажал пользователь, если движок нам не предоставляет такую информацию. Как только маркеры на карте перестают быть UIView и становятся точками в GL-слое, карта больше не знает, на что ты тапнул: она отдаёт только координату пальца, а дальше твои проблемы. Разбираю, как клиентский QuadTree на плоскости сферического меркатора превращает «на какое из тысячи облаков я попал» и «какие показать в кадре» из O(n)-перебора в спуск по дереву за O(log n). Заодно — зачем для перевода «пиксели ↔ метры ↔ координаты» пришлось портировать в Swift кусок сферической тригонометрии из Google Maps Utils, и почему «честный» top-N в отборе аур проиграл намеренно неравномерному 20/60/20.

Читать далее