Faster way to calculate hex grid coordinates
I use the following procedure to compute the coordinates of hexagonal polygons of a given radius for a square grid of a given extent (bottom left -> top right):
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
This works well for polygons in the millions, but quickly slows down (and takes up very large amounts of memory) for large networks. I am wondering if there is a way to optimize this, perhaps by concatenating numpy arrays of vertex arrays that were calculated based on extents, and removing loops altogether - my geometry is not good enough for this, however any suggestions for improvement are appreciated.
source to share
Decompose the problem into regular square grids (disjoint). One list will contain all shifted hexes (i.e. even lines), and the other will contain unmoved (straight) lines.
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, sharpness results in significantly better performance, especially for large networks. On my laptop, I saw a 3x speedup when calculating a 30 hex grid - 10x the speed for a 2900x hex 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
It may be possible to create an iterator rather than a list to save memory. Depends on how your code uses the polygon list.
source to share