Algoritmo per iterazione su una spirale verso l'esterno su una griglia 2D discreta dall'origine

Question

Ad esempio, ecco la forma di spirale inteso (e ogni passo dell'iterazione)

  y 
      | 
      | 
    16 15 14 13 12 
    17 4 3 2 11 
-- 18 5 0 1 10 --- x 
    19 6 7 8 9 
    20 21 22 23 24 
      | 
      | 

Quando le linee sono x e y assi.

Qui sarebbero i valori effettivi l'algoritmo avrebbe "ritorno" con ogni iterazione (le coordinate dei punti):

[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,2], [1,2], [0,2], [-1,2], [-2,2], [-2,1], [-2,0].. 

ecc

Ho provato a cercare, ma sono non sono proprio sicuro di cosa cercare esattamente, e quali ricerche ho provato hanno trovato un vicolo cieco.

Non sono nemmeno sicuro da dove iniziare, a parte qualcosa di disordinato e poco elegante e ad-hoc, come creare/codificare una nuova spirale per ogni livello.

Qualcuno può aiutarmi a iniziare?

Inoltre, c'è un modo che può facilmente passare da senso orario a senso antiorario (l'orientamento) e da quale direzione "avviare" la spirale? (la rotazione)

Inoltre, c'è un modo per farlo in modo ricorsivo?

---

La mia applicazione

Ho una griglia sparsa pieno di punti di dati, e voglio aggiungere un nuovo punto di dati alla rete, e l'abbiano in essere "il più vicino possibile" ad un dato un altro punto.

Per fare ciò, chiamerò grid.find_closest_available_point_to(point), che andrà a scorrere sulla spirale sopra riportata e restituirà la prima posizione che è vuota e disponibile.

Quindi, per prima cosa, controlla point+[0,0] (solo per completezza). Quindi controllerà point+[1,0]. Quindi controllerà point+[1,1]. Quindi point+[0,1], ecc. E restituire il primo per il quale la posizione nella griglia è vuota (o non occupata già da un punto dati).

Nessun limite superiore alla dimensione della griglia.

Answer 1

Non c'è niente di sbagliato con la soluzione diretta "ad-hoc". Anche questo può essere abbastanza pulito.
Basta notare che la spirale è costruita da segmenti. E puoi ottenere il segmento successivo da quello attuale ruotandolo di 90 gradi. E ogni due rotazioni, la lunghezza del segmento cresce di 1.

modificare Illustrazione, quei segmenti numerati

... 11 10 
7 7 7 7 6 10 
8 3 3 2 6 10 
8 4 . 1 6 10 
8 4 5 5 5 10 
8 9 9 9 9 9 

.

// (di, dj) is a vector - direction in which we move right now 
    int di = 1; 
    int dj = 0; 
    // length of current segment 
    int segment_length = 1; 

    // current position (i, j) and how much of current segment we passed 
    int i = 0; 
    int j = 0; 
    int segment_passed = 0; 
    for (int k = 0; k < NUMBER_OF_POINTS; ++k) { 
     // make a step, add 'direction' vector (di, dj) to current position (i, j) 
     i += di; 
     j += dj; 
     ++segment_passed; 
     System.out.println(i + " " + j); 

     if (segment_passed == segment_length) { 
      // done with current segment 
      segment_passed = 0; 

      // 'rotate' directions 
      int buffer = di; 
      di = -dj; 
      dj = buffer; 

      // increase segment length if necessary 
      if (dj == 0) { 
       ++segment_length; 
      } 
     } 
    } 

Per cambiare direzione originale, guarda valori originali di di e dj. Per cambiare la rotazione in senso orario, vedere come questi valori vengono modificati.

Answer 2

Provare a cercare equazioni parametriche o polari. Entrambi sono adatti a tramare a spirale cose. Here's a page che ha un sacco di esempi, con immagini (e equazioni). Dovrebbe darti qualche idea in più su cosa cercare.

Answer 3

