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

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倍。在

^{pr2}$

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