Boucle dans une spirale

Un ami avait besoin d'un algorithme qui lui permettrait de parcourir les éléments d'une matrice NxM (N et M sont impairs). J'ai trouvé une solution, mais je voulais voir si mes collègues SO'ers pouvaient trouver une meilleure solution.

Je poste ma solution en réponse à cette question.

Exemple de sortie:

Pour une matrice 3x3, la sortie doit être:

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

De plus, l'algorithme doit prendre en charge les matrices non carrées, donc par exemple pour une matrice 5x3, la sortie doit être:

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

Voici ma solution (en Python):

def spiral(X, Y):
    x = y = 0
    dx = 0
    dy = -1
    for i in range(max(X, Y)**2):
        if (-X/2 < x <= X/2) and (-Y/2 < y <= Y/2):
            print (x, y)
            # DO STUFF...
        if x == y or (x < 0 and x == -y) or (x > 0 and x == 1-y):
            dx, dy = -dy, dx
        x, y = x+dx, y+dy

C ++ quelqu'un? Traduction rapide de python, publiée par souci d'exhaustivité

void Spiral( int X, int Y){
    int x,y,dx,dy;
    x = y = dx =0;
    dy = -1;
    int t = std::max(X,Y);
    int maxI = t*t;
    for(int i =0; i < maxI; i++){
        if ((-X/2 <= x) && (x <= X/2) && (-Y/2 <= y) && (y <= Y/2)){
            // DO STUFF...
        }
        if( (x == y) || ((x < 0) && (x == -y)) || ((x > 0) && (x == 1-y))){
            t = dx;
            dx = -dy;
            dy = t;
        }
        x += dx;
        y += dy;
    }
}

let x = 0
let y = 0
let d = 1
let m = 1

while true
  while 2 * x * d < m
    print(x, y)
    x = x + d
  while 2 * y * d < m
    print(x, y)
    y = y + d
  d = -1 * d
  m = m + 1

Il y a eu de nombreuses solutions proposées pour ce problème écrites dans divers langages de programmation, mais elles semblent toutes provenir de la même approche alambiquée. Je vais considérer le problème plus général du calcul d'une spirale qui peut être exprimée de manière concise en utilisant l'induction.

Cas de base: Commencez à (0, 0), avancez d'1 case, tournez à gauche, avancez d'1 case, tournez à gauche. Pas inductif: Avancez de n + 1 carrés, tournez à gauche, avancez de n + 1 carrés, tournez à gauche.

L'élégance mathématique de l'expression de ce problème suggère fortement qu'il devrait y avoir un algorithme simple pour calculer la solution. En gardant à l'esprit l'abstraction, j'ai choisi de ne pas implémenter l'algorithme dans un langage de programmation spécifique mais plutôt sous forme de pseudo-code.

Je vais d'abord considérer un algorithme pour calculer seulement 2 itérations de la spirale en utilisant 4 paires de boucles while. La structure de chaque paire est similaire, mais distincte en soi. Cela peut sembler fou au début (certaines boucles ne sont exécutées qu'une seule fois) mais pas à pas, je vais faire des transformations jusqu'à ce que nous arrivions à 4 paires de boucles identiques et pouvant donc être remplacées par une seule paire placée à l'intérieur d'une autre boucle. Cela nous fournira une solution générale de calcul de n itérations sans utiliser de conditionnelles.

let x = 0
let y = 0

//RIGHT, UP
while x < 1
  print(x, y)
  x = x + 1
while y < 1
  print(x, y)
  y = y + 1

//LEFT, LEFT, DOWN, DOWN
while x > -1
  print(x, y)
  x = x - 1
while y > -1
  print(x, y)
  y = y - 1

//RIGHT, RIGHT, RIGHT, UP, UP, UP
while x < 2
  print(x, y)
  x = x + 1
while y < 2
  print(x, y)
  y = y + 1

//LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN
while x > -2
  print(x, y)
  x = x - 1
while y > -2
  print(x, y)
  y = y - 1

La première transformation que nous allons faire est l'introduction d'une nouvelle variable d, pour la direction, qui contient la valeur +1 ou -1. La direction change après chaque paire de boucles. Puisque nous connaissons la valeur de d en tous points, nous pouvons multiplier chaque côté de chaque inégalité par elle, ajuster la direction de l'inégalité en conséquence et simplifier toute multiplication de d par une constante à une autre constante. Cela nous laisse avec ce qui suit.

let x = 0
let y = 0
let d = 1

//RIGHT, UP
while x * d < 1
  print(x, y)
  x = x + d
while y * d < 1
  print(x, y)
  y = y + d
d = -1 * d

//LEFT, LEFT, DOWN, DOWN
while x * d < 1
  print(x, y)
  x = x + d
while y * d < 1
  print(x, y)
  y = y + d
d = -1 * d

//RIGHT, RIGHT, RIGHT, UP, UP, UP
while x * d < 2
  print(x, y)
  x = x + d
while y * d < 2
  print(x, y)
  y = y + d
d = -1 * d

//LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN
while x * d < 2
  print(x, y)
  x = x + d
while y * d < 2
  print(x, y)
  y = y + d

Maintenant, nous notons que x * d et le RHS sont des entiers, nous pouvons donc soustraire toute valeur réelle entre 0 et 1 du RHS sans affecter le résultat de l'inégalité. Nous choisissons de soustraire 0,5 des inégalités de chaque autre paire de boucles while afin d'établir davantage un modèle.

let x = 0
let y = 0
let d = 1

//RIGHT, UP
while x * d < 0.5
  print(x, y)
  x = x + d
while y * d < 0.5
  print(x, y)
  y = y + d
d = -1 * d

//LEFT, LEFT, DOWN, DOWN
while x * d < 1
  print(x, y)
  x = x + d
while y * d < 1
  print(x, y)
  y = y + d
d = -1 * d

//RIGHT, RIGHT, RIGHT, UP, UP, UP
while x * d < 1.5
  print(x, y)
  x = x + d
while y * d < 1.5
  print(x, y)
  y = y + d
d = -1 * d

//LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN
while x * d < 2
  print(x, y)
  x = x + d
while y * d < 2
  print(x, y)
  y = y + d

Nous pouvons maintenant introduire une autre variable m pour le nombre de pas que nous faisons à chaque paire de boucles while.

let x = 0
let y = 0
let d = 1
let m = 0.5

