计算六角形网格坐标的更快方法 [英] Faster way to calculate hexagon grid coordinates

问题描述

我正在使用以下过程为给定范围的正方形网格(左下->右上)计算给定半径的六边形多边形坐标:

I'm using the following procedure to calculate hexagonal polygon coordinates of a given radius for a square grid of a given extent (lower left --> upper 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

这对于数以百万计的多边形来说效果很好，但是对于大型网格，它会迅速减慢速度(并占用大量内存).我想知道是否有一种方法可以优化此结果，可能是将根据范围计算的顶点的numpy数组压缩在一起，然后完全删除循环-但是，我的几何形状对此还不够好，因此，有任何建议欢迎改进.

This works well for polygons into the millions, but quickly slows down (and takes up very large amounts of memory) for large grids. I'm wondering whether there's a way to optimise this, possibly by zipping together numpy arrays of vertices that have been calculated based on the extents, and removing the loops altogether – my geometry isn't good enough for this, however, so any suggestions for improvements are welcome.

推荐答案

将问题分解为规则的正方形网格(不连续).一个列表将包含所有移位的十六进制(即偶数行)，而另一个列表将包含未移位的(直列)行.

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

正如您所预料的那样，压缩可带来更快的性能，尤其是对于较大的网格而言.在我的笔记本电脑上，当我计算30个六角形网格时，我看到了3倍的加速速度-2900个六角形网格时是10倍的速度.

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

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

There might be an opportunity to create an iterator rather than the list to save memory. Depends on how your code is using the list of the polygons.

这篇关于计算六角形网格坐标的更快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！