Search code examples
geometryhexagonal-tilestessellation

Tessellating hexagons over a rectangle

I have an infinite grid of hexagons, defined by a cubic (x y z) coordinate system like so:

3 lines at 120 degree intervals of each other, labeled x, y, and z, and a hexagonal honeycomb pattern using these axes.

I also have a viewport -- a rectangular canvas where I will draw the hexagons.

My issue is this. Because the grid of hexagons is infinite in all directions, I can't feasibly draw all of them at once. Therefore, I need to draw all the hexagons that are in the viewport, and ONLY those hexagons.

This image summarizes what I want to do:

Hexagons intersecting inside the rectangular viewport are colored purple and thus rendered, all other hexagons are not rendered and are colored white in the diagram

In this image, purple-colored hexagons are those I want to render, while white-colored hexagons are those I don't want to render. The black rectangle is hte viewport -- all the hexagons that intersect with it are to be drawn. How would I find which hexagons to render (IE their xyz coordinates)?

Some other info:

  • I have a function that can recall a hexagon tile and draw it centered at position(x,y) in the viewport, given its cubic xyz coordinates. Therefore, all I should need is the xyz coords of each rectangle to draw, and I can draw them. This might simplify the problem.

  • I have formulas to convert from cubic hexagon coordinates to x/y coordinates, and back. Given the above diagram, r/g/b being the axes for the cubic coords with the image above, x and y being the cartesian coordinates, and s being the length of a hexagon's edge...

    y = 3/2 * s * b
b = 2/3 * y / s
x = sqrt(3) * s * ( b/2 + r)
x = - sqrt(3) * s * ( b/2 + g )
r = (sqrt(3)/3 * x - y/3 ) / s
g = -(sqrt(3)/3 * x + y/3 ) / s
r + b + g = 0
Solution

  • Let's X0, Y0 are coordinates of top left corner, RectWidth is rectangle width, HexWidth = s * Sqrt(3/2) is hexagon width.

    Find center of the closest hexagon r0, g0, b0, HX0, HY0. (Rect corner lies in this hexagon, because hexagons are Voronoy diagram cells). Remember horizontal and vertical shift DX = X0 - HX0, DY = Y0 - HY0

    Draw horizontal row of Ceil(RectWidth/HexWidth) hexagons, incrementing r coordinate, decrementing f, and keeping b the same, ROWINC=(1,-1,0). Note that if DY > HexWidth/2, you need extra top row with initial coordinates shifted up (r0, g0-1, b0+1)

    Shift starting point by L=(0, 1, -1) if the DX < 0, or by R=(1, 0, -1) otherwise. Draw another horizontal row with the same ROWINC

    Shift row starting point by alternative way (L after R, R after L). Draw horizontal rows until bottom edge is reached.

    Check whether extra row is needed in the bottom.