Search code examples
javascriptalgorithmpacking

Hexagon packing algorithm

I'm trying to pack hexagons, within bigger hexagons, as shown here:

enter image description here

For this example, I have 5 "children" to put in my "father" hexagon.

Each time I've got too many children, I would like to reduce the size (divide by 3?) of the children, to store more of them, as shown on this image (ignore the bad position quality):

enter image description here

Have you ever worked on this kind of problem? Is there any algorithm I could use to determine for a given hexagon size, the position for each new hexagon?

I've seen a lot of these algorithms for circle packing, but nothing for hexagon packing.

Thanks for your help

Solution

  • I've found exactly what I was looking for on this topic: Algorithm to generate a hexagonal grid with coordinate system

    Thanks to the link above, here is the algorithm I used to generate a grid, itemCount is the number of hexes you need to put on your grid.

    this.x and this.y are the origin of the main hex. this.radius is the radius of the main hex, in 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;
}