Index Conversion of multidimensional array in C++

Question

I have sample code which converts 3d coordinate to id(index) and reverse. How can i do this for N Dimentional(for example 5d and 6d) array? here is the 3d conversion code :

inline NoximCoord id2Coord(int id) {
  NoximCoord coord;

  coord.z = id / (NoximGlobalParams::mesh_dim_x *
                  NoximGlobalParams::mesh_dim_y);  ////
  coord.y = (id - coord.z * NoximGlobalParams::mesh_dim_x *
                      NoximGlobalParams::mesh_dim_y) /
            NoximGlobalParams::mesh_dim_x;
  coord.x = (id - coord.z * NoximGlobalParams::mesh_dim_x *
                      NoximGlobalParams::mesh_dim_y) %
            NoximGlobalParams::mesh_dim_x;

  assert(coord.x < NoximGlobalParams::mesh_dim_x);
  assert(coord.y < NoximGlobalParams::mesh_dim_y);
  assert(coord.z < NoximGlobalParams::mesh_dim_z);

  return coord;
}

inline int coord2Id(const NoximCoord &coord) {
  int id =
      coord.z * NoximGlobalParams::mesh_dim_x * NoximGlobalParams::mesh_dim_y +
      (coord.y * NoximGlobalParams::mesh_dim_x) + coord.x;
  assert(id < NoximGlobalParams::mesh_dim_x * NoximGlobalParams::mesh_dim_y *
                  NoximGlobalParams::mesh_dim_z);
  return id;
}

I need the conversion in this way (c++ <14)not the ways implemented on other answers.

I would replace x, y and z in coord and mesh_dim with index 0-2 and look for a pattern. You need a loop for all dimensions and a loop in each dimension to calculate the value. — mch
– mch, Commented Dec 16, 2022 at 11:39

Homer512 · Accepted Answer · 2022-12-16 12:57:37Z

Well, this is pretty standard from what I can tell. The coordinate to ID transformation is a simple polynomial evaluation which is best evaluated using Horner's method. The inverse looks more confusing than it needs to be simply because you are inconsistent in using modulo or manually computing it.

Here is a version that uses std::arrays for its dimensions, going from inner most dimension to outermost, so {x, y, z, ...}

#include <array>
#include <functional>
// using std::multiplies
#include <numeric>
// using std::partial_sum


template<std::size_t N>
int coord2Id(const std::array<int, N>& coords,
             const std::array<int, N>& mesh) noexcept
{
    int id = coords.back();
    for(std::size_t i = N - 1; i > 0; --i)
        id = id * mesh[i - 1] + coords[i - 1];
    return id;
}

template<std::size_t N>
std::array<int, N> id2Coord(int id, const std::array<int, N>& mesh) noexcept
{
    std::array<int, N> coord;
    std::array<int, N-1> partials;
    std::partial_sum(mesh.begin(), mesh.end() - 1, partials.begin(),
                     std::multiplies<int>{});
    for(std::size_t i = N - 1; i > 0; --i) {
        coord[i] = id / partials[i - 1];
        id = id % partials[i - 1];
    }
    coord.front() = id;
    return coord;
}

A word of warning: For large dimensions, ID can easily overflow the integer range, for example a {500, 500, 500, 500} mesh would already be too large. I suggest switching to std::ptrdiff_t instead.

Here is a quick conversion from the original pattern:

class NoximCoord
{
public:
    int x, y, z;
};
struct NoximGlobalParams
{
    static int mesh_dim_x, mesh_dim_y, mesh_dim_z;
};
int coord2Id(const NoximCoord& coord) noexcept
{
    return coord2Id(std::array<int, 3>{{coord.x, coord.y, coord.z}},
        std::array<int, 3>{{NoximGlobalParams::mesh_dim_x,
                            NoximGlobalParams::mesh_dim_y,
                            NoximGlobalParams::mesh_dim_z}});
}
NoximCoord id2Coord(int id) noexcept
{
    std::array<int, 3> coords = id2Coord(
        id, std::array<int, 3>{{NoximGlobalParams::mesh_dim_x,
                                NoximGlobalParams::mesh_dim_y,
                                NoximGlobalParams::mesh_dim_z}});
    return NoximCoord{coords[0], coords[1], coords[2]};
}

Thanks for the quick answer, since my NoximCoord is a class like : ``` class NoximCoord { public: int x; // X coordinate int y; // Y coordinate int z; // Z coordinate inline bool operator==(const NoximCoord &coord) const { return (coord.x == x && coord.y == y && coord.z == z); } }; ``` can you give me an example how to use your code?

Collectives™ on Stack Overflow

Index Conversion of multidimensional array in C++

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related