faster way to calculate hexagon grid coordinates

Decompose the problem into the regular square grids (not-contiguous). One list will contain all shifted hexes (i.e. the even rows) and the other will contain unshifted (straight) rows.

def calc_polygons_new(startx, starty, endx, endy, radius):
   sl = (2 * radius) * math.tan(math.pi / 6)

# calculate coordinates of the hexagon points
p = sl * 0.5
b = sl * math.cos(math.radians(30))
w = b * 2
h = 2 * sl

# offsets
for moving along and up rows
xoffset = b
yoffset = 3 * p

row = 1

shifted_xs = []
straight_xs = []
shifted_ys = []
straight_ys = []

while startx < endx:
   xs = [startx, startx, startx + b, startx + w, startx + w, startx + b, startx]
straight_xs.append(xs)
shifted_xs.append([xoffset + x
   for x in xs
])
startx += w

while starty < endy:
   ys = [starty + p, starty + (3 * p), starty + h, starty + (3 * p), starty + p, starty, starty + p]
   (straight_ys
      if row % 2
      else shifted_ys).append(ys)
starty += yoffset
row += 1

polygons = [zip(xs, ys) for xs in shifted_xs
   for ys in shifted_ys
] + [zip(xs, ys) for xs in straight_xs
   for ys in straight_ys
]
return polygons

As you predicted, zipping results in much faster performance, especially for larger grids. On my laptop I saw 3x speedup when calculating 30 hexagon grid - 10x speed for 2900 hexagon grid.

>>> from timeit
import Timer
   >>>
   t_old = Timer('calc_polygons_orig(1, 1, 100, 100, 10)', 'from hexagons import calc_polygons_orig') >>>
   t_new = Timer('calc_polygons_new(1, 1, 100, 100, 10)', 'from hexagons import calc_polygons_new') >>>
   t_old.timeit(20000)
9.23395299911499
   >>>
   t_new.timeit(20000)
3.12791109085083
   >>>
   t_old_large = Timer('calc_polygons_orig(1, 1, 1000, 1000, 10)', 'from hexagons import calc_polygons_orig') >>>
   t_new_large = Timer('calc_polygons_new(1, 1, 1000, 1000, 10)', 'from hexagons import calc_polygons_new') >>>
   t_old_large.timeit(200)
9.09613299369812
   >>>
   t_new_large.timeit(200)
0.7804560661315918

Here is a solution that doesn't require any looping. It creates grid of 50x50 hexagons:

coord_x, coord_y = np.meshgrid(50, 50, sparse = False, indexing = 'xy')

ratio = np.sqrt(3) / 2
coord_y = coord_y * ratio # Condense the coordinates along Y - axes
coord_x = coord_x.astype(np.float)
coord_x[1::2,: ] += 0.5 # Shift every other row of the grid
coord_x = coord_x.reshape(-1, 1) # Flatten the grid matrices into[2500, 1] arrays
coord_y = coord_y.reshape(-1, 1)

radius = 5 # Inflate each hexagon to the required radius
coord_x *= radius
coord_y *= radius

Suggestion : 2

Now let's assemble hexagons into a grid. With square grids, there's one obvious way to do it. With hexagons, there are multiple approaches. I like cube coordinates for algorithms and axial or doubled for storage.,Study how the cube coordinates work on the hex grid. Selecting the hexes will highlight the cube coordinates corresponding to the three axes.,To reach the other two reflections, negate the coordinates of the original and the first reflection. These are shown as white arrows in the diagram.,The cube coordinates are a reasonable choice for a hex grid coordinate system. The constraint is that q + r + s = 0 so the algorithms must preserve that. The constraint also ensures that there's a canonical coordinate for each hex.

In a regular hexagon the interior angles are 120°. There are six “wedges”, each an equilateral triangle with 60° angles inside. Each corner is size units away from the center. In code:

function pointy_hex_corner(center, size, i):
var angle_deg = 60 * i - 30°
var angle_rad = PI / 180 * angle_deg
return Point(center.x + size * cos(angle_rad),
   center.y + size * sin(angle_rad))