//RIGHT, UP
while x * d < m
  print(x, y)
  x = x + d
while y * d < m
  print(x, y)
  y = y + d
d = -1 * d
m = m + 0.5

//LEFT, LEFT, DOWN, DOWN
while x * d < m
  print(x, y)
  x = x + d
while y * d < m
  print(x, y)
  y = y + d
d = -1 * d
m = m + 0.5

//RIGHT, RIGHT, RIGHT, UP, UP, UP
while x * d < m
  print(x, y)
  x = x + d
while y * d < m
  print(x, y)
  y = y + d
d = -1 * d
m = m + 0.5

//LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN
while x * d < m
  print(x, y)
  x = x + d
while y * d < m
  print(x, y)
  y = y + d

Enfin, on voit que la structure de chaque paire de boucles while est identique et peut se réduire à une seule boucle placée à l'intérieur d'une autre boucle. Aussi, pour éviter d'utiliser des nombres réels, j'ai multiplié la valeur initiale de m; la valeur m est incrémentée de; et les deux côtés de chaque inégalité par 2.

Cela conduit à la solution indiquée au début de cette réponse.

Voici une solution O (1) pour trouver la position dans une spirale carrée: Fiddle

function spiral(n) {
    // given n an index in the squared spiral
    // p the sum of point in inner square
    // a the position on the current square
    // n = p + a

    var r = Math.floor((Math.sqrt(n + 1) - 1) / 2) + 1;

    // compute radius : inverse arithmetic sum of 8+16+24+...=
    var p = (8 * r * (r - 1)) / 2;
    // compute total point on radius -1 : arithmetic sum of 8+16+24+...

    var en = r * 2;
    // points by face

    var a = (1 + n - p) % (r * 8);
    // compute de position and shift it so the first is (-r,-r) but (-r+1,-r)
    // so square can connect

    var pos = [0, 0, r];
    switch (Math.floor(a / (r * 2))) {
        // find the face : 0 top, 1 right, 2, bottom, 3 left
        case 0:
            {
                pos[0] = a - r;
                pos[1] = -r;
            }
            break;
        case 1:
            {
                pos[0] = r;
                pos[1] = (a % en) - r;

            }
            break;
        case 2:
            {
                pos[0] = r - (a % en);
                pos[1] = r;
            }
            break;
        case 3:
            {
                pos[0] = -r;
                pos[1] = r - (a % en);
            }
            break;
    }
    console.log("n : ", n, " r : ", r, " p : ", p, " a : ", a, "  -->  ", pos);
    return pos;
}

J'adore les générateurs de python.

def spiral(N, M):
    x,y = 0,0   
    dx, dy = 0, -1

    for dumb in xrange(N*M):
        if abs(x) == abs(y) and [dx,dy] != [1,0] or x>0 and y == 1-x:  
            dx, dy = -dy, dx            # corner, change direction

        if abs(x)>N/2 or abs(y)>M/2:    # non-square
            dx, dy = -dy, dx            # change direction
            x, y = -y+dx, x+dy          # jump

        yield x, y
        x, y = x+dx, y+dy

Tester avec:

print 'Spiral 3x3:'
for a,b in spiral(3,3):
    print (a,b),

print '\n\nSpiral 5x3:'
for a,b in spiral(5,3):
    print (a,b),

Vous obtenez:

Spiral 3x3:
(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1) 

Spiral 5x3:
(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1) (2, -1) (2, 0) (2, 1) (-2, 1) (-2, 0) (-2, -1)

Tentative de "Code golf" en spirale Java, basée sur la variante C ++.

public static void Spiral(int X, int Y) {
    int x=0, y=0, dx = 0, dy = -1;
    int t = Math.max(X,Y);
    int maxI = t*t;

    for (int i=0; i < maxI; i++){
        if ((-X/2 <= x) && (x <= X/2) && (-Y/2 <= y) && (y <= Y/2)) {
            System.out.println(x+","+y);
            //DO STUFF
        }

        if( (x == y) || ((x < 0) && (x == -y)) || ((x > 0) && (x == 1-y))) {
            t=dx; dx=-dy; dy=t;
        }   
        x+=dx; y+=dy;
    }
}

Voici une solution C ++ qui montre que vous pouvez calculer les coordonnées suivantes (x, y) directement et facilement à partir des précédentes - pas besoin de suivre la direction, le rayon ou autre chose:

void spiral(const int M, const int N)
{
    // Generate an Ulam spiral centered at (0, 0).
    int x = 0;
    int y = 0;

    int end = max(N, M) * max(N, M);
    for(int i = 0; i < end; ++i)
    {
        // Translate coordinates and mask them out.
        int xp = x + N / 2;
        int yp = y + M / 2;
        if(xp >= 0 && xp < N && yp >= 0 && yp < M)
            cout << xp << '\t' << yp << '\n';

        // No need to track (dx, dy) as the other examples do:
        if(abs(x) <= abs(y) && (x != y || x >= 0))
            x += ((y >= 0) ? 1 : -1);
        else
            y += ((x >= 0) ? -1 : 1);
    }
}

