Cell neighbors

[atsyplenkov]

Hey 👋

Do you have plans to add cell neighbouring based on the shared edge, similar to the way it is currently implemented in Quadbin:

https://github.com/CartoDB/quadbin-py/blob/39a0adbb238ff214fbbca7b73200cfebf2aef38c/quadbin/main.py#L317-L342

or as a directed edge, as is done in h3?

[felixpalmer]

Yes, that is on the roadmap

[felixpalmer]

@atsyplenkov @alpha-beta-soup any opinions on how the Kring should be defined? Given the lattice shape it isn’t as obvious as it is for quadbin.

[alpha-beta-soup]

I had the same question but no good answer, sorry. There are only two options:

• Edge neighbours only (Rook's case contiguity)
• Edge neighbours and vertex neighbours (Queen's case contiguity)

There's no real solution to this fundamental dilemma. I would look to how k-ring is implemented in S2, rHEALPix, etc.

Yet S2 provides separate functions to retrieve both rook (edge-sharing) and queen (vertex-sharing) neighbours, but its broader neighbourhood functions (e.g. speherical caps) do not use k-ring traversal based on cell adjacency. Instead, they return all cells intersecting a region, which is defined geometrically, i.e. not topologically resolved through adjacency relationships.

So perhaps its a matter of picking a default but allowing the specification of the option.

For helping users pick which case they prefer, a table and image of the difference in set size after different size rings would be useful. Presumably the difference grows (linearly? quadratically?) with k. What about the perimeter length?

The answer of appropriate neighbourhood type would ultimately come down to the analysis question in many cases; for some the difference is immaterial so perhaps the default should be whichever is more efficient to calculate.

[felixpalmer]

Screen.Recording.2025-05-18.at.11.41.10.mov

The approach I'm thinking of is to using the underlying set of anchors to define neighboring cells. These are indexed with integers, so it should be efficient to construct an envelope around a given cell. But will have to see how this looks and figure out how to cross quintant boundaries

@alpha-beta-soup @atsyplenkov could you share what you need this feature for? It would help inform if I'm solving for the right use case

[atsyplenkov]

Thanks for sharing, @felixpalmer. I am not quite sure that I fully understand your proposed approach, but I am happy to help if you need a hand.

My only concern is that for edge neighbours only, I can understand how to get 4/5 of the neighbours. From the video you shared, it is visible that each cell has two anchors and every anchor is shared by three other cells. So, from the shared anchors, it is feasible to find four neighbours, but how do you get the fifth?

I am thinking about developing a flow accumulation tool based on the pentagon A5 cells, since they have a little area distortion. I am keen to try an implementation of a regional-scale flow accumulation estimation based on a D5 algorithm (i.e. water can flow in five directions only).

[felixpalmer]

Yes that's a good point - I need to think this through more. If there is no neat way to exploit the properties of the lattice, then then a natural way would be to go with the edge neighbors only, as there it is clear how many each cell has

Could you share a link to the D5 algorithm?

[atsyplenkov]

Could you share a link to the D5 algorithm?

@felixpalmer I am not sure that it exists yet. However, in terms of implementation and behaviour it should look very similar to D4 for rectangular grids and D6 for hexagons. You can find some discussion of this topic here: https://www.sciencedirect.com/science/article/pii/S1364815219308278

[DOSull]

Perhaps the 'almost-Cairo nature' of the underlying tiling can help.

All the tiles away from the boundaries of the quintant triangles are in two 'super-hexes' of 4 pentagons (outlined in red and blue), and all the edge-neighbours of each pentagon are contained in those two hexagons. The two super-hexes together contain 7 pentagons -- the intersection pentagon and six others. All but one of those six is an edge neighbour. Perhaps organising the indexing so that it was aware of the 'super-hexes' might make finding edge neighbours easier?

Clearly along the quintant triangle boundaries (black lines) things are a little different and at the central vertex where the five quintant triangles on a dodecahedron face meet it is different again, but my understanding is that the vast bulk of pentagons are formed by the intersection of two hexagons, which might provide a quick way to identify the edge-neighbours.

Edit Might lose 1-bit indexing via the super-hexes however, since they don't nicely fit the 64 cells in each quintant.

[felixpalmer]

I still need to sit down and figure it out, but my rough idea is to use the underlying grid that lays out the cells and then compute the necessary offsets. Given that there are just 4 orientations of the pentagon (these make up the hex meta-tile) then for each of these there should be a deterministic way to obtain the offsets, thus getting the neighborhood without any geometry calculations.

Things will naturally get fun at the edges on the quintants 😅

[DOSull]

Yeah, if it's anything like how I generate tilings in weavingspace then you have some kind of vector basis (in my context the 'translation vectors') and every tile location is some integer 2- or 3-tuple in that vector space. Ideally you want coordinates such that they differ in one coordinate only between edge-neighbours.

I found these resources useful figuring some of this out for triangular and hexagonal grids:

Nagy BN 2003. Shortest Paths in Triangular Grids with Neighbourhood Sequences. Journal of Computing and Information Technology 11(2):111

and https://www.redblobgames.com/grids/hexagons/