I need to (roughly) evenly distribute points in space, but the dimensionality isn't fixed.
I've seen the Fibonacci Sphere algorithm, but as it uses sin cos for x,z it seems it's only suited for 3D space. I've also seen the sunflower spiral algorithm, but it similarly is limited to 2D.
Is there a general algorithm that takes
- a number of points
- a number of dimensions
and spreads points throughout?
CodePudding user response：
We can fill your space with k^n n-dimensional hypercubes by dividing each dimension into k equally-sized regions.
Given r points and n dimensions, we want r = k^n, so k = r^(1/n).
E.g., for 1000 points and 2 dimensions we'd want k = 1000^(1/2) = 31.6 regions per dimension, but for 3 dimensions we'd want k = 1000^(1/3) = 10 regions per dimension.
For non-integer values, I'd recommend rounding up (so 31.6 becomes 32). This will give you a few more cells than points. You can either select which cells don't get points at random, or distribute them towards the edges or however you like.
Once you have the cells that should have points, assign 1 point randomly to a location within each cell, choosing a float between 0-1 per each dimension as the points location along that dimension's axis segment within the cell.
Since the cells are perfectly distributed (except possibly a few extra empty cells) and there is one point per cell, the points are reasonably distributed in space while still being random.