1

Based on a known {x,y,z,...} coordinate, I'm looking for the index of a location. A 2-dimensional (2d) solution, is provided here. I'm now trying to extend this to two other dimensions: 1d and 3d (and possibly to generalize to higher dimensions).

For 1d, I ended up with the following algorithm (Matlab code), where the walk alternates between the right and left side of the axis:

n = 20; %number of values
X = -n/2:n/2; %X values (1d)

%we want 'p' the index of the location:
for i=1:numel(X)
    if(X(i) > 0)
        p(i) = 2*X(i)-1;
    else
        p(i) = -2*X(i);
    end
end

resulting in the following indexes: enter image description here

However, I have difficulties in vizualizing how the indexation should takes place in 3d (i.e. how the index walks through the nodes in 3d). I'm primarily interested in a C/C++ solution but any other language is fine.

EDIT Reflecting @Spektre comments and suggestions: I aim at finding the indexes of a set of 3d coordinates {x,y,z}. This can be seen as a way to map the 3d coordinates into a set of indexes (1d). The spiral provides a convenient way to perform such a task in 2d, but cannot be extended in 3d.

Grasshoper
  • 457
  • 2
  • 13
  • 1
    well your main problem is that you use term "spiral" which is 2D object/construct... and I do not think it can be expanded into different dimension (and still be called spiral). Even your 1D is questionalble (better call it 1D cut through spiral instead). So to move to 3D or more you would need to first determine what the stuff should do: (cover (hyper)volume with single polyline/curve what shape (curved,rectangular) ? However that would not be spiral more like coil of spirals on hyperspheres/hypercubes with increasing radius/size... – Spektre Oct 23 '20 at 06:47
  • 1
    Also you might want to investigate **space filling curves** like [2D/3D hilbert curve](https://stackoverflow.com/a/50488348/2521214) thre probably is something similar if not the same as you want to achieve... So what pattern/shape in 3D you want can you describe more? – Spektre Oct 24 '20 at 07:28
  • 1
    @Spektre Thank you for the interesting link. Distributing the point evenly on an hypersphere could possibly solve my issue. However, I aim at finding the inverse problem: i.e. finding the index instead of the position {x,y,z,...}), and I need this ot be fast. To be more precise, I would like to map a set of coordinates {x,y,z,...} into 1D and the spiral index provides a convenient (and quite fast) solution in 2D. However, as you stated, this cannot be extended to nD, I will reflect this in the topic. – Grasshoper Oct 26 '20 at 08:47
  • @Spektre Really interesting replies! i will go for cube_map it really sounds to fit my problem! Thank you I will mark your answer when ready. – Grasshoper Oct 26 '20 at 09:06
  • 1
    I moved the comments into answer and add some more stuff ... I also cleared out the comments a bit... Also I think you should google up **butterfly shuffling** and **bit-reversal of index/address** ... I got the feeling they could ease up the conversion into your pattern without any goniometrics (but its just feeling so I might be wrong) – Spektre Oct 26 '20 at 09:45
  • @Spektre Not sure to understand, I want the index from point n-d location, that is indicated in the title (i'm not looking for the location from the index, that is, the reverse of my question). – Grasshoper Oct 26 '20 at 11:55
  • Aaah my bed I misreaded your comment ...`However, I aim at finding the inverse problem: i.e. finding the index instead of the position {x,y,z,...}` was seeing just `finding the index instead of the position {x,y,z,...}` :) – Spektre Oct 26 '20 at 14:22

1 Answers1

1

well as you chose line/square/cube like coil of screws to fill your 1D/2D/3D space like this:

1D/2D/3D preview

I would:

  1. Implement line/square/cube maps

    These will map between 1D index ix and coordinate for known "radius". It will be similar to this:

    See the member functions: ix2dir and dir2ix which maps between index and direction vector. No need to store the surface data you just need these conversion functions. However you need to tweak them so the order of points/indexes represent the pattern you want... in 1D,2D is easy but for 3D I would chose something like surface spiral on cube similar to this:

    Do not forget to handle even and odd screws in 3D differently (mirror) so screws join at correct locations...

    Just to be complete the cube map is like single screw in your 3D system it holds the surface of a cube and can convert between direction vector dir and 1D index ix back and forward. Its used to speed up algorithms in both graphics and geometry ... I think its first use was for Bump Mapping fast vector normalizations. By using cube_map you can do analogy in any dimensionality even 2D,1D easily you just use square_map and Line_map instead without any algo changes. I have tested it on OBB 2D/3D after conversion to cube/square maps the algo stayed the same just the vectors had different number of coordinates (without them the algos where very different).

  2. create/derive equation/LUT that describes how many points which radius covers (inside screws included)

    So function that returns number of points that are in coil of r screws together. It will be a series so the equation should be derivable/inferable easily. Let call this:

    points = volume(r);

  3. now conversion ix -> (x,y,z...)

    first find which radius r your ix is so:

    volume(r) <= ix < volume(r+1)

    simple for loop will do but even better would be binary search of r. Then convert your ix into index iy in line/square/cube map:

    iy = ix-volume(r);

    Now just use the ix2dir(iy) function to obtain your point position...

  4. Reverse conversion (x,y,z...) -> ix

    r = max(|x|,|y|,|z|,...)
iy = dir2ix(x,y,z,...)
ix = volume(r-1) + iy
Spektre
  • 49,595
  • 11
  • 110
  • 380