Как выполнить операцию поиска с использованием геометрии Google S2

Question

У меня есть географическое местоположение транспортных средств и моя точка в городе, и мне нужно найти те транспортные средства, которые находятся в радиусе 5 км от моей точки. Я мог бы представить местоположение транспортного средства и мою точку с идентификатором ячейки S2. Но как я могу сделать запрос?

Могу ли я сохранить данные для всех пользователей в базе данных и сделать запрос по идентификаторам сот S2. Поскольку идентификатор ячейки S2 использует кривую Гильберта, можем ли мы знать, что транспортные средства, которые имеют более близкие идентификаторы ячейки S2, находятся ближе друг к другу на расстоянии. Или есть какой-то другой метод, который я должен использовать здесь, чтобы выполнить операцию поиска?

Answer 1

Я бы разбил эту проблему на несколько этапов:

1. Выберите подходящий уровень S2 для вашего приложения. В вашем случае, поскольку вы запрашиваете радиусы 5 км, я бы выбрал ячейки уровня 13, которые имеют средний размер 1,27 км ^ 2.

2. Создайте покрытие ячеек 13-го уровня радиусом 5 км вокруг человека.

3. Получите ячейку 13 уровня по широте / длине машины.

4. Проведите проверку содержания ячейки S2 автомобиля на покрытие ячейки S2 радиусом 5 км.

Вот пример библиотеки Node.js JavaScript S2:

const s2 = require('@radarlabs/s2');

# s2 cell level of ~1.27 km^2
const level = 13;

# cell covering of enclosure around a person
const enclosureLLs = [
  [40.77933906065449, -73.96983146667479],
  [40.77933906065449, -73.9634370803833],
  [40.78483079505022, -73.9634370803833],
  [40.78483079505022, -73.96983146667479],
].map((latlng) => {
  const [lat, lng] = latlng;
  return new s2.LatLng(lat, lng);
});

const enclosureCells = new Set(s2.RegionCoverer.getCoveringTokens(enclosureLLs, { min: level, max: level }));
# -> Set { '89c25894', '89c2589c' }

// arbitrary vehicle lat longs

const vehicle1 = new s2.CellId(new s2.LatLng(40.78340103809933,  -73.96515369415283)).parent(level);
# -> '89c2589c'

const vehicle2 = new s2.CellId(new s2.LatLng(40.782848623761375, -73.95506858825684)).parent(level);
# -> '89c258a4'


console.log(enclosureCells.has(vehicle1.token()));
# -> true

console.log(enclosureCells.has(vehicle2.token()));
# -> false

Вы можете визуализировать, как это выглядит, с помощью инструмента карты S2 от Side walk Lab:

• Покрытие
• Автомобиль 1
• Автомобиль 2