How to find a locations inside a Polygon with multiple data points and inside a circle with centroid lat/long, radius using uber h3-js?

Question

I am working on a bike-sharing application where I have the following requirements.

Show all bikes near the user locations in a certain radius.

For this I came with an approach where get all indexes of bike locations on a specific resolution and get all the indexes from the user location with a radius using kRing function and then find all the bike locations which are inside kRing indexes.

const res = 8;
//get hexagon index of all locations
const lookupMap = bike_locations.reduce((map, bike) => {
    const {latitude, longitude} = bike;
    const h3Index = h3.geoToH3(latitude, longitude, res);
    if (!map[h3Index]) map[h3Index] = [];
    map[h3Index].push(bike.id);
    return map;
}, {});

//hexagon index of user location
const origin = h3.geoToH3(user_lat, user_logn, res);
const radius = Math.floor(distance_in_km / (h3.edgeLength(res, h3.UNITS.km) * 2));
const lookupIndexes = h3.kRing(origin, radius);

// Find all points of bikes in those indexes
const results = lookupIndexes.reduce(
    (output, h3Index) => [...output, ...(lookupMap[h3Index] || [])], 
    []);

I have a big circle with centre lat/long, the radius of the circle in km and these big circle divided into multiple polygons with data points.

How to get all the bikes that are outside the city boundary (i.e big circle)?

How to get in which polygon how many bikes are existing and how to get in which polygon a given bike location present using polyfill?
How to display all the bike locations, polygons, big circle and filled with hexagons on a map? here I am using MapmyIndia.

How can I implement the above requirements using Uber H3-js and my solution for the point is correct or any better solution is there for the same?

score 0 · Answer 1 · answered Jun 28 '21 at 16:33

There are a lot of questions here, and I'm not sure I understand them all, but here's my attempt:

K-ring lookup

The k-ring based radius lookup seems like a reasonable solution (looks like it's based on this answer), particularly if the bike lookup map can be calculated once rather than every time you need to perform the lookup.

Bikes not in circle

Getting all the bikes not in the circle works in a similar way. If you need the circle to be more circular than a k-ring, you'd need to calculate the set of hexes within the circle - there isn't an H3 function for this, but a reasonable approach might look like:

Calculate a k-ring of cells that covers the circle
Check the haversine distance from each cell center to the circle center
If distance <= radius add the cell to the circle set

Now you have a set of cells representing the circle, filter out all bikes whose cells are in that set. The remaining bikes are outside the circle.

Bikes in polygons

To take a set of polygons and use it for lookup, you'll need a reverse index (cell => polygon). You can create it like this (untested):

const lookup = {};
for (const poly of polygons) {
  for (const cell of h3.polyfill(poly, res)) {
    lookup[cell] = polygon; // or polygon id, or whatever
  } 
}

Now you can use the index to easily lookup the polygon for a particular bike. To count the bikes in a polygon, you can either loop through all the bikes and count which ones are inside, or loop through all the cells in the polygon and determine which ones have a bike - these are both O(n), so the better option just depends on which n is smaller, bikes or cells.

How to find a locations inside a Polygon with multiple data points and inside a circle with centroid lat/long, radius using uber h3-js?

1 Answers1