CODEWITHSUNDEEP
algorithm
muell
muell

Reputation: 563

Iterate Over Circular Area Of Hexagonal Grid?

I am currently working with a hexagonal grid of cells which are indexed like this:

Hexagonal Grid

I am trying to find the simplest way to iterate over a circular area of this grid. For example, with (3, 3) as the center cell and a radius of one cell, I would want the loop to iterate over the cells (3, 3), (4, 4), (4, 3), (4, 2), (3, 2), (2, 3), (3, 4) (in any order). Given the coordinate of the center cell and a radius (excluding the center cell), how would you construct a two-dimensional loop to iterate over each cell/coordinate?

Upvotes: 1

Views: 655

Answers (2)

Tom Sirgedas
Tom Sirgedas

Reputation: 3258

enter image description here

The basic idea:

Let's scan each row of the hexagon left-to-right.

How to do it:

Let R be the "cell radius".

  1. Start at the center and move left R cells. Call this cell "A". A's row has 2*R-1 cells in it.
  2. Now step one cell up/right. This cell begins a row with one less cell.
  3. Repeat step 2 until you've stepped up/right R times.

This covers the top half. Now do the lower half with similar steps (stepping down/right starting from A, to find the beginning of each of those rows).

Details

How do you step up/right? The y coordinate increases by 1. The x coordinate increases by 1 only if y was odd.

How do you step down/right? The y coordinate decreases by 1. The x coordinate increases by 1 only if y was odd.

Upvotes: 2

btilly
btilly

Reputation: 46409

The choice of grid system is what makes this one complicated. Because, for example, a step down and right might change your coordinates by (1, -1) or (0, -1) depending on which row you are in.

Therefore I would move to a different grid system, do the calculation there, then switch back to the grid system that you're showing.

Here is a demonstration of that in Python.

def loop (center, radius):
    if 0 == radius:
        yield center
    else:
        directions = [
            ( 1, -1),
            ( 0, -1),
            (-1,  0),
            (-1,  1),
            ( 0,  1),
            ( 1,  0),
        ]

        cell = list(to_normalized(center))

        cell[1] += radius

        for direction in directions:
            for i in range(radius):
                cell[0] += direction[0]
                cell[1] += direction[1]
                yield to_grid(cell)

def to_normalized (cell):
    return (cell[0] - (cell[1] // 2), cell[1])

def to_grid (cell):
    return (cell[0] + (cell[1] // 2), cell[1])

for cell in loop((3, 3), 2):
    print(cell)

Upvotes: 2

Related Questions