2D Date in a 1D Array
Representing two dimensional data in a one dimensional array is a very common concepts in graphics as well as general programming, as multi-dimensional arrays have issues of not being very cache friendly and causing issues of uninitialized rows or jagged arrays.
Data in a 2D grid layout
This is a representation of data in a 2D grid with zero-based index pairs (x, y). The first digit represents the row the second represents the column.
Matching of 2D data to a 1D index
Putting all the rows behind each other we can transform the 2D grid layout into a 1D line. Now the remaining challenge is to find a mapping between the 2D index and the 1D when you try to access data in a spacial manner. All it takes is some simple math:
Some examples to confirm the validity of the formula:
- (0, 0) → 0
- \(i = 0 + (0 \cdot 3) = 0\)
- (2, 1) → 5
- \(i = 2 + (1 \cdot 3) = 5\)
And finally the reverse process for getting the (x, y) value pair from a one dimensional array. Again this requires some math, but it's important to note here that we’re using integer division:
Using some values from the graphics above gives us the follow examples:
- 7 → (1, 2)
- \(x = 7 - (\frac{7}{3} \cdot 3) = 7 - (2 \cdot 3) = 1\)
- \(y = \frac{7}{3} = 2\)
- 3 → (0, 1)
- \(x = 3 - (\frac{3}{3} \cdot 3) = 3 - 3 = 0\)
- \(y = \frac{3}{3} = 1\)
Code Example
Enough text, images and math, here's some example code:
#include <vector>
#include <iostream>
template<typename T>
struct Vector
{
Vector(T x, T y): X{x}, Y{y} {}
T X;
T Y;
};
template<typename T>
constexpr T GetIndex(Vector<T> position, Vector<T> size)
{
auto width = size.X;
return position.X + (width * position.Y);
}
template<typename T>
constexpr Vector<T> GetPosition(T index, Vector<T> size)
{
auto width = size.X;
auto height = size.Y;
auto x = index - ((index / width) * height);
auto y = index / width;
return { x, y };
}
int main()
{
const auto size = Vector<unsigned int>{ 4, 4 };
auto data = std::vector<int>{ 25, 34, 42, 27,
40, 44, 50, 47,
45, 13, 36, 44,
18, 34, 36, 41 };
for (auto y = 0u; y < size.Y; ++y)
{
for (auto x = 0u; x < size.X; ++x)
{
std::cout << data[GetIndex({ x, y }, size)] << "\t";
}
std::cout << "\n";
}
std::cout << "\n";
for (auto i = 0u; i < data.size(); ++i)
{
std::cout << i << "\t";
}
std::cout << "\n";
for (auto& value : data)
{
std::cout << value << "\t";
}
std::cout << "\n\n";
std::cout << "Index of (2, 1) is " << GetIndex({ 2u, 1u }, size) << "\n";
std::cout << "Value: " << data[GetIndex({2u, 1u}, size)] << "\n\n";
auto position = GetPosition(7u, size);
std::cout << "Index of 7 is at position (" << position.X << ", " << position.Y << ")\n";
std::cout << "Value: " << data[7] << "\n\n";
}