计算六边形网格比较快的方式坐标

Question

我使用以下过程来计算给定半径的六边形的多边形坐标为给定程度的正方形栅格（左下 - >右上）：

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 

这适用于数百万个多边形，但对于大型网格会很快变慢（并占用大量内存）。我想知道是否有办法优化这一点，可能是通过将基于范围计算的numpy顶点数组一起压缩，然后完全移除这些循环 - 但是我的几何不够好，因此，任何建议为改进而受到欢迎。

Answer 1

将问题分解为规则的正方形网格（不连续）。一个列表将包含所有移位的格式（即偶数行），另一个列表将包含未移位的（直行）行。

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 

正如你所预测的那样，压缩导致性能更快，尤其是对于大型网格。在我的笔记本电脑上，当计算30个六角形网格时，看到3倍加速 - 对于2900个六角形网格，速度为10倍。

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

可能有机会创建迭代器而不是列表来节省内存。取决于您的代码如何使用多边形列表。