Obtener índice de espiral desde la ubicación

Question

estoy usando solución de Alberto Santini a esta pregunta para obtener una referencia de la rejilla en espiral sobre la base de un índice de artículos

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

no es la solución aceptada, pero es lo mejor para mi necesidades ya que evita el uso de un bucle.

Está funcionando bien, pero lo que quiero ahora es hacer lo contrario. En función de una coordenada xey conocida, devuelva el índice de una ubicación.

Esto es como un precursor para devolver los artículos que rodean una ubicación determinada.

Answer 1

código de 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; 

Descripción: superior izquierdo semi-diagonal (0-4-16-36-64) contiene un número de capa cuadrada (4 * capa^2).La instrucción if externa define la capa y encuentra el resultado (pre) para la posición en la fila o columna correspondiente del semiplano superior izquierdo, y la instrucción if interna corrige el resultado para la posición del espejo.

Answer 2

No sé si hay una ecuación matemática concisa para obtener lo que desea, pero tengo una solución que calcula lo que desea en O (1) tiempo por consulta. No hay bucles como tú querías.

Mi enfoque:

(I) para cualquier punto dado (x, y), encontrar el número de puntos que se encuentran en la plaza de longitud de lado (2 * a-1), donde a = Max (| x |, | y |). Estos son los puntos interiores. es decir, la cantidad de puntos que se encuentran en todas las espirales, NO incluye la espiral actual.

Esto no es sino (2 * a -1) * (2 * a -1)

Ej: Consideremos el siguiente diagrama:

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

Para el punto (2,1), a = 2. Los puntos interiores, aquí están etiquetados como 0, 1, 2, 3, 4, 5, 6, 7, 8 - El cuadrado con la longitud del borde 3

(ii) Ahora calcule los puntos en el espiral actual. La espiral tiene 4 "esquina" puntos -

(a) El punto de partida (donde comienza la espiral actual)

(b) el punto (a, a)

(c) el punto (-a, a)

(d) el punto (-a, -a)

Por lo tanto, calcular el número de elementos que se encuentran entre cada par [es decir, entre (a) y (b), (b) y (c), (c) y (d)], de modo que todos estos caen antes del punto de entrada requerido en la secuencia en espiral. Esto se puede hacer por simple resta de coordenadas de punto.

Este valor, más el número de puntos interiores le dará la respuesta requerida.

No estoy seguro de haber explicado esto muy claramente. Avíseme si necesita alguna aclaración o explicación adicional.

Adjunto está el código JAVA que escribí para probar mi lógica. Lo siento, pero no es muy elegante, pero funciona: 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)); 
     } 
    } 

}