Si tout ce que vous essayez de faire est de générer les N premiers points de la spirale (sans la contrainte du problème d'origine de masquer une région N x M), le code devient très simple:

void spiral(const int N)
{
    int x = 0;
    int y = 0;
    for(int i = 0; i < N; ++i)
    {
        cout << x << '\t' << y << '\n';
        if(abs(x) <= abs(y) && (x != y || x >= 0))
            x += ((y >= 0) ? 1 : -1);
        else
            y += ((x >= 0) ? -1 : 1);
    }
}

L'astuce est que vous pouvez comparer x et y pour déterminer de quel côté du carré vous vous trouvez, et cela vous indique dans quelle direction aller.

TDD, en Java.

SpiralTest.java:

import java.awt.Point;
import java.util.List;

import junit.framework.TestCase;

public class SpiralTest extends TestCase {

    public void test3x3() throws Exception {
        assertEquals("(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1)", strung(new Spiral(3, 3).spiral()));
    }

    public void test5x3() throws Exception {
        assertEquals("(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1) (2, -1) (2, 0) (2, 1) (-2, 1) (-2, 0) (-2, -1)",
                strung(new Spiral(5, 3).spiral()));
    }

    private String strung(List<Point> points) {
        StringBuffer sb = new StringBuffer();
        for (Point point : points)
            sb.append(strung(point));
        return sb.toString().trim();
    }

    private String strung(Point point) {
        return String.format("(%s, %s) ", point.x, point.y);
    }

}

Spiral.java:

import java.awt.Point;
import java.util.ArrayList;
import java.util.List;

public class Spiral {
    private enum Direction {
    E(1, 0) {Direction next() {return N;}},
    N(0, 1) {Direction next() {return W;}},
    W(-1, 0) {Direction next() {return S;}},
    S(0, -1) {Direction next() {return E;}},;

        private int dx;
        private int dy;

        Point advance(Point point) {
            return new Point(point.x + dx, point.y + dy);
        }

        abstract Direction next();

        Direction(int dx, int dy) {
            this.dx = dx;
            this.dy = dy;
        }
    };
    private final static Point ORIGIN = new Point(0, 0);
    private final int   width;
    private final int   height;
    private Point       point;
    private Direction   direction   = Direction.E;
    private List<Point> list = new ArrayList<Point>();

    public Spiral(int width, int height) {
        this.width = width;
        this.height = height;
    }

    public List<Point> spiral() {
        point = ORIGIN;
        int steps = 1;
        while (list.size() < width * height) {
            advance(steps);
            advance(steps);
            steps++;
        }
        return list;
    }

    private void advance(int n) {
        for (int i = 0; i < n; ++i) {
            if (inBounds(point))
                list.add(point);
            point = direction.advance(point);
        }
        direction = direction.next();
    }

    private boolean inBounds(Point p) {
        return between(-width / 2, width / 2, p.x) && between(-height / 2, height / 2, p.y);
    }

    private static boolean between(int low, int high, int n) {
        return low <= n && n <= high;
    }
}

Voici ma solution (en rubis)

def spiral(xDim, yDim)
   sx = xDim / 2
   sy = yDim / 2

   cx = cy = 0
   direction = distance = 1

   yield(cx,cy)
   while(cx.abs <= sx || cy.abs <= sy)
      distance.times { cx += direction; yield(cx,cy) if(cx.abs <= sx && cy.abs <= sy); } 
      distance.times { cy += direction; yield(cx,cy) if(cx.abs <= sx && cy.abs <= sy); } 
      distance += 1
      direction *= -1
   end
end

spiral(5,3) { |x,y|
   print "(#{x},#{y}),"
}

Haskell, faites votre choix:

spiral x y = (0, 0) : concatMap ring [1 .. max x' y'] where
    ring n | n > x' = left x' n  ++ right x' (-n)
    ring n | n > y' = up   n  y' ++ down (-n) y'
    ring n          = up n n ++ left n n ++ down n n ++ right n n
    up    x y = [(x, n) | n <- [1-y .. y]]; down = (.) reverse . up
    right x y = [(n, y) | n <- [1-x .. x]]; left = (.) reverse . right
    (x', y') = (x `div` 2, y `div` 2)

spiral x y = filter (\(x',y') -> 2*abs x' <= x && 2*abs y' <= y) .
             scanl (\(a,b) (c,d) -> (a+c,b+d)) (0,0) $
             concat [ (:) (1,0) . tail 
                    $ concatMap (replicate n) [(0,1),(-1,0),(0,-1),(1,0)]
                    | n <- [2,4..max x y] ]

C'est en C.

J'ai choisi de mauvais noms de variables. Dans les noms T == haut, L == gauche, B == bas, R == droite. Donc, tli est en haut à gauche i et brj en bas à droite j.

#include<stdio.h>

typedef enum {
   TLTOR = 0,
   RTTOB,
   BRTOL,
   LBTOT
} Direction;

int main() {
   int arr[][3] = {{1,2,3},{4,5,6}, {7,8,9}, {10,11,12}};
   int tli = 0, tlj = 0, bri = 3, brj = 2;
   int i;
   Direction d = TLTOR;

   while (tli < bri || tlj < brj) {
     switch (d) {
     case TLTOR:
    for (i = tlj; i <= brj; i++) {
       printf("%d ", arr[tli][i]);
    }
    tli ++;
    d = RTTOB;
    break;
     case RTTOB:
    for (i = tli; i <= bri; i++) {
       printf("%d ", arr[i][brj]);
    }
    brj --;
    d = BRTOL;
    break;
     case BRTOL:
    for (i = brj; i >= tlj; i--) {
       printf("%d ", arr[bri][i]);
    }
    bri --;
        d = LBTOT;
    break;
     case LBTOT:
    for (i = bri; i >= tli; i--) {
       printf("%d ", arr[i][tlj]);
    }
    tlj ++;
        d = TLTOR;
    break;
 }
   }
   if (tli == bri == tlj == brj) {
      printf("%d\n", arr[tli][tlj]);
   }
}

J'ai une bibliothèque open source, pixelscan , qui est une bibliothèque python qui fournit des fonctions pour numériser des pixels sur une grille dans une variété de modèles spatiaux. Les motifs spatiaux inclus sont les circulaires, les anneaux, les grilles, les serpents et les marches aléatoires. Il existe également diverses transformations (par exemple, couper, permuter, faire pivoter, traduire). Le problème OP d'origine peut être résolu comme suit

for x, y in clip(swap(ringscan(0, 0, 0, 2)), miny=-1, maxy=1):
    print x, y

qui rapporte les points

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

Les générateurs de bibliothèques et les transformations peuvent être enchaînés pour changer les points dans une grande variété d'ordres et de modèles spatiaux.

Voici une solution en Python 3 pour imprimer des entiers consécutifs dans une spirale dans le sens horaire et antihoraire.

import math

def sp(n): # spiral clockwise
    a=[[0 for x in range(n)] for y in range(n)]
    last=1
    for k in range(n//2+1):
      for j in range(k,n-k):
          a[k][j]=last
          last+=1
      for i in range(k+1,n-k):
          a[i][j]=last
          last+=1
      for j in range(n-k-2,k-1,-1):
          a[i][j]=last
          last+=1
      for i in range(n-k-2,k,-1):
          a[i][j]=last
          last+=1

    s=int(math.log(n*n,10))+2 # compute size of cell for printing
    form="{:"+str(s)+"}"
    for i in range(n):
        for j in range(n):
            print(form.format(a[i][j]),end="")
        print("")

sp(3)
# 1 2 3
# 8 9 4
# 7 6 5

sp(4)
#  1  2  3  4
# 12 13 14  5
# 11 16 15  6
# 10  9  8  7

def sp_cc(n): # counterclockwise
    a=[[0 for x in range(n)] for y in range(n)]
    last=1
    for k in range(n//2+1):
      for j in range(n-k-1,k-1,-1):
          a[n-k-1][j]=last
          last+=1
      for i in range(n-k-2,k-1,-1):
          a[i][j]=last
          last+=1
      for j in range(k+1,n-k):
          a[i][j]=last
          last+=1
      for i in range(k+1,n-k-1):
          a[i][j]=last
          last+=1

    s=int(math.log(n*n,10))+2 # compute size of cell for printing
    form="{:"+str(s)+"}"
    for i in range(n):
        for j in range(n):
            print(form.format(a[i][j]),end="")
        print("")

sp_cc(5)
#  9 10 11 12 13
#  8 21 22 23 14
#  7 20 25 24 15
#  6 19 18 17 16
#  5  4  3  2  1

Explication

Une spirale est composée de carrés concentriques, par exemple un carré de 5x5 avec une rotation dans le sens des aiguilles d'une montre ressemble à ceci:

 5x5        3x3      1x1

>>>>>
^   v       >>>
^   v   +   ^ v   +   >
^   v       <<<
<<<<v

( >>>>>signifie "aller 5 fois à droite" ou augmenter l'index de colonne 5 fois,v signifie diminuer ou augmenter l'index de ligne, etc.)

Tous les carrés sont identiques jusqu'à leur taille, j'ai bouclé sur les carrés concentriques.

Pour chaque carré, le code a quatre boucles (une pour chaque côté), dans chaque boucle nous augmentons ou diminuons les colonnes ou l'index de ligne. Si iest l'index de ligne et jl'index de colonne, alors un carré de 5x5 peut être construit en: - incrémentant jde 0 à 4 (5 fois) - incrémentant ide 1 à 4 (4 fois) - décrémentant jde 3 à 0 (4 fois) - décrémentanti de 3 à 1 (3 fois)

Pour les carrés suivants (3x3 et 1x1), nous faisons de même mais décalons les indices initial et final de manière appropriée. J'ai utilisé un indexk pour chaque carré concentrique, il y a n // 2 + 1 carrés concentriques.

Enfin, quelques maths pour une jolie impression.

Pour imprimer les index:

def spi_cc(n): # counter-clockwise
    a=[[0 for x in range(n)] for y in range(n)]
    ind=[]
    last=n*n
    for k in range(n//2+1):
      for j in range(n-k-1,k-1,-1):
          ind.append((n-k-1,j))
      for i in range(n-k-2,k-1,-1):
          ind.append((i,j))
      for j in range(k+1,n-k):
          ind.append((i,j))
      for i in range(k+1,n-k-1):
          ind.append((i,j))

    print(ind)

spi_cc(5)

Voici c #, linq'ish.

public static class SpiralCoords
{
  public static IEnumerable<Tuple<int, int>> GenerateOutTo(int radius)
  {
    //TODO trap negative radius.  0 is ok.

    foreach(int r in Enumerable.Range(0, radius + 1))
    {
      foreach(Tuple<int, int> coord in GenerateRing(r))
      {
        yield return coord;
      }
    }
  }

  public static IEnumerable<Tuple<int, int>> GenerateRing(int radius)
  {
    //TODO trap negative radius.  0 is ok.

    Tuple<int, int> currentPoint = Tuple.Create(radius, 0);
    yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2);

    //move up while we can
    while (currentPoint.Item2 < radius)
    {
      currentPoint.Item2 += 1;
      yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2);
    }
    //move left while we can
    while (-radius < currentPoint.Item1)
    {
      currentPoint.Item1 -=1;
      yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2);    
    }
    //move down while we can
    while (-radius < currentPoint.Item2)
    {
      currentPoint.Item2 -= 1;
      yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2);
    }
    //move right while we can
    while (currentPoint.Item1 < radius)
    {
      currentPoint.Item1 +=1;
      yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2);    
    }
    //move up while we can
    while (currentPoint.Item2 < -1)
    {
      currentPoint.Item2 += 1;
      yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2);
    }
  }

}

