Equidistant points across a cube

Question

I need to initialize some three dimensional points, and I want them to be equally spaced throughout a cube. Are there any creative ways to do this?

I am using an iterative Expectation Maximization algorithm and I want my initial vectors to "span" the space evenly.

For example, suppose I have eight points that I want to space equally in a cube sized 1x1x1. I would want the points at the corners of a cube with a side length of 0.333, centered within the larger cube.

A 2D example is below. Notice that the red points are equidistant from eachother and the edges. I want the same for 3D.

In cases where the number of points does not have an integer cube root, I am fine with leaving some "gaps" in the arrangement.

Currently I am taking the cube root of the number of points and using that to calculate the number of points and the desired distance between them. Then I iterate through the points and increment the X, Y and Z coordinates (staggered so that Y doesn't increment until X loops back to 0, same for Z with regard for Y).

If there's an easy way to do this in MATLAB, I'd gladly use it.

Rainfall

You didn't define the problem fully, for example there will be many possible layouts of 2 points in a 3D cube. – Dieldrin

3d is often hard to explain in text. Can you give us a sketch? – Profanatory

Why would your 8 pts be in a 1/3 cube? Why not a 1/2 cube or a 9/10ths cube? – Unpopular

I want all the points to be equidistant from eachother and from the sides of the containing cube. – Rainfall

"equidistant from eachother and from the sides of the containing cube"? I am not sure that there necessarily is always a solution that satisfies these conditions. – Unpopular

Just solving once... I have an algorithm that works, but I'm curious if there are better ways. – Rainfall

+1: But its definitely interesting... – Unpopular

The example with 8 points and a 1x1x1 cube is easy to picture. How would say 10 points be distributed? Would that mean you would distribute the first 8 like above and the 2 remaining points randomly? – Profanatory

Answer 1

You'll have to define the problem in more detail for the cases where the number of points isn't a perfect cube. Hovever, for the cases where the number of points is a cube, you can use:

l=linspace(0,1,n+2);
x=l(2:n+1); y=x; z=x;
[X, Y, Z] = meshgrid(x, y, z);

Then for each position in the matrices, the coordinates of that point are given by the corresponding elements of X, Y, and Z. If you want the points listed in a single matrix, such that each row represents a point, with the three columns for x, y, and z coordinates, then you can say:

points(:,1) = reshape(X, [], 1);
points(:,2) = reshape(Y, [], 1);
points(:,3) = reshape(Z, [], 1);

You now have a list of n^3 points on a grid throughout the unit cube, excluding the boundaries. As others have suggested, you can probably randomly remove some of the points if you want fewer points. This would be easy to do, by using randi([0 n^3], a, 1) to generate a indices of points to remove. (Don't forget to check for duplicates in the matrix returned by randi(), otherwise you might not delete enough points.)

Thimble

Answer 2

The sampling strategy you are proposing is known as a Sukharev grid, which is the optimal low dispersion sampling strategy, http://planning.cs.uiuc.edu/node204.html. In cases where the number of samples is not n^3, the selection of which points to omit from the grid is unimportant from a sampling standpoint.

In practice, it's possible to use low discrepancy (quasi-random) sampling techniques to achieve very good results in three dimensions, http://planning.cs.uiuc.edu/node210.html. You might want to look at using Halton and Hammersley sequences.

• http://en.wikipedia.org/wiki/Halton_sequence
• http://en.wikipedia.org/wiki/Constructions_of_low-discrepancy_sequences

Lajuanalake

This answer is interesting and may be what I'm looking for, but it's beyond my understanding at the moment. – Rainfall

Answer 3

This looks related to sphere packing.

Jackofalltrades

Answer 4

Choose the points randomly within the cube, and then compute vectors to the nearest neighbor or wall. Then, extend the endpoints of the smallest vector by exponentially decaying step size. If you do this iteratively, the points should converge to the optimal solution. This even works if the number of points is not cubic.

Achlamydeous

I was doing this previously, but I now need a deterministic solution. – Rainfall

Answer 5

a good random generator could be a first a usable first approximation. maybe with a later filter to reposition (again randomly) the worst offenders.

Pyramidal

How do you define good RNG? After all, if it's random it shouldn't produce approximations for this problem. – Amphiaster

I need a deterministic algorithm. – Rainfall