六边形填充算法

Question

我正在尝试在更大的六边形内打包六边形，如下所示：

对于这个例子，我有 5 "children" 可以放入我的 "father" 六边形。

每次我得到太多 children，我想减小 children 的大小（除以 3？）以存储更多的 children，如此处所示图像（忽略糟糕的位置质量）：

你处理过这类问题吗？对于给定的六边形大小，是否可以使用任何算法来确定每个新六边形的位置？

我见过很多关于圆形填充的算法，但没有看到六边形填充的算法。

感谢您的帮助

Answer 1

我已经找到了关于这个主题的确切内容： Algorithm to generate a hexagonal grid with coordinate system

感谢上面的 link，这是我用来生成网格的算法，itemCount 是您需要放在网格上的十六进制数。

this.x 和 this.y 是主六角形的原点。 this.radius 是主六边形的半径，以 px 为单位。

generateHexGrid(itemCount) {
  let size = 0;
  let pushed = 0;

  /*
  `n` must be odd

    n | columns-per row sequence
    --+-------------------------
    3 | 2 3 2
    5 | 3 4 5 4 3
    7 | 4 5 6 7 6 5 4
    9 | 5 6 7 8 9 8 7 6 5
    */

  // This can be optimised to make it generic if you need more hexes
  if (itemCount <= 7) {
    size = 3;
  } else if (itemCount <= 19) {
    size = 5;
  } else if (itemCount <= 37) {
    size = 7;
  } else if (itemCount <= 61) {
    size = 9;
  }
  const radius = this.radius / size;
  const toReturn = [];
  const ang30 = 30 * (Math.PI/180);
  const xOff = Math.cos(ang30) * (radius);
  const yOff = Math.sin(ang30) * (radius);
  const half = Math.floor(size / 2);

  for (let row = 0; row < size; row++) {
    const cols = size - Math.abs(row - half);

    for (let col = 0; col < cols; col++) {
      const x = Math.ceil(this.x + xOff * (col * 2 + 1 - cols));
      const y = Math.ceil(this.y + yOff * (row - half) * 3);
      toReturn.push({
        x,
        y,
        radius,
      });
      pushed ++;
      if (pushed === itemCount) {
        return toReturn;
      }
    }
  }
  return toReturn;
}

六边形填充算法

Hexagon packing algorithm

javascript

algorithm

packing