Le premier exemple de la question (3x3) serait:

var coords = SpiralCoords.GenerateOutTo(1);

Le deuxième exemple de la question (5x3) serait:

var coords = SpiralCoords.GenerateOutTo(2).Where(x => abs(x.Item2) < 2);

Ceci est une version légèrement différente - essayant d'utiliser recursionet iteratorsdans LUA. A chaque étape, le programme descend plus loin à l'intérieur de la matrice et boucle. J'ai également ajouté un drapeau supplémentaire à spiral clockwiseou anticlockwise. La sortie commence à partir des coins inférieurs droit et effectue une boucle récursive vers le centre.

local row, col, clockwise

local SpiralGen
SpiralGen = function(loop)  -- Generator of elements in one loop
    local startpos = { x = col - loop, y = row - loop }
    local IteratePosImpl = function() -- This function calculates returns the cur, next position in a loop. If called without check, it loops infinitely

        local nextpos = {x = startpos.x, y = startpos.y}        
        local step = clockwise and {x = 0, y = -1} or { x = -1, y = 0 }

        return function()

            curpos = {x = nextpos.x, y = nextpos.y}
            nextpos.x = nextpos.x + step.x
            nextpos.y = nextpos.y + step.y
            if (((nextpos.x == loop or nextpos.x == col - loop + 1) and step.y == 0) or 
                ((nextpos.y == loop or nextpos.y == row - loop + 1) and step.x == 0)) then --Hit a corner in the loop

                local tempstep = {x = step.x, y = step.y}
                step.x = clockwise and tempstep.y or -tempstep.y
                step.y = clockwise and -tempstep.x or tempstep.x
                -- retract next step with new step
                nextpos.x = curpos.x + step.x 
                nextpos.y = curpos.y + step.y

            end         
            return curpos, nextpos
        end
    end
    local IteratePos = IteratePosImpl() -- make an instance
    local curpos, nextpos = IteratePos()
    while (true) do
        if(nextpos.x == startpos.x and nextpos.y == startpos.y) then            
            coroutine.yield(curpos)
            SpiralGen(loop+1) -- Go one step inner, since we're done with this loop
            break -- done with inner loop, get out
        else
            if(curpos.x < loop + 1 or curpos.x > col - loop or curpos.y < loop + 1 or curpos.y > row - loop) then
                break -- done with all elemnts, no place to loop further, break out of recursion
            else
                local curposL = {x = curpos.x, y = curpos.y}
                curpos, nextpos = IteratePos()
                coroutine.yield(curposL)
            end
        end     
    end 
