Обход двумерного массива под углом

Question

Обычно мы пересекаем массив по строкам или столбцам, но здесь я хочу пересечь его под углом.Я попытаюсь объяснить, что я имею в виду. Допустим, если угол равен 45 градусам, то вместо строки за столбцом он будет искать как (0,0), тогда (0,1) (1,0), так и (0,2)., (1,1), (2,0) и т. Д. (Извините, не удалось загрузить изображение, так как я новый пользователь и не могу этого сделать, возможно, попробуйте представить себе / нарисовать массив, который поможет получитьчто я пытаюсь сказать) Но что произойдет, если пользователь введет угол около 20 градусов, как мы можем определить, как искать в массиве.

я просто хотел узнать, есть ли какой-нибудь алгоритм, который делает что-то похожее на это?Язык программирования не проблема, я думаю, проблема скорее в алгоритме.Любые идеи будут приветствоваться.Пожалуйста, не стесняйтесь спрашивать, если я не могу четко объяснить, что я ищу.

Спасибо, ребята.

Answer 1

Легко. Возьми угол (скажем, 45). Это соответствует вектору v=(1, 1) в вашем случае. (Это может быть нормализовано к унитарному вектору (sqrt(2)/2, sqrt(2)/2), но это не обязательно)

Для каждой отдельной точки в вашем массиве у вас есть их координаты (x, y). Просто сделайте скалярное произведение этих координат на вектор. Давайте назовем f(x, y) = scalarProduct((x, y), v)

Сортируйте значения f(x, y), и вы получите "обход", который вы ищете!

---

Реальный пример. Ваша матрица 3х3 Скалярные продукты:

(0,0). (1,1) = 0

(0,1). (1,1) = 1

(0,2). (1,1) = 2

(1,0). (1,1) = 1

(1,1). (1,1) = 2

(1,2). (1,1) = 3

(2,0). (1,1) = 2

(2,1). (1,1) = 3

(2,2). (1,1) = 4

Если вы заказываете эти скалярные произведения в порядке возрастания, вы получаете порядок (0,0), (1,0), (1,0), (2,0), (1,1), (0, 2), (2,1) ...

---

А если вы хотите сделать это с углом 20, замените все вхождения v=(1, 1) на v=(cos(20), sin(20))

---

Вот иллюстрация геометрической интерпретации. Скалярные произведения соответствуют пересечению вектора v (красным) с синими линиями.

Answer 2

Для каждой начальной точки (самой левой точки каждой строки) используйте тригонометрию, чтобы определить конечную точку для данного угла.Загар (угол) определяется как (разность высот / ширина массива), поэтому ваша разность высот равна загару (угол) * (с массивом).Вы должны рассчитать разницу высот только один раз.Если разница y + высота больше, чем высота массива, просто вычтите высоту (или используйте оператор по модулю).

Теперь, когда у вас есть начальная точка и конечная точка, вы можете использовать алгоритм Брезенхэма, чтобы определитьточки между: http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

Answer 3

Вы хотите найти кривую заполнения пространства, например, кривую Мортона или Z-кривую. Если вы хотите разделить массив на 4 фрагмента, вы можете искать кривую Гильберта или кривую Мура.