Получить спиральный индекс от места

Question

Я использую решение Альберто Сантини на этот вопрос, чтобы получить ссылку спирали сетки на основе индекса элемента

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

Это не принято решением, но это лучше для моих поскольку он избегает использования цикла.

Это хорошо работает, но теперь я хочу сделать инверсию. Основываясь на известной координате x и y, возвращайте индекс местоположения.

Это как предшественник для возвращения предметов, связанных с данным местоположением.

Answer 1

Паскаль код:

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; 

Описания: левый верхний пол-диагональ (0-4-16-36-64) содержит квадратный номер слоя (слой 4 *^2).Внешний if-statement определяет слой и находит (pre-) результат для позиции в соответствующей строке или столбце левой верхней полуплоскости, а внутренний if-statement корректирует результат для позиции зеркала.

Answer 2

Я не знаю, есть ли сжатое математическое уравнение для получения того, что вы хотите, но у меня есть решение, которое вычисляет то, что вы хотите в O (1) раз за запрос. Никаких петель, как вы этого хотели.

Мой подход:

(я) для любой данной точке (х, у), найти число точек, которые лежат в квадрате с длиной стороны (2 * а-1), где а = Max (| x |, | y |). Это внутренние точки. т. е. количество точек, лежащих во всех спиралях, не содержащих текущую спираль.

Это не что иное, (2 * -1) * (2 * -1)

Например: Рассмотрим следующую диаграмму:

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

Для точки (2,1), a = 2. Внутренние точки здесь обозначены как 0, 1, 2, 3, 4, 5, 6, 7, 8 - Квадрат с длиной ребра 3

(ii) Теперь вычислите точки, лежащие на текущая спираль. Спираль имеет 4 "угловые" точки -

(а) начальная точка (где начинается ток спираль)

(б) точки (а, а)

(с) в точке (-а, а)

(г) в точке (-a, -a)

Итак, я вычислить число элементов, лежащих между каждой такой пары [то есть, между (а) и (б), (b) и (c), (c) и (d)], так что все они выпадают перед необходимой входной точкой в ​​спиральной последовательности. Это можно сделать простым вычитанием точечных координат.

Это значение, а также количество внутренних точек даст вам необходимый ответ.

Я не уверен, объяснил ли я это очень четко. Дайте мне знать, если вам потребуются какие-либо разъяснения или дополнительные разъяснения.

Прилагается код JAVA, который я написал, чтобы проверить мою логику. Я сожалею, но это не очень элегантно, но он работает: 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)); 
     } 
    } 

}