计算六边形网格坐标的更快方法

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

这对于数百万个多边形来说效果很好，但对于大网格来说，速度很快就慢了下来（并且占用了大量的内存）。我想知道是否有办法优化这个问题，可能是通过将基于extents计算的顶点的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

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