end


local Spiral = function(rowP, colP, clockwiseP)
    row = rowP
    col = colP
    clockwise = clockwiseP
    return coroutine.wrap(function() SpiralGen(0) end) -- make a coroutine that returns all the values as an iterator
end


--test
for pos in Spiral(10,2,true) do
    print (pos.y, pos.x)
end

for pos in Spiral(10,9,false) do
    print (pos.y, pos.x)
end

// Implémentation PHP

function spiral($n) {

    $r = intval((sqrt($n + 1) - 1) / 2) + 1;

    // compute radius : inverse arithmetic sum of 8+16+24+...=
    $p = (8 * $r * ($r - 1)) / 2;
    // compute total point on radius -1 : arithmetic sum of 8+16+24+...

    $en = $r * 2;
    // points by face

    $a = (1 + $n - $p) % ($r * 8);
    // compute de position and shift it so the first is (-r,-r) but (-r+1,-r)
    // so square can connect

    $pos = array(0, 0, $r);
    switch (intval($a / ($r * 2))) {
        // find the face : 0 top, 1 right, 2, bottom, 3 left
        case 0:
            $pos[0] = $a - $r;
            $pos[1] = -$r;
            break;
        case 1:
            $pos[0] = $r;
            $pos[1] = ($a % $en) - $r;
            break;
        case 2:
            $pos[0] = $r - ($a % $en);
            $pos[1] = $r;
            break;
        case 3:
            $pos[0] = -$r;
            $pos[1] = $r - ($a % $en);
            break;
    }
    return $pos;
}

for ($i = 0; $i < 168; $i++) {

    echo '<pre>';
    print_r(spiral($i));
    echo '</pre>';
}

Voici une solution itérative JavaScript (ES6) à ce problème:

let spiralMatrix = (x, y, step, count) => {
    let distance = 0;
    let range = 1;
    let direction = 'up';

    for ( let i = 0; i < count; i++ ) {
        console.log('x: '+x+', y: '+y);
        distance++;
        switch ( direction ) {
            case 'up':
                y += step;
                if ( distance >= range ) {
                    direction = 'right';
                    distance = 0;
                }
                break;
            case 'right':
                x += step;
                if ( distance >= range ) {
                    direction = 'bottom';
                    distance = 0;
                    range += 1;
                }
                break;
            case 'bottom':
                y -= step;
                if ( distance >= range ) {
                    direction = 'left';
                    distance = 0;
                }
                break;
            case 'left':
                x -= step;
                if ( distance >= range ) {
                    direction = 'up';
                    distance = 0;
                    range += 1;
                }
                break;
            default:
                break;
        }
    }
}

Voici comment l'utiliser:

spiralMatrix(0, 0, 1, 100);

Cela créera une spirale vers l'extérieur, commençant aux coordonnées (x = 0, y = 0) avec un pas de 1 et un nombre total d'éléments égal à 100. La mise en œuvre démarre toujours le mouvement dans l'ordre suivant - haut, droite, bas, la gauche.

Veuillez noter que cette implémentation crée des matrices carrées.

