Points équidistants à travers un cube

Question

J'ai besoin d'initialiser quelques points en trois dimensions, et je veux qu'ils soient équidistants dans un cube. Existe-t-il des moyens créatifs de le faire? J'utilise un algorithme de maximisation de l'attente itératif et je veux que mes vecteurs initiaux "étendent" l'espace uniformément. Par exemple, supposons que j'ai huit points que je veux espacer également dans un cube de taille 1x1x1. Je voudrais que les points aux coins d'un cube avec une longueur de côté de 0,333, centré dans le plus grand cube.

Un exemple 2D est ci-dessous. Notez que les points rouges sont équidistants les uns des autres et les bords. Je veux la même chose pour la 3D.

Dans les cas où le nombre de points ne dispose pas d'une racine cubique entier, je suis très bien avec laissant des « lacunes » dans l'arrangement.

Actuellement, je prends la racine cubique du nombre de points et de l'utiliser pour calculer le nombre de points et la distance désirée entre eux. Ensuite, je parcourt les points et incrémente les coordonnées X, Y et Z (décalées de sorte que Y ne s'incrémente pas jusqu'à ce que X reboucle à 0, même chose pour Z à l'égard de Y).

S'il y a un moyen facile de le faire dans MATLAB, je serais ravi de l'utiliser.

Answer 1

Vous devez définir le problème plus en détail dans les cas où le nombre de points n'est pas un cube parfait. Mais selon moi, pour les cas où le nombre de points est un cube, vous pouvez utiliser:

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

Ensuite, pour chaque position dans les matrices, les coordonnées de ce point sont données par les éléments correspondants de X, Y, et Z. Si vous voulez que les points énumérés dans une seule matrice, de telle sorte que chaque ligne représente un point, avec les trois colonnes pour x, y, et les coordonnées z, alors vous pouvez dire:

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

vous avez maintenant un liste de n^3 points sur une grille dans le cube unité, à l'exclusion des limites. Comme d'autres l'ont suggéré, vous pouvez probablement supprimer certains points au hasard si vous voulez moins de points.Ce serait facile à faire, en utilisant randi([0 n^3], a, 1) pour générer a indices de points à supprimer. (N'oubliez pas de vérifier les doublons dans la matrice renvoyée par randi(), sinon vous risquez de ne pas supprimer suffisamment de points.)

Answer 2

un bon générateur aléatoire pourrait être une première approximation utilisable. peut-être avec un filtre ultérieur pour repositionner (de nouveau au hasard) les pires contrevenants.

Answer 3

Cela ressemble à sphere packing.

Answer 4

La stratégie d'échantillonnage que vous proposez est connue sous le nom de grille de Sukharev, qui est la stratégie optimale d'échantillonnage à faible dispersion, http://planning.cs.uiuc.edu/node204.html. Dans les cas où le nombre d'échantillons n'est pas n^3, la sélection des points à omettre de la grille est sans importance du point de vue de l'échantillonnage.

En pratique, il est possible d'utiliser des techniques d'échantillonnage à faible discordance (quasi-aléatoire) pour obtenir de très bons résultats en trois dimensions, http://planning.cs.uiuc.edu/node210.html. Vous pourriez vouloir regarder en utilisant des séquences de Halton et Hammersley.

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

Answer 5

Choisissez les points de façon aléatoire dans le cube, puis calculez les vecteurs au voisin ou au mur le plus proche. Ensuite, étendre les extrémités du vecteur le plus petit par décroissance exponentielle de la taille du pas. Si vous le faites de manière itérative, les points devraient converger vers la solution optimale. Cela fonctionne même si le nombre de points n'est pas cubique.