Guest Post on Blinkdagger

Readers of this Web log may be interested in, An Introduction to Combinatorics, an article on the perms, randperm and nchoosek functions which I authored as a guest of Blinkdagger. Blinkdagger covers MATLAB programming, among other things, and I suggest you have a look.

Generating Hexagonal Grids for Fun and Profit

Grids are used for a variety of purposes in data analysis, such as division of physical areas into equal-sized units, or for data visualization. Some clustering techniques, such as Kohonen's Self-Organizing Map use grids to organize their internal structure.


Square Grids

By far, the most commonly-employed grids are square grids. Square grids are convenient in that every cell is the same shape with the same orientation, and boundaries between rows or columns are straight lines. Indexing square grids is easy: (x, y), and extension to more dimensions is straightforward: (x, y, z), etc. Generating square grids in MATLAB is a breeze:


>> [X Y] = meshgrid(0:8)

X =

0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8


Y =

0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6 6
7 7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8 8


X and Y now contain the coordinates for the centers of the square cells, which can be plotted in MATLAB thus (click the figure to enlarge):


>> figure, voronoi(X(:),Y(:)), axis square





meshgrid-generated grids need not have the same axes, nor equal spacing. See 'help meshgrid' for more information. The linspace and logspace MATLAB routines are handy as meshgrid arguments, as well.


Hexagonal Grids

Despite their advantages, square grids do have one basic failing: their representations of circles and other non-rectangular forms are awkward.

With a square grid, cells surrounding a central cell have mixed distances. Repeated single-unit "hops" from a central cell (such as activation in a cellular automata) result in square or diamond patterns, not circles.

Hexagonal grids, one alternative to square grids, are much cleaner in their approximation of circular regions. All six immediate neighbors of any hexagonal cell are the same distance away. Repeated single-unit hops from a given hexagonal cell maintain a relatively "round" form (at least a better one than those provided by square grids).

Generating hexagonal grids is a bit trickier than generating square grids, but with a little geometry it can be done (as always, click the figure to enlarge):

% Generate hexagonal grid
Rad3Over2 = sqrt(3) / 2;
[X Y] = meshgrid(0:1:41);
n = size(X,1);
X = Rad3Over2 * X;
Y = Y + repmat([0 0.5],[n,n/2]);

% Plot the hexagonal mesh, including cell borders
[XV YV] = voronoi(X(:),Y(:)); plot(XV,YV,'b-')
axis equal, axis([10 20 10 20]), zoom on



Shifting the resulting grid coordinates is accomplished through addition. Scaling is accomplised by multiplication. Note that individual hexagons produced by the code above are oriented with their tops and bottoms flat. Rotating the cells so that the left and right sides are flat is a simple as reversing the rolls of the x and y coordinates in the code.