Voici une réponse dans Julia: mon approche consiste à attribuer les points en carrés concentriques (`` spirales '') autour de l'origine (0,0), où chaque carré a une longueur de côtém = 2n + 1 , pour produire un dictionnaire ordonné avec des numéros d'emplacement (à partir de 1 pour l'origine) comme clés et la coordonnée correspondante comme valeur.

Puisque l'emplacement maximum par spirale est à (n,-n), le reste des points peut être trouvé en travaillant simplement en arrière à partir de ce point, c'est-à-dire à partir du coin inférieur droit par m-1unités, puis en répétant pour les 3 segments perpendiculaires dem-1 unités .

Ce processus est écrit dans l'ordre inverse ci-dessous, correspondant à la façon dont la spirale se déroule plutôt qu'à ce processus de comptage inversé, c'est-à-dire que le rasegment [ascendant à droite] est décrémenté de 3(m+1), puis la[ascendant à gauche] de 2(m+1), et ainsi de suite - j'espère que cela s'explique par lui-même .

import DataStructures: OrderedDict, merge

function spiral(loc::Int)
    s = sqrt(loc-1) |> floor |> Int
    if s % 2 == 0
        s -= 1
    end
    s = (s+1)/2 |> Int
    return s
end

function perimeter(n::Int)
    n > 0 || return OrderedDict([1,[0,0]])
    m = 2n + 1 # width/height of the spiral [square] indexed by n
    # loc_max = m^2
    # loc_min = (2n-1)^2 + 1
    ra = [[m^2-(y+3m-3), [n,n-y]] for y in (m-2):-1:0]
    la = [[m^2-(y+2m-2), [y-n,n]] for y in (m-2):-1:0]
    ld = [[m^2-(y+m-1), [-n,y-n]] for y in (m-2):-1:0]
    rd = [[m^2-y, [n-y,-n]] for y in (m-2):-1:0]
    return OrderedDict(vcat(ra,la,ld,rd))
end

function walk(n)
    cds = OrderedDict(1 => [0,0])
    n > 0 || return cds
    for i in 1:n
        cds = merge(cds, perimeter(i))
    end
    return cds
end

Donc, pour votre premier exemple, vous connecter m = 3à l'équation pour trouver n donne n = (5-1)/2 = 2, et walk(2)donne un dictionnaire ordonné d'emplacements en coordonnées, que vous pouvez transformer en un simple tableau de coordonnées en accédant au valschamp du dictionnaire :

walk(2)
DataStructures.OrderedDict{Any,Any} with 25 entries:
  1  => [0,0]
  2  => [1,0]
  3  => [1,1]
  4  => [0,1]
  ⋮  => ⋮

[(co[1],co[2]) for co in walk(2).vals]
25-element Array{Tuple{Int64,Int64},1}:
 (0,0)  
 (1,0)  
 ⋮       
 (1,-2) 
 (2,-2)

Notez que pour certaines fonctions [par exemple norm], il peut être préférable de laisser les coordonnées dans des tableaux plutôt que Tuple{Int,Int}, mais ici je les change en tuples—(x,y) - comme demandé, en utilisant la compréhension de liste.

Le contexte de "prise en charge" d'une matrice non carrée n'est pas spécifié (notez que cette solution calcule toujours les valeurs hors grille), mais si vous souhaitez filtrer uniquement la plage xpar y(ici pour x=5, y=3) après avoir calculé la spirale complète puis intersectcette matrice contre les valeurs de walk.

grid = [[x,y] for x in -2:2, y in -1:1]
5×3 Array{Array{Int64,1},2}:
 [-2,-1]  [-2,0]  [-2,1]
   ⋮       ⋮       ⋮ 
 [2,-1]   [2,0]   [2,1]

[(co[1],co[2]) for co in intersect(walk(2).vals, grid)]
15-element Array{Tuple{Int64,Int64},1}:
 (0,0)  
 (1,0)  
 ⋮ 
 (-2,0) 
 (-2,-1)

Votre question ressemble à une question appelée mémoire en spirale. Dans ce problème, chaque carré de la grille est alloué selon un motif en spirale à partir du numéro 1 qui se situe à l'origine. Et puis compter en montant en spirale vers l'extérieur. Par exemple:

17  16  15  14  13

18   5   4   3  12

19   6   1   2  11

20   7   8   9  10

21  22  23  ---->

Ma solution pour calculer les coordonnées de chaque nombre suivant ce modèle en spirale est postée ci-dessous:

def spiral_pattern(num):
    x = y = 0
    for _ in range(num-1):
        x, y = find_next(x, y)
    yield (x, y)


def find_next(x, y):
    """find the coordinates of the next number"""
    if x == 0 and y == 0:
        return 1, 0

    if abs(x) == abs(y):
        if x > 0 and y > 0:
            x, y = left(x, y)
        elif x < 0 and y > 0:
            x, y = down(x, y)
        elif x < 0 and y < 0:
            x, y = right(x, y)
        elif x > 0 and y < 0:
            x, y = x+1, y
    else:
        if x > y and abs(x) > abs(y):
            x, y = up(x, y)
        elif x < y and abs(x) < abs(y):
            x, y = left(x, y)
        elif x < y and abs(x) > abs(y):
            x, y = down(x, y)
        elif x > y and abs(x) < abs(y):
            x, y = right(x, y)

    return x, y

def up(x, y):
    return x, y+1


def down(x, y):
    return x, y-1


def left(x, y):
    return x-1, y


def right(x, y):
    return x+1, y

Ceci est basé sur votre propre solution, mais nous pouvons être plus intelligents pour trouver les coins. Cela permet de voir plus facilement comment vous pourriez sauter les zones à l'extérieur si M et N sont très différents.

def spiral(X, Y):
    x = y = 0
    dx = 0
    dy = -1
    s=0
    ds=2
    for i in range(max(X, Y)**2):
            if abs(x) <= X and abs(y) <= Y/2:
                    print (x, y)
                    # DO STUFF...
            if i==s:
                    dx, dy = -dy, dx
                    s, ds = s+ds/2, ds+1
            x, y = x+dx, y+dy

et une solution basée sur un générateur qui est meilleure que O (max (n, m) ^ 2), C'est O (nm + abs (nm) ^ 2) car elle saute des bandes entières si elles ne font pas partie de la solution.

def spiral(X,Y):
X = X+1>>1
Y = Y+1>>1
x = y = 0
d = side = 1
while x<X or y<Y:
    if abs(y)<Y:
        for x in range(x, x+side, d):
            if abs(x)<X: yield x,y
        x += d
    else:
        x += side
    if abs(x)<X:
        for y in range(y, y+side, d):
            if abs(y)<Y: yield x,y
        y += d
    else:
        y += side
    d =-d
    side = d-side

Here is my attempt for simple C solution. First print the outer spiral and move one block inside..and repeat.

#define ROWS        5
#define COLS        5
//int A[ROWS][COLS] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {11, 12, 13, 14}, {15, 16, 17, 18} };
//int A[ROWS][COLS] = { {1, 2, 3}, {6, 7, 8}, { 12, 13, 14} };
//int A[ROWS][COLS] = { {1, 2}, {3, 4}};

int A[ROWS][COLS] = { {1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15} , {16, 17, 18, 19, 20}, {21, 22, 23, 24, 25} };


void print_spiral(int rows, int cols)
{
    int row = 0;
    int offset = 0;

    while (offset < (ROWS - 1)) {
        /* print one outer loop at a time. */
        for (int col = offset; col <= cols; col++) {
            printf("%d ", A[offset][col]);
        }

        for (row = offset + 1; row <= rows; row++) {
            printf("%d ", A[row][cols]);
        }

        for (int col = cols - 1; col >= offset; col--) {
            printf("%d ", A[rows][col]);
        }

        for (row = rows - 1; row >= offset + 1; row--) {
            printf("%d ", A[row][offset]);
        }

       /* Move one block inside */
        offset++;
        rows--;
        cols--;
    }
    printf("\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
    print_spiral(ROWS-1, COLS-1);
    return 0;
}

C'est ma très très mauvaise solution, faite à partir d'une connaissance minimale de Java. Ici, je dois placer des unités sur un champ en spirale. Les unités ne peuvent pas être placées au-dessus d'autres unités ou sur des montagnes ou dans l'océan.

Pour être clair. Ce n'est pas une bonne solution. C'est une très mauvaise solution ajoutée pour le plaisir des autres à rire de la façon dont cela peut être mal fait

private void unitPlacementAlgorithm(Position p, Unit u){
    int i = p.getRow();
    int j = p.getColumn();

    int iCounter = 1;
    int jCounter = 0;

    if (getUnitAt(p) == null) {
            unitMap.put(p, u);
    } else {
        iWhileLoop(i, j, iCounter, jCounter, -1, u);
    }

}

private void iWhileLoop(int i, int j, int iCounter, int jCounter, int fortegn, Unit u){
    if(iCounter == 3) {
        for(int k = 0; k < 3; k++) {
            if(k == 2) { //This was added to make the looping stop after 9 units
                System.out.println("There is no more room around the city");
                return; 
            }
            i--;

            if (getUnitAt(new Position(i, j)) == null 
                && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.OCEANS)) 
                && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.MOUNTAINS))) {
                    unitMap.put(new Position(i, j), u);
                    return;
            }
            iCounter--;
        }
    }

    while (iCounter > 0) {
        if (fortegn > 0) {
            i++;
        } else {
            i--;
        }

        if (getUnitAt(new Position(i, j)) == null 
            && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.OCEANS)) 
            && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.MOUNTAINS))) {
                unitMap.put(new Position(i, j), u);
                return;
        }
        iCounter--;
        jCounter++;
    }
    fortegn *= -1;
    jWhileLoop(i, j, iCounter, jCounter, fortegn, u);
}