Ho fatto praticamente lo stesso sottile di un allenamento, con alcune differenze nell'output e l'orientamento a spirale, e con un requisito in più, che la complessità spaziale delle funzioni deve essere O (1).

Dopo aver pensato per un po 'mi sono reso conto che sapendo da dove inizia la spirale e la posizione per cui stavo calcolando il valore, avrei potuto semplificare il problema sottraendo tutti i "cerchi" completi della spirale, e quindi basta calcolare un valore più semplice.

Qui è la mia implementazione di tale algoritmo in Ruby:

def print_spiral(n) 
    (0...n).each do |y| 
    (0...n).each do |x| 
     printf("%02d ", get_value(x, y, n)) 
    end 
    print "\n" 
    end 
end 


def distance_to_border(x, y, n) 
    [x, y, n - 1 - x, n - 1 - y].min 
end 

def get_value(x, y, n) 
    dist = distance_to_border(x, y, n) 
    initial = n * n - 1 

    (0...dist).each do |i| 
    initial -= 2 * (n - 2 * i) + 2 * (n - 2 * i - 2) 
    end   

    x -= dist 
    y -= dist 
    n -= dist * 2 

    if y == 0 then 
    initial - x # If we are in the upper row 
    elsif y == n - 1 then 
    initial - n - (n - 2) - ((n - 1) - x) # If we are in the lower row 
    elsif x == n - 1 then 
    initial - n - y + 1# If we are in the right column 
    else 
    initial - 2 * n - (n - 2) - ((n - 1) - y - 1) # If we are in the left column 
    end 
end 

print_spiral 5 

Questo non è esattamente la cosa che hai chiesto, ma credo che vi aiuterà a pensare il vostro problema

Answer 4

Questo problema è meglio compreso analizzando come cambia le coordinate degli spigoli a spirale. Considerate questo tavolo di primi 8 curve a spirale (esclusa origine):

 
x,y | dx,dy | k-th corner | N | Sign | 
___________________________________________ 
1,0 | 1,0 | 1   | 1 | + 
1,1 | 0,1 | 2   | 1 | + 
-1,1 | -2,0 | 3   | 2 | - 
-1,-1 | 0,-2 | 4   | 2 | - 
2,-1 | 3,0 | 5   | 3 | + 
2,2 | 0,3 | 6   | 3 | + 
-2,2 | -4,0 | 7   | 4 | - 
-2,-2 | 0,-4 | 8   | 4 | - 

Guardando a questo tavolo possiamo calcolare X, Y dell'angolo k-esimo dato X, Y di angolo (k-1):

Ora quando si conoscono le coordinate di k e k + 1 spigolo a spirale è possibile ottenere tutti i punti dati tra k e k + 1 semplicemente aggiungendo 1 o -1 a x o y dell'ultimo punto. Ecco fatto.

buona fortuna.

Answer 5

Lo risolverei usando un po 'di matematica. Ecco il codice Ruby (con input e output):

(0..($*.pop.to_i)).each do |i| 
    j = Math.sqrt(i).round 
    k = (j ** 2 - i).abs - j 
    p = [k, -k].map {|l| (l + j ** 2 - i - (j % 2)) * 0.5 * (-1) ** j}.map(&:to_i) 
    puts "p => #{p[0]}, #{p[1]}" 
end 

E.g.

$ ruby spiral.rb 10 
p => 0, 0 
p => 1, 0 
p => 1, 1 
p => 0, 1 
p => -1, 1 
p => -1, 0 
p => -1, -1 
p => 0, -1 
p => 1, -1 
p => 2, -1 
p => 2, 0 

E golfed versione:

p (0..$*.pop.to_i).map{|i|j=Math.sqrt(i).round;k=(j**2-i).abs-j;[k,-k].map{|l|(l+j**2-i-j%2)*0.5*(-1)**j}.map(&:to_i)} 

Modifica

primo tentativo di affrontare il problema in modo funzionale. Che cosa è necessario sapere, ad ogni passo, per passare al prossimo passo?

