Квадратная спираль с шагом

Question

Мне необходимо рассчитать некоторую точку на плоскости по спирали, тоесть я хочу создать такую функцию, которая на вход получает целое число >=0 и возвращает на выходе целые координаты точки (расстояние между точками контролируется множителем). Также направление выхода из центра не имеет значения. Иллюстрация для примера:

Я находил формулы квадратной спирали, но все они создают непрерывную линию.

Функцию желательно реализовать на kotlin или JavaScript, но подойдёт и любой псевдокод. И это не должен быть цикл, перебирающий все точки.

Answer 1

Можно так:

const getCoordsInSpiralByStepNumber = (stepNumber) => {
  const stepSize = 2;
  const currentCoords = {
    x: 0,
    y: 0
  };
  /*
    h: 1 - up; -1 - down
    v: 1 - right; -1 - left
  */
  const currentDirection = {
    h: 1,
    v: 1
  };
  const firstStepIsVertical = true; // false if first step is horizontal

  const switchHDirection = () => currentDirection.h = currentDirection.h === 1 ? -1 : 1;
  const switchVDirection = () => currentDirection.v = currentDirection.v === 1 ? -1 : 1;

  let currentWidth = 1;
  let currentHeight = 1;

  const moveVertical = () => {
    for (let i = 0; i < currentHeight && stepNumber !== 0; ++i, --stepNumber) {
      currentCoords.y += currentDirection.h * stepSize;
    }

    ++currentHeight;
    switchHDirection();
  }

  const moveHorizontal = () => {
    for (let i = 0; i < currentWidth && stepNumber !== 0; ++i, --stepNumber) {
      currentCoords.x += currentDirection.v * stepSize;
    }

    ++currentWidth;
    switchVDirection();
  }

  if (firstStepIsVertical) {
    while (true) {
      moveVertical();
      if (stepNumber === 0) break;

      moveHorizontal();
      if (stepNumber === 0) break;
    }
  } else {
    while (true) {
      moveHorizontal();
      if (stepNumber === 0) break;

      moveVertical();
      if (stepNumber === 0) break;
    }
  }

  return currentCoords;
}

for (let i = 0; i <= 8; ++i) console.log(getCoordsInSpiralByStepNumber(i));

Единственное то что он не знает о предыдущих шагах, потому заново пересчитывает. Можно этот последний шаг сохранять, чтобы если что продолжить с того же места

Answer 2

Ух, спиральки...

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

49 50 51 52 53 54 55 56
48 25 26 27 28 29 30 
47 24  9 10 11 12 31 
46 23  8  1  2 13 32  
45 22  7  0  3 14 33
44 21  6  5  4 15 34
43 20 19 18 17 16 35     
42 41 40 39 38 37 36

Отсюда вычисляем "полуслой" t, его начало start и положение на горизонтали или на вертикали. Код на Python (// - целочисленное деление) и его выдача

На два координаты домножить нетрудно

import math
def spiralcoord(k):
    t = int(math.sqrt(k))
    start = t * t
    if t%2:
        if k - start <= t:
            return (-(t-1)//2+k-start, -(t+1)//2)
        else:
            return ((t+1)//2, -(t+1)//2 + k - (start + t))
    else:
        if k - start <= t:
            return (t//2-(k-start), t//2)
        else:
            return (-t//2, t//2 -k +(t+start))

for i in range(50):
    print(i, spiralcoord(i))

0 (0, 0)
1 (0, -1)
2 (1, -1)
3 (1, 0)
4 (1, 1)
5 (0, 1)
6 (-1, 1)
7 (-1, 0)
8 (-1, -1)
9 (-1, -2)
10 (0, -2)
11 (1, -2)
12 (2, -2)
13 (2, -1)
14 (2, 0)
15 (2, 1)
16 (2, 2)
17 (1, 2)
18 (0, 2)
19 (-1, 2)
20 (-2, 2)
21 (-2, 1)
22 (-2, 0)
23 (-2, -1)
24 (-2, -2)
25 (-2, -3)
26 (-1, -3)
27 (0, -3)
28 (1, -3)
29 (2, -3)
30 (3, -3)
31 (3, -2)
32 (3, -1)
33 (3, 0)
34 (3, 1)
35 (3, 2)
36 (3, 3)
37 (2, 3)
38 (1, 3)
39 (0, 3)
40 (-1, 3)
41 (-2, 3)
42 (-3, 3)
43 (-3, 2)
44 (-3, 1)
45 (-3, 0)
46 (-3, -1)
47 (-3, -2)
48 (-3, -3)
49 (-3, -4)

Перевод на JS от автора вопроса:

const sspiral = (n, step = 1) => {
  const t = Math.sqrt(n) >> 0
  const start = t * t
  let result = []
  if (t % 2)
    if (n - start <= t) result = [-(t - 1) / 2 + n - start, -(t + 1) / 2]
    else result = [(t + 1) / 2, -(t + 1) / 2 + n - (start + t)]
  else if (n - start <= t) result = [t / 2 - (n - start), t / 2]
  else result = [-t / 2, t / 2 - n + (t + start)]
  return result.map(r => r * step >> 0)
}

БЛОГ НА HUSL

Квадратная спираль с шагом

Ответы (2 шт):