private void jWhileLoop(int i, int j, int iCounter, int jCounter,
        int fortegn, Unit u) {
    while (jCounter > 0) {
        if (fortegn > 0) {
            j++;
        } else {
            j--;
        }

        if (getUnitAt(new Position(i, j)) == null 
            && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.OCEANS)) 
            && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.MOUNTAINS))) {
                unitMap.put(new Position(i, j), u);
                return;

        }
        jCounter--;
        iCounter++;
        if (jCounter == 0) {
            iCounter++;
        }

    }
    iWhileLoop(i, j, iCounter, jCounter, fortegn, u);
}

Cudos à tous ceux qui peuvent réellement lire ceci

Question bonus: Quelle est la durée de fonctionnement de cet "algorithme"? : P

Solution pour AutoIt

#include <Math.au3>
#include <Array.au3>

Func SpiralSearch($xMax,$yMax)
    $x = 0
    $y = 0
    $dx = 0
    $dy = -1
    for $i=0 To _max($xMax, $yMax)^2-1 Step 1
        if -$xMax/2 < $x and $x <= $xMax/2 And -$yMax/2 < $y And $y <= $yMax/2 Then
            MsgBox(0, "We are here ", $x & " " & $y)
        EndIf
        if $x == $y or ($x < 0 and $x == -$y) or ($x > 0 and $x == 1-$y) Then
            _ArraySwap ($dx, $dy)
            $dx=-$dx
        EndIf
        $x += $dx
        $y += $dy
    Next
EndFunc

J'ai récemment eu un défi similaire où j'ai dû créer un tableau 2D et utiliser un algorithme de matrice en spirale pour trier et imprimer les résultats. Ce code C # fonctionnera avec un tableau N, N 2D. Il est détaillé pour plus de clarté et peut probablement être retravaillé pour répondre à vos besoins.

//CREATE A NEW MATRIX OF SIZE 4 ROWS BY 4 COLUMNS - SCALE MATRIX SIZE HERE
SpiralMatrix SM = new SpiralMatrix(4, 4);
string myData = SM.Read();


public class SpiralMatrix
{
    //LETS BUILD A NEW MATRIX EVERY TIME WE INSTANTIATE OUR CLASS
    public SpiralMatrix(int Rows, int Cols)
    {
        Matrix = new String[Rows, Cols];

        int pos = 1;
        for(int r = 0; r<Rows; r++){
            for (int c = 0; c < Cols; c++)
            {
                //POPULATE THE MATRIX WITH THE CORRECT ROW,COL COORDINATE
                Matrix[r, c] = pos.ToString();
                pos++;
            }
        }
    }

    //READ MATRIX
    public string Read()
    {
        int Row = 0;
        int Col = 0;

        string S = "";
        bool isDone = false;

        //CHECK tO SEE IF POSITION ZERO IS AVAILABLE
        if(PosAvailable(Row, Col)){
            S = ConsumePos(Row, Col);
        }


        //START READING SPIRAL
        //THIS BLOCK READS A FULL CYCLE OF RIGHT,DOWN,LEFT,UP EVERY ITERATION
        while(!isDone)
        {
            bool goNext = false;

            //READ ALL RIGHT SPACES ON THIS PATH PROGRESSION
            while (PosAvailable(Row, Col+1))
            {
                //Is ReadRight Avail
                Col++;
                S += ConsumePos(Row, Col);
                goNext = true;
            }

            //READ ALL DOWN SPACES ON THIS PATH PROGRESSION
            while(PosAvailable(Row+1, Col)){
                //Is ReadDown Avail
                Row++;
                S += ConsumePos(Row, Col);
                goNext = true;
            }

            //READ ALL LEFT SPACES ON THIS PATH PROGRESSION
            while(PosAvailable(Row, Col-1)){
                //Is ReadLeft Avail
                Col--;
                S += ConsumePos(Row, Col);
                goNext = true;
            }

            //READ ALL UP SPACES ON THIS PATH PROGRESSION
            while(PosAvailable(Row-1, Col)){
                //Is ReadUp Avail
                Row--;
                S += ConsumePos(Row, Col);
                goNext = true;
            }

            if(!goNext){
                //DONE - SET EXIT LOOP FLAG
                isDone = true;
            }
        }

        return S;
    }

    //DETERMINE IF THE POSITION IS AVAILABLE
    public bool PosAvailable(int Row, int Col)
    {
        //MAKE SURE WE ARE WITHIN THE BOUNDS OF THE ARRAY
        if (Row < Matrix.GetLength(0) && Row >= 0
            && Col < Matrix.GetLength(1) && Col >= 0)
        {
            //CHECK COORDINATE VALUE
            if (Matrix[Row, Col] != ConsumeChar)
                return true;
            else
                return false;
        }
        else
        {
            //WE ARE OUT OF BOUNDS
            return false;
        }
    }

    public string ConsumePos(int Row, int Col)
    {
        string n = Matrix[Row, Col];
        Matrix[Row, Col] = ConsumeChar;
        return n;
    }

    public string ConsumeChar = "X";
    public string[,] Matrix;
}

J'ai fait celui-ci avec un ami qui ajuste la spirale au rapport hauteur / largeur de la toile sur Javascript. La meilleure solution que j'ai eue pour une évolution d'image pixel par pixel, remplissant l'image entière.

J'espère que cela aide quelqu'un.

var width = 150;
var height = 50;

var x = -(width - height)/2;
var y = 0;
var dx = 1;
var dy = 0;
var x_limit = (width - height)/2;
var y_limit = 0;
var counter = 0;

var canvas = document.getElementById("canvas");
var ctx = canvas.getContext('2d');

