How to efficiently (no pointers) store hex grid with shared edges and vertices?

Question

I have a hex grid stored in a 2d array; now I want to add some properties to the edges of the grid (e.g. rivers between hexes) and also potentially to the vertices. How can I store edges and vertices

1. Without duplication, i.e. I don't want to store a river between two hexes in both, or check neighboring hexes - I want to store it once in the edge.
2. With a fast way to find mapping between things, i.e. from a given edge to two hexes it's dividing, or from a given vertex to its 3 edges, etc.
3. Efficiently i.e. without tons of pointers in every object to every neighboring object?

I was thinking there should be 3 2d arrays (hexes, vertices, edges) with arithmetic formulas to map things to things. However for the only schemes I can come up with to store vertices and edges (since they don't map naturally onto a 2d array), the mapping formulas between array coordinates are very convoluted. I wonder if there's some simple scheme that I'm missing?

Answer 1

Assuming you have Hex objects stored in a 2d array, just make each Hex own some of its edges and vertices. For example, have each hex own the edges with arrows pointing to them as well as the two vertices between those edges:

 __
/  \ <3
\__/ <2
  ^
  1

We only store three edges and two vertices, so where do the others come from? Well, continuing counter-clockwise, edge 4 would be edge 1 from the hex above this one, edge 5 would be edge 2 from the hex to the upper left, etc. Vertices would be accessed similarly. You could add some accessor methods to make this ownership more transparent by automatically going to the appropriate neighbor to find the needed edge/vertex.

The downside of this approach is that along some of the sides of your grid, there won't be edges and vertices. You can add a set of dummy hexes around these sides and give them a flag like isDummy to indicate that they only exist to provide edges and vertices to other hexes.