Determine which type of offset system you use; *-r are pointy top; *-q are flat top. The conversion is different for each.

function axial_to_oddr(hex):
var col = hex.q + (hex.r - (hex.r & 1)) / 2
var row = hex.r
return OffsetCoord(col, row)

function oddr_to_axial(hex):
var q = hex.col - (hex.row - (hex.row & 1)) / 2
var r = hex.row
return Hex(q, r)

Determine which type of offset system you use; *-r are pointy top; *-q are flat top. The conversion is different for each.

function axial_to_oddr(hex):
var col = hex.q + (hex.r - (hex.r & 1)) / 2
var row = hex.r
return OffsetCoord(col, row)

function oddr_to_axial(hex):
var q = hex.col - (hex.row - (hex.row & 1)) / 2
var r = hex.row
return Hex(q, r)

Doubled coordinates

function doubleheight_to_axial(hex):
var q = hex.col
var r = (hex.row - hex.col) / 2
return Hex(q, r)

function axial_to_doubleheight(hex):
var col = hex.q
var row = 2 * hex.r + hex.q
return DoubledCoord(col, row)

function doublewidth_to_axial(hex):
var q = (hex.col - hex.row) / 2
var r = hex.row
return Hex(q, r)

function axial_to_doublewidth(hex):
var col = 2 * hex.q + hex.r
var row = hex.r
return DoubledCoord(col, row)

Moving one space in hex coordinates involves changing one of the 3 cube coordinates by +1 and changing another one by -1 (the sum must remain 0). There are 3 possible coordinates to change by +1, and 2 remaining that could be changed by -1. This results in 6 possible changes. Each corresponds to one of the hexagonal directions. The simplest and fastest approach is to precompute the permutations and put them into a table of Cube(dq, dr, ds):

var cube_direction_vectors = [
   Cube(+1, 0, -1), Cube(+1, -1, 0), Cube(0, -1, +1), Cube(-1, 0, +1), Cube(-1, +1, 0), Cube(0, +1, -1),
]

function cube_direction(direction):
return cube_direction_vectors[direction]

function cube_add(hex, vec):
return Cube(hex.q + vec.q, hex.r + vec.r, hex.s + vec.s)

function cube_neighbor(cube, direction):
return cube_add(cube, cube_direction(direction))

Since axial is the same as cube except not storing the third coordinate, the code is the same as the previous section except we won't write out the third coordinate:

var axial_direction_vectors = [
   Hex(+1, 0), Hex(+1, -1), Hex(0, -1), Hex(-1, 0), Hex(-1, +1), Hex(0, +1),
]

function axial_direction(direction):
return axial_direction_vectors[direction]

function axial_add(hex, vec):
return Hex(hex.q + vec.q, hex.r + vec.r)

function axial_neighbor(hex, direction):
return axial_add(hex, axial_direction(direction))

Suggestion : 3

I'm using the following procedure to anycodings_geometry calculate hexagonal polygon coordinates of a anycodings_geometry given radius for a square grid of a given anycodings_geometry extent (lower left --> upper right):,Here is a solution that doesn't require anycodings_computational-geometry any looping. It creates grid of 50x50 anycodings_computational-geometry hexagons:,As you predicted, zipping results in anycodings_computational-geometry much faster performance, especially for anycodings_computational-geometry larger grids. On my laptop I saw 3x anycodings_computational-geometry speedup when calculating 30 hexagon grid anycodings_computational-geometry - 10x speed for 2900 hexagon grid. ,Here you can find additional examples anycodings_computational-geometry and link to the repo: LINK

def calc_polygons(startx, starty, endx, endy, radius):
   sl = (2 * radius) * math.tan(math.pi / 6)

# calculate coordinates of the hexagon points
p = sl * 0.5
b = sl * math.cos(math.radians(30))
w = b * 2
h = 2 * sl

origx = startx
origy = starty

# offsets
for moving along and up rows
xoffset = b
yoffset = 3 * p

polygons = []
row = 1
counter = 0

while starty < endy:
   if row % 2 == 0:
   startx = origx + xoffset
