Как заполнить 2D массив по диагонали на основе координат
Я создаю подобный heatmap интерфейс прямоугольной антенной решетки, и я хочу, чтобы 'горячее' местоположение было наверху покинуто массива и 'холодного' местоположения, чтобы быть в нижнем правом. Поэтому мне нужен массив, чтобы быть заполненным по диагонали как это:
0 1 2 3
|----|----|----|----|
0 | 0 | 2 | 5 | 8 |
|----|----|----|----|
1 | 1 | 4 | 7 | 10 |
|----|----|----|----|
2 | 3 | 6 | 9 | 11 |
|----|----|----|----|
Таким образом, на самом деле мне нужна функция f (x, y) таким образом что
f(0,0) = 0
f(2,1) = 7
f(1,2) = 6
f(3,2) = 11
(или, конечно, подобная функция f (n), где f (7) = 10, f (9) = 6, и т.д.).
Наконец, да, я знаю, что этот вопрос подобен тем, которых спрашивают здесь, здесь и здесь, но решения, описанные там только, пересекают и не заполняют матрицу.
4 ответа
Интересная проблема, если вы ограничены просмотром массива строка за строкой. Я разделил прямоугольник на три части. верхний левый треугольник , нижний правый треугольник и ромб в середине .
Для верхнего левого треугольника значения в первом столбце (x = 0) могут быть вычислены с использованием общего арифметического ряда 1 + 2 + 3 + .. + n = n * ( n + 1) / 2 . Поля в этом треугольнике с одинаковым значением x + y находятся на одной диагонали, и здесь значение равно сумме из первого столбца + x.
Тот же подход работает для нижнего правого треугольника . Но вместо x и y , wx и hy используется, где w - ширина, а h высота прямоугольника. Это значение необходимо вычесть из максимального значения w * h-1 в массиве.
Есть два случая для ромбовидной формы посередине . Если ширина прямоугольника больше (или равна) высоте, то нижнее левое поле прямоугольника является полем с наименьшим значением в ромбовидном элементе, и эта сумма может быть вычислена ранее для h-1 . Оттуда вы можете представить, что ромбовидный прямоугольник представляет собой прямоугольник со значением x x + y и значением y y из исходного прямоугольника. Так что вычислить оставшиеся значения в этом новом прямоугольнике несложно.
В другом случае, когда высота больше ширины, то поле в x = w-1 и y = 0 может быть вычислено с использованием этой арифметической суммы, и ромбовидный элемент может быть в виде прямоугольника со значением x x и значением y y- (wx-1) .
Код можно оптимизировать, например, предварительно вычислив значения. Я думаю, что для всех этих случаев тоже есть одна формула. Может быть, я подумаю об этом позже.
inline static int diagonalvalue(int x, int y, int w, int h) {
if (h > x+y+1 && w > x+y+1) {
// top/left triangle
return ((x+y)*(x+y+1)/2) + x;
} else if (y+x >= h && y+x >= w) {
// bottom/right triangle
return w*h - (((w-x-1)+(h-y-1))*((w-x-1)+(h-y-1)+1)/2) - (w-x-1) - 1;
}
// rhomboid in the middle
if (w >= h) {
return (h*(h+1)/2) + ((x+y+1)-h)*h - y - 1;
}
return (w*(w+1)/2) + ((x+y)-w)*w + x;
}
for (y=0; y<h; y++) {
for (x=0; x<w; x++) {
array[x][y] = diagonalvalue(x,y,w,h);
}
}
Конечно, если нет такого ограничения, что-то вроде этого должно быть намного быстрее:
n = w*h;
x = 0;
y = 0;
for (i=0; i<n; i++) {
array[x][y] = i;
if (y <= 0 || x+1 >= w) {
y = x+y+1;
if (y >= h) {
x = (y-h)+1;
y -= x;
} else {
x = 0;
}
} else {
x++;
y--;
}
}
Выполните шаги из 3-го примера - это дает индексы (чтобы распечатать срезы) - и просто установите значение с помощью увеличивающегося счетчика:
int x[3][3];
int n = 3;
int pos = 1;
for (int slice = 0; slice < 2 * n - 1; ++slice) {
int z = slice < n ? 0 : slice - n + 1;
for (int j = z; j <= slice - z; ++j)
x[j][slice - j] = pos++;
}
В матрице M * N значения при обходе, как в указанном вами примере, похоже, увеличиваются на n, за исключением пограничных случаев, поэтому
f(0,0)=0
f(1,0)=f(0,0)+2
f(2,0)=f(1,0)+3
... и так далее до f (N, 0) . Затем
f(0,1)=1
f(0,2)=3
, а затем
f(m,n)=f(m-1,n)+N, where m,n are index variables
и
f(M,N)=f(M-1,N)+2, where M,N are the last indexes of the matrix
Это не решающий момент, но он должен дать вам то, с чем можно поработать. Обратите внимание, что для начала вам нужно только значение предыдущего элемента в каждой строке и несколько начальных значений.
Если вам нужна простая функция, вы можете использовать рекурсивное определение.
H = height
def get_point(x,y)
if x == 0
if y == 0
return 0
else
return get_point(y-1,0)+1
end
else
return get_point(x-1,y) + H
end
end
Это использует тот факт, что любое значение равно H+значение элемента слева от него. Если элемент уже находится в крайнем левом столбце, то вы находите клетку, которая находится в крайнем верхнем правом столбце, двигаетесь влево оттуда и прибавляете 1.
Это хороший шанс использовать динамическое программирование, и "кэшировать" или запоминать функции, которые вы уже выполнили.
Если вы хотите, чтобы что-то "строго" выполнялось f(n), вы можете использовать соотношение:
n = ( n % W , n / H ) [integer division, with no remainder/decimal]
И работать с вашей функцией оттуда.
В качестве альтернативы, если вам нужен чисто метод заполнения массива по строкам, без рекурсии, вы можете следовать следующим правилам:
- Если вы находитесь на первой ячейке строки, "запомните" элемент в ячейке (R-1) (где R - ваша текущая строка) первой строки и добавьте к нему 1.
- В противном случае просто добавьте H к ячейке, которую вы вычислили последней (т.е. к ячейке слева от вас).
Псевдокод: arr[row,column])
arr[0,0] = 0
for R from 0 to H
if R > 0
arr[R,0] = arr[0,R-1] + 1
end
for C from 1 to W
arr[R,C] = arr[R,C-1]
end
end