Concentrarsi sulla prima diagonale del piano x = y. k ti dice quanti passi devi compiere prima di toccarlo: i valori negativi significano che devi spostare i passi abs(k) verticalmente, mentre quelli positivi devi spostare i passi k orizzontalmente.

Ora concentrarsi sulla lunghezza del segmento in cui ci si trova attualmente (i vertici della spirale - quando l'inclinazione dei segmenti cambia - sono considerati parte del segmento "successivo"). È 0 la prima volta, quindi 1 per i prossimi due segmenti (= 2 punti), quindi 2 per i prossimi due segmenti (= 4 punti), ecc. Cambia ogni due segmenti e ogni volta il numero di punti parte di tali segmenti aumentare. Questo è quello che viene usato per j.

Accidentalmente, questo può essere utilizzato per ottenere un altro po 'di informazioni: (-1)**j è solo una scorciatoia per "1 se si sta diminuendo alcune coordinate per arrivare a questo passo, -1 se si sta aumentando" (Si noti che una sola la coordinata è cambiata ad ogni passo). Stesse riserve per j%2, basta sostituire 1 con 0 e -1 con 1 in questo caso. Questo significa che si scambiano tra due valori: uno per i segmenti "heading" su o right e uno per quelli che vanno giù o sinistra.

Questo è un ragionamento familiare, se sei abituato alla programmazione funzionale: il resto è solo un po 'di matematica semplice.

Answer 6

Questa è la soluzione javascript in base alla risposta al Looping in a spiral

var x = 0, 
    y = 0, 
    delta = [0, -1], 
    // spiral width 
    width = 6, 
    // spiral height 
    height = 6; 


for (i = Math.pow(Math.max(width, height), 2); i>0; i--) { 
    if ((-width/2 < x && x <= width/2) 
      && (-height/2 < y && y <= height/2)) { 
     console.debug('POINT', x, y); 
    } 

    if (x === y 
      || (x < 0 && x === -y) 
      || (x > 0 && x === 1-y)){ 
     // change direction 
     delta = [-delta[1], delta[0]]    
    } 

    x += delta[0]; 
    y += delta[1];   
} 

violino: http://jsfiddle.net/N9gEC/18/

Answer 7

Ecco una pugnalata a esso in C++, un iteratore stateful.

class SpiralOut{ 
protected: 
    unsigned layer; 
    unsigned leg; 
public: 
    int x, y; //read these as output from next, do not modify. 
    SpiralOut():layer(1),leg(0),x(0),y(0){} 
    void goNext(){ 
     switch(leg){ 
     case 0: ++x; if(x == layer) ++leg;    break; 
     case 1: ++y; if(y == layer) ++leg;    break; 
     case 2: --x; if(-x == layer) ++leg;    break; 
     case 3: --y; if(-y == layer){ leg = 0; ++layer; } break; 
     } 
    } 
}; 

Dovrebbe essere efficiente quanto basta.

Answer 8

Ho avuto un problema simile, ma non volevo ripetere l'intera spirale ogni volta per trovare la nuova coordinata successiva. Il requisito è che tu conosca le tue ultime coordinate.

Ecco quello che mi è venuta con un sacco di lettura su altre soluzioni:

function getNextCoord(coord) { 

    // required info 
    var x  = coord.x, 
     y  = coord.y, 
     level = Math.max(Math.abs(x), Math.abs(y)); 
     delta = {x:0, y:0}; 

    // calculate current direction (start up) 
    if (-x === level) 
     delta.y = 1; // going up 
    else if (y === level) 
     delta.x = 1; // going right 
    else if (x === level)   
     delta.y = -1; // going down 
    else if (-y === level) 
     delta.x = -1; // going left 

    // check if we need to turn down or left 
    if (x > 0 && (x === y || x === -y)) { 
     // change direction (clockwise) 
     delta = {x: delta.y, 
       y: -delta.x}; 
    } 

    // move to next coordinate 
    x += delta.x; 
    y += delta.y; 

    return {x: x, 
      y: y}; 
} 

coord = {x: 0, y: 0} 
for (i = 0; i < 40; i++) { 
    console.log('['+ coord.x +', ' + coord.y + ']'); 
    coord = getNextCoord(coord); 

} 

Ancora non è sicuro se è la soluzione più elegante. Forse qualche elegante matematica potrebbe rimuovere alcune delle affermazioni if. Alcune limitazioni richiederebbero alcune modifiche per cambiare la direzione della spirale, non tengono conto delle spirali non quadrate e non possono spostarsi a spirale attorno a una coordinata fissa.

Answer 9

Ecco l'algoritmo. Ruota in senso orario, ma potrebbe facilmente ruotare in senso antiorario, con alcune modifiche. L'ho fatto in meno di un'ora.

// spiral_get_value(x,y); 
sx = argument0; 
sy = argument1; 
a = max(sqrt(sqr(sx)),sqrt(sqr(sy))); 
c = -b; 
d = (b*2)+1; 
us = (sy==c and sx !=c); 
rs = (sx==b and sy !=c); 
bs = (sy==b and sx !=b); 
ls = (sx==c and sy !=b); 
ra = rs*((b)*2); 
ba = bs*((b)*4); 
la = ls*((b)*6); 
ax = (us*sx)+(bs*-sx); 
ay = (rs*sy)+(ls*-sy); 
add = ra+ba+la+ax+ay; 
value = add+sqr(d-2)+b; 
return(value);` 

Gestirà qualsiasi valore x/y (infinito).

È scritto in GML (Game Maker Language), ma la logica effettiva è valida in qualsiasi linguaggio di programmazione.

L'algoritmo a riga singola ha solo 2 variabili (sx e sy) per gli ingressi x e y. Ho praticamente allargato le parentesi, molto. Ti rende più facile incollarlo nel blocco note e cambiare 'sx' per il tuo argomento x/nome della variabile e 'sy' per il tuo argomento y/nome della variabile.

`// spiral_get_value(x,y); 

sx = argument0; 
sy = argument1; 

value = ((((sx==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sy !=(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy))))))*((max(sqrt(sqr(sx)),sqrt(sqr(sy))))*2))+(((sy==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sx !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*((max(sqrt(sqr(sx)),sqrt(sqr(sy))))*4))+(((sx==(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy)))) and sy !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*((max(sqrt(sqr(sx)),sqrt(sqr(sy))))*6))+((((sy==(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy)))) and sx !=(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy))))))*sx)+(((sy==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sx !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*-sx))+(((sx==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sy !=(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy))))))*sy)+(((sx==(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy)))) and sy !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*-sy))+sqr(((max(sqrt(sqr(sx)),sqrt(sqr(sy)))*2)+1)-2)+max(sqrt(sqr(sx)),sqrt(sqr(sy))); 

return(value);` 

So che la risposta è terribilmente in ritardo: D ma spero che aiuti i futuri visitatori.

Answer 10

Ho un algoritmo in java che emette un output simile al tuo, tranne che dà la priorità al numero a destra, quindi il numero a sinistra.

public static String[] rationals(int amount){ 
    String[] numberList=new String[amount]; 
    int currentNumberLeft=0; 
    int newNumberLeft=0; 
    int currentNumberRight=0; 
    int newNumberRight=0; 
    int state=1; 
    numberList[0]="("+newNumberLeft+","+newNumberRight+")"; 
    boolean direction=false; 
for(int count=1;count<amount;count++){ 
    if(direction==true&&newNumberLeft==state){direction=false;state=(state<=0?(-state)+1:-state);} 
    else if(direction==false&&newNumberRight==state){direction=true;} 
    if(direction){newNumberLeft=currentNumberLeft+sign(state);}else{newNumberRight=currentNumberRight+sign(state);} 
    currentNumberLeft=newNumberLeft; 
    currentNumberRight=newNumberRight; 
    numberList[count]="("+newNumberLeft+","+newNumberRight+")"; 
} 
return numberList; 
}