# Square to Hex

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.: