Algorytm iteracji nad zewnątrz spirali na dyskretnej siatce 2D od początku

Question

Na przykład, tutaj kształt zamierzonego spirali (a każdy etap iteracji)

  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 
      | 
      | 

Jeżeli linie X i y osie.

Tutaj byłoby rzeczywiste wartości algorytm będzie „powrót” z każdej iteracji (współrzędne punktów):

[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].. 

itp

próbowałem poszukiwania, ale jestem Nie wiem dokładnie, czego dokładnie szukać, a jakie wyszukiwania próbowałem wymyślić ślepych zaułków.

Nie jestem nawet pewien, od czego zacząć, poza czymś nieporządnym, nieeleganckim i ad-hoc, jak tworzenie/kodowanie nowej spirali dla każdej warstwy.

Czy ktoś może mi pomóc zacząć?

Czy istnieje sposób, który można łatwo przełączać w kierunku zgodnym lub przeciwnym do ruchu wskazówek zegara (orientacja) i w którym kierunku "rozpocząć" spiralę? (obrót)

Czy istnieje sposób na rekursywne robienie tego?

---

Moja aplikacja

mam rzadką siatkę wypełnioną punktów danych, a chcę, aby dodać nowy punkt danych do sieci i mają być „tak blisko, jak to możliwe” Do podany inny punkt.

Aby to zrobić, zadzwonię pod numer grid.find_closest_available_point_to(point), który przejdzie przez spiralę podaną powyżej i zwróci pierwszą pozycję, która jest pusta i dostępna.

Po pierwsze, sprawdzi to point+[0,0] (tylko ze względu na kompletność). To sprawdzi point+[1,0]. To sprawdzi point+[1,1]. Następnie point+[0,1] itd. Zwróć pierwszą, dla której pozycja w siatce jest pusta (lub nie zajęta już przez punkt danych).

Nie ma górnej granicy do rozmiaru siatki.

Answer 1

Nie ma nic złego w bezpośrednim, "ad-hoc" rozwiązaniu. Może też być wystarczająco czysty.
Po prostu zauważ, że spirala jest zbudowana z segmentów. I możesz uzyskać następny segment od bieżącego obracając go o 90 stopni. Każde dwa obroty, długość segmentu rośnie o 1.

edit Ilustracje te odcinki numerowane

... 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; 
      } 
     } 
    } 

Aby zmienić pierwotny kierunek, spojrzeć na oryginalnych wartościach di i dj. Aby przełączyć obrót zgodnie z ruchem wskazówek zegara, zobacz, jak te wartości są modyfikowane.

Answer 2

Spróbuj wyszukać równania parametryczne lub biegunowe. Oba są odpowiednie do drukowania spiralnych rzeczy. Here's a page który ma wiele przykładów, ze zdjęciami (i równaniami). Powinien dać ci więcej pomysłów na to, czego szukać.

Answer 3

Zrobiłem prawie tak samo cienki jak ćwiczenie treningowe, z pewnymi różnicami w wynikach i orientacji spiralnej, oraz z dodatkowym wymogiem, że funkcje złożoności przestrzennej muszą być O (1).

Po chwili namysłu doszedłem do wniosku, że wiedząc skąd zaczyna się spirala i pozycja, dla której obliczałem wartość, mogłem uprościć problem, odejmując wszystkie pełne "okręgi" spirali, oraz następnie obliczyć prostszą wartość.

Oto moja implementacja tego algorytmu w 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 

To nie jest dokładnie to, co prosiłeś, ale wierzę, że to pomoże ci myśleć problem

Answer 4

Ten problem jest najlepiej zrozumieć, analizując, jak zmienia współrzędne spiralnych narożników. Rozważmy tę tabelę pierwszych 8 spiralnych rogach (z wyłączeniem pochodzenia):

 
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 | - 

Patrząc na tej tabeli możemy obliczyć X, Y z k-tym rogu podano X, Y (k-1) rogu:

 
N = INT((1+k)/2) 
Sign = | +1 when N is Odd 
     | -1 when N is Even 
[dx,dy] = | [N*Sign,0] when k is Odd 
      | [0,N*Sign] when k is Even 
[X(k),Y(k)] = [X(k-1)+dx,Y(k-1)+dy] 

