Get indice spirale dalla posizione

Question

sto usando la soluzione di Alberto Santini a questa domanda per ottenere una griglia di riferimento a spirale sulla base di un indice articoli

Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin

Non è la soluzione accettata, ma è il meglio per il mio ha bisogno di come evita di usare un ciclo.

Sta funzionando bene, ma quello che voglio ora è fare l'inverso. Sulla base di una coordinata xey nota, restituire l'indice di una posizione.

Questo è come un precursore per restituire gli elementi che circondano una determinata posizione.

Answer 1

codice Pascal:

if y * y >= x * x then begin 
    p := 4 * y * y - y - x; 
    if y < x then 
    p := p - 2 * (y - x) 
end 
else begin 
    p := 4 * x * x - y - x; 
    if y < x then 
    p := p + 2 *(y - x) 
end; 

Descrizione: sinistro superiore semi-diagonale (0-4-16-36-64) contiene il numero di uno strato quadrato (4 * livello^2).L'istruzione if esterna definisce il layer e trova (pre) risultato per la posizione nella riga o colonna corrispondente del semipiano sinistro-superiore e l'istruzione if interna corregge il risultato per la posizione dello specchio.

Answer 2

Non so se esiste un'equazione matematica concisa per ricavare ciò che si desidera, ma ho una soluzione che calcola ciò che si desidera in O (1) tempo per query. Niente loop come volevi.

mio approccio:

(i) Per ogni punto (x, y), per il numero di punti che si trovano nel quadrato di lato (2 * a-1), dove a = Max (| x |, | y |). Questi sono i punti interni. cioè, il numero di punti che giace in tutte le spirali NON include la spirale corrente.

Questo non è altro che (2 * a -1) * (2 * a -1)

Es: Si consideri il seguente schema:

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

Per il punto (2,1), a = 2. I punti interni, qui sono etichettati come 0, 1, 2, 3, 4, 5, 6, 7, 8 - Il quadrato con lunghezza del bordo 3

(ii) Calcolare ora i punti che si trovano sul spirale attuale. La spirale ha 4 "angolo" punti -

(a) Il punto di partenza (dove inizia la spirale corrente)

(b) il punto (a, a)

(c) il punto (-a, a)

(d) il punto (-a, -a)

Quindi, calcolare il numero di elementi che si trovano tra ciascuna di queste coppie [cioè tra (a) e (b), (b) e (c), (c) e (d)], in modo tale che tutti questi elementi cadano prima del punto di ingresso richiesto nella sequenza a spirale. Questo può essere fatto con la semplice sottrazione delle coordinate punto.

Questo valore, oltre al numero di punti interni, fornisce la risposta richiesta.

Non sono sicuro di averlo spiegato molto chiaramente. Fatemi sapere se avete bisogno di chiarimenti o ulteriori spiegazioni.

In allegato è il codice JAVA che ho scritto per testare la mia logica. Mi dispiace ma non è molto elegante, ma funziona: P

import java.io.IOException; 
import java.util.Scanner; 

class Pnt 
{ 
    int x, y; 

    public Pnt(int _x, int _y) 
    { 
     x = _x; 
     y = _y; 
    } 
} 

public class Spiral 
{ 

    static int interior(Pnt p) // returns points within interior square of side length MAX(x, y) - 1 
    { 
     int a = Math.max(Math.abs(p.x), Math.abs(p.y)); 
     return (2*a - 1)*(2*a - 1); 
    } 


    static Pnt startPnt(Pnt p) // first point in that spiral 
    { 
     int a = Math.max(Math.abs(p.x), Math.abs(p.y)); 

     // last pnt in prev spiral = [ a-1, -(a-1) ] 

     // next pnt = [ a, -(a-1) ] 

     return new Pnt(a, -(a-1)); 
    } 

    static int offSetRow1(Pnt pStart, Pnt p) 
    { 

     return (p.y - pStart.y) + 1; 
    } 



    static int solve(Pnt curr) 
    { 
     // check location of curr 
     // It may lie on 1st row, 2nd row, 3rd or 4th row 

     int a = Math.max(Math.abs(curr.x), Math.abs(curr.y)); 
     int off=0; 
     int interiorCnt = interior(curr); 
     Pnt start = startPnt(curr); 

     if((curr.x == a) && (curr.y >= start.y)) // row 1 
     { 
      off = offSetRow1(start, curr); 
      return off+interiorCnt; 
     } 

     if(curr.y == a) // row 2 
     { 
      Pnt start2 = new Pnt(a, a); 
      int off1 = offSetRow1(start, start2); 

      // now add diff in x-coordinates 

      int off2 = start2.x - curr.x; 
      off = off1 + off2; 
      return off+interiorCnt; 

     } 

     if(curr.x == -a) // row 3 
     { 
      Pnt start2 = new Pnt(a, a); 
      int off1 = offSetRow1(start, start2); 

      // now add diff in x-coordinates 

      Pnt start3 = new Pnt(-a, a); 
      int off2 = start2.x - start3.x; 

      // now add diff in y co-ordinates 


      int off3 = start3.y - curr.y; 

      off = off1 + off2 + off3; 
      return off+interiorCnt; 

     } 

     else // row 4 
     { 
      Pnt start2 = new Pnt(a, a); 
      int off1 = offSetRow1(start, start2); 

      // now add diff in x-coordinates 

      Pnt start3 = new Pnt(-a, a); 
      int off2 = start2.x - start3.x; 

      // now add diff in y co-ordinates 


      int off3 = start3.y - curr.y; 

      Pnt start4 = new Pnt(-a, -a); 

      // add diff in x co-ordinates 

      int off4 = curr.x - start4.x; 
      off = off1 + off2 + off3 + off4; 
      return interiorCnt + off; 
     } 


    } 

    public static void main(String[] args) throws IOException 
    { 
     Scanner s = new Scanner(System.in); 

     while(true) 
     { 
      int x = s.nextInt(); 
      int y = s.nextInt(); 

      Pnt curr = new Pnt(x, y); 
      System.out.println(solve(curr)); 
     } 
    } 

}