How to identify the hexagons which overlap with a given geofence?

Question

The H3 API reference introduced polyfill, the idea of which is "a point-in-poly operation on every hexagon in a k-ring defined around the given geofence". The questions are:

1. I don't understand what's the meaning of "k-ring defined around a geofence", is this a "ring" and it center is actually the total geofence?
2. If the judgement is based on the hexagons' center location, and do an "point in polygon" operation, it's possible that the geofence and a hexagon overlaps, but the hexagon's center is out of the geofence and I can't get it's index using polyfill. So, is there any ways that I can get the 2 kinds of hexagons separately which are totally inside a geofence and the hexagons which are partly overlaps with the geofence?

Answer 1

You can actually ignore the k-ring part of this - it's an implementation detail, and in fact that detail has changed in the latest version of the library. The basic idea in both implementations is that we collect a "test" set of cells that covers the entire polygon, and then do a point-in-poly check based on the center of each cell.

It sounds like what you need are ways to get all fully-contained cells and all intersecting cells. There's an existing feature request for this functionality, and while we'd like to add this we don't have any support for other polyfill modes in the library at present.

It's not too hard to roll this yourself, but it may be slow for large sets. You'd need to have a polygon intersection check for a cell and the polygon - a naive implementation would simply check if any two segments intersect (O(polygonVertices), since the count of cell vertices is effectively constant).

• Run polyfill to get the starting set. This includes fully contained and some, but not necessarily all, partially contained cells.

• For each cell in the starting set, check if it intersects the polygon

  • If it does not intersect, it is fully contained, add to the set of contained cells
  • If it does intersect, add to the set of partially contained cells and also to a temporary queue of "border" cells.
  • If it is contiguous with the polygon, it's fully contained. Add it to the set of contained cells, and also to the border cell queue.

• Now identify partially-contained cells that were not in the initial polyfill set. While cells remain in the border queue, pop the first cell and use kRing(cell, 1) to get its neighbors. For each neighbor:

  • If the neighbor is in the initial polyfill set, ignore.
  • If the neighbor does not intersect the polygon, ignore.
  • If the neighbor intersects the polygon, add to the set of partially contained cells and push onto the border queue.

• When the border queue is empty, your two sets (contained and partially contained) are complete.