Как мне использовать S2 в сервисе Yelp или Uber?
Допустим, у меня есть список ресторанов, и у меня есть местоположение клиента, который ищет рестораны поблизости. Как я мог использовать S2?
Насколько я понимаю, без S2 я бы поддерживал свое собственное Quad Tree, в котором есть все рестораны, а затем я бы взял широту и долготу моего клиента и запросил бы свое Quad Tree, чтобы найти узел и соседние узлы Quad Tree.
Как S2 вписался бы в эту картину? Заменит ли это необходимость поддерживать собственное Quad Tree?
Я понимаю S2, что под капотом есть Quad Trees и Hilber-кривые, заполняющие пространство, которые с учетом широты и долготы могут предоставить 64-битный идентификатор ячейки, который идентифицирует узел в Quad Tree, которому принадлежат широта и долгота.
2 ответа
Эта статья из Tinder - именно то, что я искал.
Если вы создаете службу, которая требует разделения геоданных, вы должны использовать S2, чтобы предоставить вам числовую кодировку определенных местоположений или диапазон числовых кодировок для определенного радиуса. Вы бы сами поддерживали схему разделения.
Обычно в S2 это делается через существующие классы API S2, например, здесь я бы использовал S2ClosestPointQuery.
На внутреннем уровне класс запроса создает внутренний индекс (в данном случае - с использованием ячеек S2 ресторанов), и когда вы хотите найти все точки рядом с клиентом, он вычисляет диапазон ячеек на кривой Гильберта S2, которые находятся на заданном расстоянии от место поиска (в данном случае - местонахождение покупателя) и ищет эти ячейки в индексе.