Teraz, gdy znasz współrzędne spirali k i k + 1, możesz uzyskać wszystkie punkty danych pomiędzy k i k + 1, po prostu dodając 1 lub -1 do x lub y ostatniego punktu. To to.

powodzenia.

Answer 5

Rozwiążę to za pomocą jakiejś matematyki. Oto kod Ruby (z wejściem i wyjściem):

(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 

I golfed wersja:

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)} 

Edit

najpierw spróbować podejść do problemu funkcjonalnie. Co musisz wiedzieć na każdym etapie, aby przejść do następnego kroku?

Skoncentruj się na pierwszej przekątnej samolotu x = y. k informuje, ile kroków należy wykonać przed dotknięciem: wartości ujemne oznaczają, że musisz przenieść abs(k) kroków w pionie, podczas gdy wartość dodatnia oznacza, że ​​musisz przesunąć poziomy w poziomie o k.

Teraz skup się na długości segmentu, w którym aktualnie się znajdujesz (wierzchołki spirali - gdy zmienia się nachylenie segmentów - są traktowane jako część "następnego" segmentu). Za pierwszym razem jest 0, następnie 1 dla następnych dwóch segmentów (= 2 punkty), następnie 2 dla następnych dwóch segmentów (= 4 punkty) itp. Zmienia co dwa segmenty i za każdym razem liczba punktów części tych segmentów zwiększać. Do tego służy j.

Przypadkowo, to może być wykorzystane do uzyskania innego bit informacji: (-1)**j jest tylko skrótem do „1 jeśli zmniejszając niektóre koordynować aby dostać się do tego kroku; -1 jeśli wzrasta” (Uwaga: tylko jeden współrzędna zmienia się na każdym etapie). To samo dotyczy j%2, po prostu zamień 1 na 0 i -1 z 1 w tym przypadku. Oznacza to, że zamieniają się między dwiema wartościami: jedną dla segmentów "z nagłówkiem" w górę lub w prawo i jedną dla osób schodzących lub opuszczonych.

Jest to znane rozumowanie, jeśli jesteś przyzwyczajony do programowania funkcjonalnego: reszta to tylko odrobina prostej matematyki.

Answer 6

Jest to rozwiązanie oparte na javascript odpowiedź na 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];   
} 

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

Answer 7

Oto stab na to w C++, a stanowego iteracyjnej.

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; 
     } 
    } 
}; 

Powinien być tak wydajny, jak to tylko możliwe.

Answer 8

Miałem podobny problem, ale nie chciałem pętać całej spirali za każdym razem, aby znaleźć następną nową współrzędną. Wymagane jest, abyś znał ostatnią współrzędną.

Oto co wymyśliłem z dużo czytania na innych rozwiązań:

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); 

} 

Nadal nie wiem, czy to jest najbardziej eleganckie rozwiązanie. Być może niektóre eleganckie matematyki mogą usunąć niektóre z instrukcji if. Niektóre ograniczenia wymagałyby jakiejś modyfikacji, aby zmienić kierunek spirali, nie uwzględniają nie-kwadratowych spiral i nie mogą obracać się wokół ustalonej współrzędnej.

Answer 9

Oto algorytm. Obraca się zgodnie z ruchem wskazówek zegara, ale może się łatwo obracać w kierunku przeciwnym do ruchu wskazówek zegara, z kilkoma zmianami. Zrobiłem to w niecałą godzinę.

// 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);` 

Będzie obsłużyć dowolne wartości x/y (nieskończone).

Jest napisany w GML (Game Maker Language), ale rzeczywista logika jest dźwiękiem w dowolnym języku programowania.

Algorytm jednoliniowy ma tylko dwie zmienne (sx i sy) dla wejść x i y. Zasadniczo rozszerzyłem nawiasy, dużo. Ułatwia to wklejenie go do notatnika i zmianę "sx" dla twojego x argument/nazwa zmiennej i "sy" dla twojego argumentu y/nazwa zmiennej.

`// 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);` 

Wiem, że odpowiedź jest spóźniona: D, ale mam nadzieję, że pomoże to przyszłym odwiedzającym.

Answer 10

Mam algorytm w java, który wyprowadza podobne wyjście do twojego, z tym wyjątkiem, że priorytetem jest numer po prawej, a następnie numer po lewej.

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; 
}