Imagine you had a square grid of points and you’d like to transform that grid into a hexagonal grid of points such that the local relationships between points are preserved. For irregular or arbitrary start or target grids tools like Mario Klingemann’s RasterFairy do an excellent job. However for a regular to regular transform I was wondering if there were optimal, regular, tilable solutions.

The naive way to transform from square to hex is to simply take every second row and shift it by half the gridspacing. That gives you triangles and you’re done. However, unfortunately, the triangles are now not equilateral, being stretched in y by sqrt(3)/2. Ok, you say, why not just just rescale in y by 2/sqrt(3), and now you’re done. Ok, but now you’ve changed the aspect ratio of the points. What if you wanted to preserve the aspect ratio and get an equilateral, hexagonal arrangement and minimize the grid distortion.

Obviosuly there can’t be perfect solutions to this problem since sqrt(3) is irrational. However we can find grid arrangements whose aspect ratio change is very close to 1.0

Square Hexagonal Aspect Devation Points
4x4 4x4 0.866 20
4x6 4x6 0.866 24
16x14 14x16 1.131 224
18x16 16x18 1.096 288
20x18 18x20 1.069 360
22x20 20x22 1.048 440
24x22 22x24 1.031 528
26x24 24x26 1.016 624
28x26 26x28 1.004 728

The 28x26 solution appears to be so optimal that there appears to be no better solution up to 10000 points (i didn’t search past that point. Eventually, of course, there should be an even better approximation though it becomes intractable for the assignment algorithm (see below) since the Kuhn-Munkres algorithm is O(N^3).

Ok, now once we have the grids we still have to assign which point in the square grid becomes which point in the hex grid. We can calculate the ideal minimal distortion by solving the assignment problem over a cost matrix of distances. For the patches to be tileable we need to calculate the distance matrix under periodic boundary conditions, i.e if you walk out of the unit cell to the left you reappear on the right.

16x14 = 224 points

18x16 = 288 points

20x18 = 360 points

22x20 = 440 points

24x22 = 528 points

26x24 = 624 points

28x26 = 728 points

Tiling

All these can be tiled so arbitrarily large planes of points can be converted this way.:

224 2x2

728 2x2