0

I need to generate grid shells for a given level. For example, the 2d grid "shell" at level 0 is just the cell (0,0). The level 1 shell would be every cell surrounding (0,0), the level 2 shell surrounds that one, etc.

The formula for the number of shells at each level is 8*level for each level above 0, and 1 cell for level 0.

The formula for the total number of shells is just the (number of side cells + 1) / 2

So, the output for level 1 would be the coordinates (in no particular order)

(-1,0)
(0,-1)
(1, 0)
(0, 1)
(1, 1)
(-1, 1)
(1, -1)
(-1,-1)

I'm struggling to come up with an algorithm to generate the coordinates at each level, despite knowing how many there should be, and what the coordinates are for each given level.

It would be even better if the coordinates for a given shell were ordered by distance from (0,0)

I'm also interested in how this would scale to 3d.

Improve this question
1
  • 1
    start by just doing one side, then the answer will become clear
    – Ewan
    Feb 4 at 18:22

1 Answer 1

Reset to default
1

For shell 𝒩:

  • Start at (𝒩,𝒩)
  • Move 2𝒩 cells in the direction (-1, 0); location is now (-𝒩,𝒩)
  • Move 2𝒩 cells in the direction (0, -1); location is now (-𝒩,-𝒩)
  • Move 2𝒩 cells in the direction (1, 0); location is now (𝒩,-𝒩)
  • Move 2𝒩-1 cells in the direction (0, 1); the last move would take you back to (𝒩,𝒩) but we don't want to double count that.

You can do all four sides in parallel if you want, or if you want them ordered by distance from the origin start half-way down each side (i.e. at (𝒩,0), (0,𝒩), (-𝒩,0) and (0,-𝒩)) and go out half distance in both directions from the starting points.

Improve this answer
5
  • This is a good solution. But I was wondering if it's possible to do this statelessly? So, given a level and an index, it would return that index's coordinate for that level. For example, given level 1 and index 2, it would return (1,0)
    – xytor
    Feb 4 at 18:34
  • The state here is so small you can recalculate things every time if you want to. Just work out where the 𝑖th move will end you up.
    – Philip Kendall
    Feb 4 at 18:37
  • That makes sense. I'm guessing for the 3d case, I would just nest the algorithm in another loop with a different direction?
    – xytor
    Feb 4 at 18:44
  • That's one way to do it; the 2D case is generating the 4 lines with one coordinate of ±𝒩, the 3D case is generating the 6 planes with one coordinate of ±𝒩, the 4D case is generating the 8 cubes with one coordinate of ±𝒩, ... (and to go the other way, the 1D case is generating the 2 points with a coordinate of ±𝒩)
    – Philip Kendall
    Feb 4 at 18:59
  • I just realized that a very inefficient solution is to just iterate through all the nodes inside of the shell, and only add the ones where i == min || i == max || j == min || j == max; where max is just the level, and min is -level.
    – xytor
    Feb 4 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.