How to perform the Search operation using Google S2 geometry

Question

I have geo location of vehicles and my point in the city and I need to find those vehicles that are within 5kms radius of my point. I could represent the vehicle locations and my point with S2 cell id. But how can i query ?

can I store data for all the users in a database and make query on S2 cell ids. As S2 cell id is using Hilbert curve, Can we know those vehicles which have closer S2 cell ids are closer in distance with each other. Or is there any other method which i have to use here to perform the search operation?

Answer 1

I would break this problem up into several steps:

1. Pick an appropriate S2-Level for your application. In your case, since you're querying by 5 KM radii, I'd pick level 13 cells, that have an average size of 1.27 km^2.

2. Generate a level-13 cell covering of the 5 KM radius around the person.

3. Get a level-13 cell from the lat/lng of the car.

4. Do a contains check of the car S2 Cell to the 5 KM radius S2 Cell covering.

Here is an example with the Node.js JavaScript S2 Library:

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

You can visualize what this looks like with Sidewalk Lab's S2 map tool:

• The covering
• Vehicle 1
• Vehicle 2