Алгоритм нахождения указанной c координаты элемента по спирали

Question

Здесь спираль, числа выровнены таким образом

, а элемент 1 (в центре) расположен в (0,0) Координаты;

2 равно (1,0)

3 равно (1,1)

4 равно (0,1)

5 равно (-1,1)

6 равно (-1,0)

7 равно (-1,-1)

8 равно (0,-1)

9 is (1,-1)

10 is (2,-1)

11 is (2,0) и так далее ...

Мы хотим найти индекс n-й элемент; 73 => (?,?) e.g. 10 => (2,-1)

Я написал этот алгоритм, который имитирует спираль и генерирует всю последовательность с этим числом, поэтому я могу получить координаты нужного элемента; здесь он находится в codepen ; вот фрагмент (наведите курсор на ячейки, чтобы увидеть их указатель)

//-- displaying
document.querySelector("#root").style.display = "flex";
document.querySelector("#root").style.height = "100vh";
document.querySelector("#root").style.justifyContent = "center";
document.querySelector("#root").style.alignItems = "center";

let borderStyle = "red";
let res = maze("list", 73);
//console.log(res);
let rafCounter = 0;
requestAnimationFrame(putItInPlace);


function maze(queryType, n) {
  let directions = ["→", "↑", "←", "↓"];
  let directionChangeCounter = 0;
  let turnLength = 1;
  let latestCell = { x: 0, y: 0, value: 1 };
  let output = [latestCell];
  for (let total = 0; total < n; null) {
    for (let i = 0; i < turnLength && total < n; i++) {
      let newCell = { ...latestCell, value: latestCell.value + 1 };
      switch (directions[directionChangeCounter % 4]) {
        case "→":
          newCell.x = latestCell.x + 1;
          break;
        case "↑":
          newCell.y = latestCell.y + 1;
          break;
        case "←":
          newCell.x = latestCell.x - 1;
          break;
        case "↓":
          newCell.y = latestCell.y - 1;
          break;
        default:
          break;
      }
      latestCell = newCell;
      newCell.DxC = directionChangeCounter * turnLength;
      newCell.isLastInTurn = i + 1 === turnLength;
      newCell.direction = directions[directionChangeCounter % 4];
      newCell.directionChangeCounter = directionChangeCounter;
      output.push(newCell);
      total++;
    }
    directionChangeCounter++;
    if (directionChangeCounter % 2 === 0) {
      turnLength++;
    }
  }
  return output;
}


function putItInPlace() {
  let cell = res[rafCounter];
  let span = document.createElement("span");
  span.textContent = cell.value;
  span.title = `x: ${cell.x} y: ${cell.y} dcc: ${cell.directionChangeCounter}`;
  span.style.position = "absolute";
  span.style.display = "flex";
  span.style.justifyContent = "center";
  span.style.alignItems = "center";
  span.style.border = "2px solid grey";
  span.style.backgroundColor = "grey";
  let size = 30;
  span.style.width = size + "px";
  span.style.height = size + "px";
  if (cell.direction === "←") {
    addBorderTop(span);
    if (cell.isLastInTurn) addBorderLeft(span);
  }
  if (cell.direction === "→") {
    addBorderBottom(span);
    if (cell.isLastInTurn) addBorderRight(span);
  }
  if (cell.direction === "↑") {
    addBorderRight(span);
    if (cell.isLastInTurn) addBorderTop(span);
  }
  if (cell.direction === "↓") {
    addBorderLeft(span);
    if (cell.isLastInTurn) addBorderBottom(span);
  }
  if (cell.value === 1) {
    addBorderBottom(span);
    addBorderTop(span);
    addBorderLeft(span);
  }
  const multplier = 34;
  span.style.transform = `translate(${cell.x * multplier}px, ${
    -cell.y * multplier
  }px)`;
  document.querySelector("#root").appendChild(span);
  rafCounter++;
  if (rafCounter < res.length) {
    requestAnimationFrame(putItInPlace);
  }
}

function addBorderTop(el) {
  el.style.borderTopColor = borderStyle;
}
function addBorderBottom(el) {
  el.style.borderBottomColor = borderStyle;
}
function addBorderRight(el) {
  el.style.borderRightColor = borderStyle;
}
function addBorderLeft(el) {
  el.style.borderLeftColor = borderStyle;
}

<div id="root"></div>

---

Так что есть ли способ найти координаты объекта требуемые элементы без генерация всей последовательности ? может быть решение O(1)? Я не ищу точную реализацию на каком-либо конкретном c языке; Псевдокод просто отлично; заранее спасибо.

Answer 1

Надеюсь, этот код поможет вам. Вы можете найти связь по спиральной функции ..

#include <bits/stdc++.h>

using namespace std;

void spiral(int n) {
    int k = ceil((sqrt(n) - 1) / 2);
    int t = 2 * k + 1;
    int m = pow(t, 2);
    t = t - 1;
    if (n >= m - t) {
        printf("%d %d\n",k - (m - n), -k);
        return;
    }else {
        m = m - t;
    }
    if (n >= m - t) {
       printf("%d %d\n", -k, -k + (m - n));
        return;
    }  else {
        m = m - t;
    }
    if (n >= m - t) {
        printf("%d %d\n", -k + (m - n), k);
        return;
    }
    else {
        printf("%d %d\n",k, k - (m - n - t));
        return;
    }
}


int main()
{
    int n;
    while (scanf("%d", &n) == 1) {
        spiral(n);
    }

    return 0;
}

Посмотрите на это , чтобы лучше понять.

Answer 2

Вот решение O (1), версия принятого ответа javascript;

console.log(spiral(26));

function spiral(n) {
    let k = Math.ceil((Math.sqrt(n) - 1) / 2);
    let t = (2 * k + 1) ;
    let m = Math.pow(t, 2);
    t = t - 1;
    if (n >= m - t) {
        return [k - (m - n), -k];
    }else {
        m = m - t;
    }
    if (n >= m - t) {
       return  [-k, -k + (m - n)];
    }  else {
        m = m - t;
    }
    if (n >= m - t) {
        return  [-k + (m - n), k];
    }
    else {
        return [k,k - (m - n - t)];
    }
}