0

I am trying to construct a hexagonal/geodesic grid on a sphere. For my purposes I am only focussing on the North Pole. So far, I have managed to construct a triangular mesh based on the icosahedron, using the stripy package. The stripy package allows me to refine the grid through bisection: each edge is split in half, or equivalently, each triangle is split into 4 smaller triangles.

I want to create an (almost) hexagonal grid by combining 6 triangles (5 at the pole) as follows:

I have the following information available:

  • latitude/longitude of all vertices as np.array
  • triplets of indices of triangle vertices

A constraint is that indices are rather 'random', i.e. they don't increase by going outwards in a spiral or something similar.

An option is to find the midpoints of each hexagon(/pentagon) and to group together all the triangles that have this midpoint as one of their three vertices, but I am not sure how to algorithmically go about this. What would be an efficient way of finding the vertices that mark the midpoints of each hexagon? Could it be related in some way to the coarser version of the mesh (i.e. before bisection)?

falidoro
  • 399
  • 3
  • 14
  • What have you tried to identify the adjacent vertices? Brute force would simply be to search for the nearest six vertices for each vertex (Apart from the pole), wouldn’t it? Have you tried that? – DisappointedByUnaccountableMod Oct 02 '19 at 22:36
  • Not sure how you would select the vertices that you would calculate the neighbors of in order to avoid overlapping... – falidoro Oct 02 '19 at 22:48
  • see all answers in here [Mathematically producing sphere-shaped hexagonal grid](https://stackoverflow.com/a/46787885/2521214) – Spektre Oct 03 '19 at 07:20
  • @Spektre: I have seen that post, but those are entirely different ways of constructing meshes, while for now I would like to solve the problem using the mesh I have already generated. – falidoro Oct 03 '19 at 07:51
  • @falidoro in such case you should add an MCVE containing your mesh otherwise no one here would be able to help in such way ... – Spektre Oct 03 '19 at 08:11

2 Answers2

0

I think I may have just thought of an answer, but it would be great if someone could verify whether this would work and to suggest optimal ways of implementation.

  1. Let V0 be a set containing all vertices and E0 be a set containing all edges. Let V1 be an empty set that we will use to store new hexagon-midpoint-vertices for each pass. Let V2 be an empty set that will hold the final collection of hexagon midpoints. Let E1 be a collection of edges that forms the 'front-line' of the identified hexagons and let E2 be an empty set that will hold the final collection of hexagon edges.
  2. Identify the vertex at the North Pole. Move it from V0 to V1
  3. Find all edges that are opposite to this vertex. Move these edges to E1.
  4. From E0, delete edges that are connected to the vertex (later vertices) in V1.
  5. From V0, delete vertices that are connected by edges in E1.
  6. Move all vertices in V1 to V2.
  7. Each of the edges in E1 is part of another triangle, for which it forms the edge opposite to the vertex that is the center of a hexagon. Identify the vertices that are opposite to the edges in E1. Move these to V1.
  8. Move edges from E1 to E2.
  9. In E0 all edges opposite to the vertices in V1. Move these to E1.
  10. From E0, delete edges that are connected to the vertices in V1.
  11. From V0, delete vertices that are connected by edges in E1.
  12. Move all vertices in V1 to V2.

etc. etc. etc.

falidoro
  • 399
  • 3
  • 14
0

Alternatively, it is possible to construct a Voronoi diagram of the triangulation; for example using scipy.spatial.SphericalVoronoi(). The Voronoi diagram of an icosahedral grid yields a geodesic (hexagonal) grid. See for example Wang et al. (2011).

Similarly, instead of using a Voronoi diagram, one could also create a new triangulation using the midpoints of the faces of each triangle, which result in a more regular pattern, but it is less trivial to determine in which hexagon a point resides.

For the Voronoi diagram, this is much easier, as by definition the containing hexagon corresponds to the hexagon generated by the nearest vertex in the original triangulation.

Wang, Ning, and Jin-Luen Lee. "Geometric properties of the icosahedral-hexagonal grid on the two-sphere." SIAM Journal on Scientific Computing 33.5 (2011): 2536-2559.

falidoro
  • 399
  • 3
  • 14