H3 bins boundary points membership

[iverase]

One of the properties of global grid systems like h3 is that at a given resolution, any latitude / longitude pair can only belong to one h3 bin. This makes points on the boundary tricky, particularly in h3 where edges are big circles. I run the following python script to check how it looks likes in h3:

import h3

cells = h3.get_res0_indexes()
for cell in sorted(cells):
  boundary =  h3.h3_to_geo_boundary(cell)
  inclusive = []
  for pos in boundary:
    inclusive.append(str(h3.geo_to_h3(pos[0], pos[1], 0) == cell))
  print(cell + " : " + ", ".join(inclusive))

And the output looks like:

8001fffffffffff : True, False, False, False, False, True
8003fffffffffff : False, False, True, True, True, True
8005fffffffffff : False, False, False, False, True, True
8007fffffffffff : False, False, False, True, False, False
8009fffffffffff : False, False, False, False, False
800bfffffffffff : True, False, True, False, True, True
800dfffffffffff : False, False, False, False, True, True
800ffffffffffff : False, False, False, False, False, False
8011fffffffffff : False, False, False, False, False, False
8013fffffffffff : False, False, False, False, False, False
8015fffffffffff : False, True, False, False, False, True
8017fffffffffff : True, False, False, False, True, True
8019fffffffffff : True, True, True, True, False, False
801bfffffffffff : False, True, True, True, False, False
801dfffffffffff : False, False, True, False, False
...

I could not see any pattern here so I would like to ask for any information / resources about how h3 handles points on the boundary, for example in order to define sided planes that can define the membership or not of a point on a h3 bin.

[nrabinowitz]

This is a good question - unfortunately the best answer I can give is that there's no defined rule that can be used in this case. Inclusion of edge and vertex points is deterministic within a given cell, but the logic that determines this is not part of the public API and difficult to reverse-engineer, as it depends on the orientation of the underlying grid, which changes for every icosahedron face.

TBH, I'm not clear on your use case here. Defining membership of a point in an H3 bin is one of the primary purposes of the library, and attempts to recreate this geometrically are likely a Bad Idea.

[iverase]

Thanks for the quick answer @nrabinowitz!

I have points indexed on a kd-tree and I would like to be able to filter it efficiently using H3 bins (give me all points inside this H3 bin). In order to do that I need to compute the spatial relationship between the H3 bin and a bounding box which it proves tricky on boundary points.

[nrabinowitz]

If the only point of the kd-tree is to index by H3 bin, you'd be better off using the H3 index itself as the index. Alternatively, you could add a separate index by H3 index. But in general, I would not suggest using H3 geometry as the basis for an index, as this is much less efficient and as you've found can have edge cases. Alternatively, you could buffer the bounding box by some percentage and then post-filter by checking the H3 index for each point.

[iverase]

The main purpose of the index is to perform geometric filtering.

The only way forward I see as you said is to buffer out hex bins to check for disjoint bounding boxes and buffer in the hex bin to check for fully contained bounding boxes, otherwise just go down the tree.

Thanks!

[ajfriend]

I'm not sure if this is a good and/or practical idea, but theoretically, could we provide a tie-breaking strategy for points exactly on the boundaries of cells?

Perhaps this gets into floating point weirdness, but if a point is exactly on the boundary of 2 or 3 cells (within a given resolution), we could, for example, tie break by assigning it consistently to the lowest cell in sorted order.

But, I'm also not familiar with the latlng_to_cell algorithm, so I'm not sure how easy this would be to implement.

[nrabinowitz]

No, sorry - we can't do anything that changes the assignment of point to cell without a significant breaking change that could invalidate existing data. I believe there is a tie-breaking strategy now, but it's in reference to the local IJK coordinate system on a particular icosahedron face, so it's not useful for end users, and likely gets very hairy around face-crossing cells. The bottom line is that latlng_to_cell, in its current form, determines which cell the point goes into, and there's no real benefit to trying to reverse-engineer it.

[sahrk]

I believe there is a tie-breaking strategy now, but it's in reference to the local IJK coordinate system on a particular icosahedron face,

There is indeed, but it is unfortunately not documented anywhere. The actual (x, y) to hex quantization occurs in a face-centered IJ coordinate system using code lifted directly from very old DGGRID code. The resulting IJ coordinates are then transformed into IJK coordinates on the appropriate face, which means the binning steps would need to be refactored if you wanted to use the H3 indexes to break ties, as suggested by @ajfriend.

I'm pretty sure points on edges are binned into the hex in the direction of the face center/local origin (e.g., down and to the left in the first quadrant). It is something that really should have been documented, so I will look into it.

[j-helland]

Very useful information in this thread! Just so I can understand better, is the tie-breaking mechanism here in the code? If not, could someone point me in the right direction?

I also want to follow up on getting the tie-breaking strategy documented better. It would have saved me a lot of time recently if the official H3 docs had any of this information, so I imagine it will save someone else time in the future, too.