else:
   startx = origx
while startx < endx:
   p1x = startx
p1y = starty + p
p2x = startx
p2y = starty + (3 * p)
p3x = startx + b
p3y = starty + h
p4x = startx + w
p4y = starty + (3 * p)
p5x = startx + w
p5y = starty + p
p6x = startx + b
p6y = starty
poly = [
   (p1x, p1y),
   (p2x, p2y),
   (p3x, p3y),
   (p4x, p4y),
   (p5x, p5y),
   (p6x, p6y),
   (p1x, p1y)
]
polygons.append(poly)
counter += 1
startx += w
starty += yoffset
row += 1
return polygons

Decompose the problem into the regular anycodings_computational-geometry square grids (not-contiguous). One list anycodings_computational-geometry will contain all shifted hexes (i.e. the anycodings_computational-geometry even rows) and the other will contain anycodings_computational-geometry unshifted (straight) rows.

def calc_polygons_new(startx, starty, endx, endy, radius):
   sl = (2 * radius) * math.tan(math.pi / 6)

# calculate coordinates of the hexagon points
p = sl * 0.5
b = sl * math.cos(math.radians(30))
w = b * 2
h = 2 * sl

# offsets
for moving along and up rows
xoffset = b
yoffset = 3 * p

row = 1

shifted_xs = []
straight_xs = []
shifted_ys = []
straight_ys = []

while startx < endx:
   xs = [startx, startx, startx + b, startx + w, startx + w, startx + b, startx]
straight_xs.append(xs)
shifted_xs.append([xoffset + x
   for x in xs
])
startx += w

while starty < endy:
   ys = [starty + p, starty + (3 * p), starty + h, starty + (3 * p), starty + p, starty, starty + p]
   (straight_ys
      if row % 2
      else shifted_ys).append(ys)
starty += yoffset
row += 1

polygons = [zip(xs, ys) for xs in shifted_xs
   for ys in shifted_ys
] + [zip(xs, ys) for xs in straight_xs
   for ys in straight_ys
]
return polygons

As you predicted, zipping results in anycodings_computational-geometry much faster performance, especially for anycodings_computational-geometry larger grids. On my laptop I saw 3x anycodings_computational-geometry speedup when calculating 30 hexagon grid anycodings_computational-geometry - 10x speed for 2900 hexagon grid.

>>> from timeit
import Timer
   >>>
   t_old = Timer('calc_polygons_orig(1, 1, 100, 100, 10)', 'from hexagons import calc_polygons_orig') >>>
   t_new = Timer('calc_polygons_new(1, 1, 100, 100, 10)', 'from hexagons import calc_polygons_new') >>>
   t_old.timeit(20000)
9.23395299911499
   >>>
   t_new.timeit(20000)
3.12791109085083
   >>>
   t_old_large = Timer('calc_polygons_orig(1, 1, 1000, 1000, 10)', 'from hexagons import calc_polygons_orig') >>>
   t_new_large = Timer('calc_polygons_new(1, 1, 1000, 1000, 10)', 'from hexagons import calc_polygons_new') >>>
   t_old_large.timeit(200)
9.09613299369812
   >>>
   t_new_large.timeit(200)
0.7804560661315918

Here is a solution that doesn't require anycodings_computational-geometry any looping. It creates grid of 50x50 anycodings_computational-geometry hexagons:

coord_x, coord_y = np.meshgrid(50, 50, sparse = False, indexing = 'xy')

ratio = np.sqrt(3) / 2
coord_y = coord_y * ratio # Condense the coordinates along Y - axes
coord_x = coord_x.astype(np.float)
coord_x[1::2,: ] += 0.5 # Shift every other row of the grid
coord_x = coord_x.reshape(-1, 1) # Flatten the grid matrices into[2500, 1] arrays
coord_y = coord_y.reshape(-1, 1)

radius = 5 # Inflate each hexagon to the required radius
coord_x *= radius
coord_y *= radius

faster way to calculate hexagon grid coordinates

Doubled coordinates#

Doubled coordinates