setInterval(function(){
   if ((-width/2 < x && x <= width/2)  && (-height/2 < y && y <= height/2)) {
       console.log("[ " + x + " , " +  y + " ]");
       ctx.fillStyle = "#FF0000";
       ctx.fillRect(width/2 + x, height/2 - y,1,1);
   }
   if( dx > 0 ){//Dir right
       if(x > x_limit){
           dx = 0;
           dy = 1;
       }
   }
   else if( dy > 0 ){ //Dir up
       if(y > y_limit){
           dx = -1;
           dy = 0;
       }
   }
   else if(dx < 0){ //Dir left
       if(x < (-1 * x_limit)){
           dx = 0;
           dy = -1;
       }
   }
   else if(dy < 0) { //Dir down
       if(y < (-1 * y_limit)){
           dx = 1;
           dy = 0;
           x_limit += 1;
           y_limit += 1;
       }
   }
   counter += 1;
   //alert (counter);
   x += dx;
   y += dy;      
}, 1);

Vous pouvez le voir fonctionner sur http://jsfiddle.net/hitbyatruck/c4Kd6/ . Assurez-vous simplement de changer la largeur et la hauteur du canevas sur les vars javascript et sur les attributs sur le HTML.

Juste pour s'amuser en Javascript:

function spiral(x, y) {
  var iy = ix = 0
    , hr = (x - 1) / 2
    , vr = (y - 1) / 2
    , tt = x * y
    , matrix = []
    , step = 1
    , dx = 1
    , dy = 0;

  while(matrix.length < tt) {

    if((ix <= hr && ix >= (hr * -1)) && (iy <= vr && (iy >= (vr * -1)))) {
      console.log(ix, iy);
      matrix.push([ix, iy]);
    }

    ix += dx;
    iy += dy;

    // check direction
    if(dx !== 0) {
      // increase step
      if(ix === step && iy === (step * -1)) step++;

      // horizontal range reached
      if(ix === step || (ix === step * -1)) {
        dy = (ix === iy)? (dx * -1) : dx;
        dx = 0;  
      }
    } else {
      // vertical range reached
      if(iy === step || (iy === step * -1)) {
        dx = (ix === iy)? (dy * -1) : dy;
        dy = 0;
      }
    }
  }

  return matrix;
}

var sp = spiral(5, 3);

Version C #, gère également les tailles non carrées.

private static Point[] TraverseSpiral(int width, int height) {
    int numElements = width * height + 1;
    Point[] points = new Point[numElements];

    int x = 0;
    int y = 0;
    int dx = 1;
    int dy = 0;
    int xLimit = width - 0;
    int yLimit = height - 1;
    int counter = 0;

    int currentLength = 1;
    while (counter < numElements) {
        points[counter] = new Point(x, y);

        x += dx;
        y += dy;

        currentLength++;
        if (dx > 0) {
            if (currentLength >= xLimit) {
                dx = 0;
                dy = 1;
                xLimit--;
                currentLength = 0;
            }
        } else if (dy > 0) {
            if (currentLength >= yLimit) {
                dx = -1;
                dy = 0;
                yLimit--;
                currentLength = 0;
            }
        } else if (dx < 0) {
            if (currentLength >= xLimit) {
                dx = 0;
                dy = -1;
                xLimit--;
                currentLength = 0;
            }
        } else if (dy < 0) {
            if (currentLength >= yLimit) {
                dx = 1;
                dy = 0;
                yLimit--;
                currentLength = 0;
            }
        }

        counter++;
    }

    Array.Reverse(points);
    return points;
}

Je partage ce code que j'ai conçu dans un but différent; il s'agit de trouver le numéro de colonne "X" et le numéro de ligne "Y" de l'élément de tableau @ spiral index "index". Cette fonction prend la largeur "w" et la hauteur "h" de la matrice, ainsi que l '"index" requis. Bien entendu, cette fonction peut être utilisée pour produire la même sortie requise. Je pense que c'est la méthode la plus rapide possible (car elle saute par-dessus les cellules au lieu de les scanner).

    rec BuildSpiralIndex(long w, long h, long index = -1)
    {  
        long count = 0 , x = -1,  y = -1, dir = 1, phase=0, pos = 0,                            length = 0, totallength = 0;
        bool isVertical = false;
        if(index>=(w*h)) return null;

        do 
        {                
            isVertical = (count % 2) != 0;
            length = (isVertical ? h : w) - count/2 - count%2 ;
            totallength += length;
            count++;
        } while(totallength<index);

        count--; w--; h--;
        phase = (count / 4); pos = (count%4);
        x = (pos > 1 ? phase : w - phase);
        y = ((pos == 1 || pos == 2) ? h - phase : phase) + (1 * (pos == 3 ? 1 : 0));
        dir = pos > 1 ? -1 : 1;
        if (isVertical) y -= (totallength - index - 1) * dir;
        else x -= (totallength - index -1) * dir;
        return new rec { X = x, Y = y };
    }

Python bouclant le code en spirale dans le sens des aiguilles d'une montre en utilisant la réponse Can Berk Güder .

def spiral(X, Y):
    x = y = 0
    dx = 0
    dy = 1
    for i in range(max(X, Y)**2):
        if (-X/2 < x <= X/2) and (-Y/2 < y <= Y/2):
            print (x, y)
            # DO STUFF...
        if x == -y or (x < 0 and x == y) or (x > 0 and x-1 == y):
            dx, dy = dy, -dx
        x, y = x+dx, y+dy

L'excellente solution de Davidont dans VB.Net

    Public Function Spiral(n As Integer) As RowCol
    ' given n an index in the squared spiral
    ' p the sum of point in inner square
    ' a the position on the current square
    ' n = p + a
    ' starts with row 0 col -1
    Dim r As Integer = CInt(Math.Floor((Math.Sqrt(n + 1) - 1) / 2) + 1)

    ' compute radius : inverse arithmetic sum of 8+16+24+...=
    Dim p As Integer = (8 * r * (r - 1)) \ 2
    ' compute total point on radius -1 : arithmetic sum of 8+16+24+...

    Dim en As Integer = r * 2
    ' points by face

    Dim a As Integer = (1 + n - p) Mod (r * 8)
    ' compute the position and shift it so the first is (-r,-r) but (-r+1,-r)
    ' so square can connect

    Dim row As Integer
    Dim col As Integer

    Select Case Math.Floor(a \ (r * 2))
        ' find the face : 0 top, 1 right, 2, bottom, 3 left
        Case 0
            row = a - r
            col = -r
        Case 1
            row = r
            col = (a Mod en) - r
        Case 2
            row = r - (a Mod en)
            col = r
        Case 3
            row = -r
            col = r - (a Mod en)
    End Select

    Return New RowCol(row, col)
End Function