如何基于坐标对角填充2D数组 [英] How to fill a 2D array diagonally based on coordinates
问题描述
我正在构建类似热图的矩形阵列接口，我希望热"位置在阵列的左上方，而冷"位置在阵列的右下方.因此，我需要像这样对角填充一个数组:
I'm building a heatmap-like rectangular array interface and I want the 'hot' location to be at the top left of the array, and the 'cold' location to be at the bottom right. Therefore, I need an array to be filled diagonally like this:
0 1 2 3
|----|----|----|----|
0 | 0 | 2 | 5 | 8 |
|----|----|----|----|
1 | 1 | 4 | 7 | 10 |
|----|----|----|----|
2 | 3 | 6 | 9 | 11 |
|----|----|----|----|
实际上，我需要这样的函数f(x，y)
So actually, I need a function f(x,y) such that
f(0,0) = 0
f(2,1) = 7
f(1,2) = 6
f(3,2) = 11
(或者，当然是类似的函数f(n)，其中f(7)= 10，f(9)= 6，依此类推).
(or, of course, a similar function f(n) where f(7) = 10, f(9) = 6, etc.).
Finally, yes, I know this question is similar to the ones asked here, here and here, but the solutions described there only traverse and don't fill a matrix.
推荐答案
如果您仅限于逐行浏览数组，则会引起有趣的问题. 我将矩形分为三个区域. 左上三角，右下三角和中间的菱形.
Interesting problem if you are limited to go through the array row by row. I divided the rectangle in three regions. The top left triangle, the bottom right triangle and the rhomboid in the middle.
对于左上三角，可以使用通用算术级数1 + 2 + 3 + .. + n = n*(n+1)/2计算第一列(x = 0)中的值.该三角形中具有相同x + y值的字段在同一对角线中，并且该值是第一个列+ x的和.
For the top left triangle the values in the first column (x=0) can be calculated using the common arithmetic series 1 + 2 + 3 + .. + n = n*(n+1)/2. Fields in the that triangle with the same x+y value are in the same diagonal and there value is that sum from the first colum + x.
相同的方法适用于底部直角三角形.但是使用w-x和h-y代替x和y，其中w是矩形的宽度，而h是矩形的高度.该值必须从数组中的最高值w*h-1中减去.
The same approach works for the bottom right triangle. But instead of x and y, w-x and h-y is used, where w is the width and h the height of rectangle. That value have to be subtracted from the highest value w*h-1 in the array.
中间的菱形有两种情况.如果矩形的宽度大于(或等于)高度，则矩形的左下方字段是菱形中值最低的字段，并且可以计算出h-1之前的总和.从那里开始，您可以想象菱形是一个矩形，与原始矩形相比，x值为x+y，y值为y.因此，可以轻松计算该新矩形中的剩余值.
在另一种情况下，当高度大于宽度时，可以使用该算术和求出x=w-1和y=0处的字段，菱形可以想象为x值x和y-的矩形.值y-(w-x-1).
There are two cases for the rhomboid in the middle. If the width of rectangle is greater than (or equal to) the height, then the bottom left field of the rectangle is the field with the lowest value in the rhomboid and can be calculated that sum from before for h-1. From there on you can imagine that the rhomboid is a rectangle with a x-value of x+y and a y-value of y from the original rectangle. So calculations of the remaining values in that new rectangle are easy.
In the other case when the height is greater than the width, then the field at x=w-1 and y=0 can be calculated using that arithmetic sum and the rhomboid can be imagined as a rectangle with x-value x and y-value y-(w-x-1).
例如，可以通过预先计算值来优化代码.我认为对于所有这些情况也有一个公式.也许我以后再考虑.
The code can be optimised by precalculating values for example. I think there also is one formula for all that cases. Maybe i think about it later.
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);
}
}
当然，如果没有这样的限制，类似的东西应该会更快:
Of course if there is not such a limitation, something like that should be way faster:
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--;
}
}
这篇关于如何基于坐标对角填充2D数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
