Zdobądź indeks spirali od lokalizacji

Question

Używam rozwiązanie Alberto Santini na to pytanie, aby uzyskać odwołanie spirala siatki na podstawie indeksu pozycji

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

To nie przyjął rozwiązanie, ale jest to najlepsze dla mojego potrzeby, ponieważ pozwala uniknąć użycia pętli.

Działa dobrze, ale teraz chcę zrobić odwrotność. Na podstawie znanej współrzędnej x i y zwraca indeks lokalizacji.

Jest to prekursor zwracania elementów otaczających daną lokalizację.

Answer 1

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

Opis: Lewy górny semi-przekątna (0-4-16-36-64) zawiera kwadratowy numer warstwy (4 * warstwa^2).Zewnętrzna instrukcja "if" definiuje warstwę i znajduje (wstępny) wynik dla pozycji w odpowiednim wierszu lub kolumnie lewego górnego półpłaszczyzny, a wewnętrzny zwrot "if" koryguje wynik dla pozycji lustrzanej.

Answer 2

Nie wiem, czy istnieje zwięzłe równanie matematyczne do wyprowadzenia tego, co chcesz, ale mam rozwiązanie, które oblicza, co chcesz w O (1) czasie na zapytanie. Żadnych pętli, jakich nie chciałeś.

My podejście:

(i) dla każdego punktu (x, y), wybrać liczbę punktów, które leżą w kwadratu o boku (2 x a-1), gdzie A = Max (| x |, | y |). To są punkty wewnętrzne. tj. liczba punktów leżących we wszystkich spiralach, w tym spirala prądowa.

to jest tylko (2 * -1) * (2 * -1)

Np Rozważmy następujący schemat:

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

W punkcie (2,1) a = 2. Punkty wewnętrzne, oznaczone są tutaj jako 0, 1, 2, 3, 4, 5, 6, 7, 8 - Kwadrat o długości krawędzi 3

(ii) Teraz oblicz punkty leżące na obecna spirala. Spirala ma 4 "narożnych" punkty -

(A) Punkt początkowy (gdzie rozpoczyna się prąd spirala)

(b) punktu (A, A)

(c) punktu (-a, a)

(d) temperaturę (-a, -a)

Więc obliczyć liczbę elementów znajdujących się pomiędzy każdej takiej parze [czyli pomiędzy (a) i (b) (b) i (c), (c) i (d)], tak, że wszystkie te spadają przed wymaganym punktem wejściowym w sekwencji spiralnej. Można tego dokonać przez proste odjęcie współrzędnych punktu.

Ta wartość plus liczba wewnętrznych punktów dadzą wymaganą odpowiedź.

Nie jestem pewien, czy wyjaśniłem to bardzo wyraźnie. Daj mi znać, jeśli potrzebujesz wyjaśnień lub dalszych wyjaśnień.

Załączony jest kod JAVA, który napisałem, aby przetestować moją logikę. Przykro mi, ale to nie jest bardzo elegancki, ale to działa: 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)); 
     } 
    } 

}