Discussion :

[damilari]

Bonjour à tous,

Je souhaite générer aléatoirement un nombre N de points de coordonnées x,y,z dans un certain volume V. Ces points, pris 2 à 2, doivent toujours être distant d'au moins r.

Je procède en générant une matrice Nx3. A chaque point généré, l'algorithme teste si ce point est bien distant d'au moins r des points générés précédemment. Tant que le point est trop proche, il est recalculé.

Je joins l'algorithme que j'ai écrit (je ne montre pas par contre la partie au début qui teste si le nombre de points demandé n'est pas trop important).

Les points ne respectent pas la contrainte de distance. Je ne vois pas ce qui cloche pourtant. Grand merci pour votre aide.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
clear all;
N = 20;%nombre de points à générer
r = 0.16;%distance minimale souhaitée entre les points 
A(1,:) = [(0.5 + 0.5*rand(1)) (0.5 + 0.5*rand(1)) (0.5 + 0.5*rand(1))]; %premier point généré dans un volume de dimensions 0.5, 0.5, 0.5
    for i = 2:N
        A(i,:) = [((0.5 + 0.5*rand(1)) (0.5 + 0.5*rand(1)) (0.5 + 0.5*rand(1))];  
        y = pdist(A);%fonction qui calcule les distances entre les points pris 2 à 2. C'est un vecteur de longueur N*(N-1)/2
            for j = 1:length(y)
                if y(j) < r
                    A(i,:) = [(0.5 + 0.5*rand(1)) (0.5 + 0.5*rand(1)) (0.5 + 0.5*rand(1))];%le point est recalculé
                    y = pdist(A);%les distances euclidiennes sont recalculées
                    while y(j) < r
                      A(i,:) = [(0.5 + 0.5*rand(1)) (0.5 + 0.5*rand(1)) (0.5 + 0.5*rand(1))];
                      y = pdist(A);
                    end
              end
     break%pour sortir de la boucle 'for' et passer au point suivant sachant que les précédents sont bons
     end
end
A;
pdist(A);
plot3(A(:,1),A(:,2),A(:,3),'.','MarkerSize',15)

[Jerome Briot]

Pourquoi ne pas simplement générer une grille régulière de points équidistants (d'au moins r) avec NDGRID et n'en conserver qu'un certain nombre en les désignant de façon aléatoire avec RANDPERM ?

[paradize3]

La solution de Dut ne fournira que des points alignes sur la grille, je suppose que l'OP a plutot besoin de points avec coordinees aleatoires non entieres?

[Jerome Briot]

Un simple décalage donné en multipliant chaque point par un triplet de valeur aléatoire en utilisant RAND et en veillant à rester dans la limite r fixée devrait faire l'affaire...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[x,y,z] = ndgrid(...);
 
idx = randperm(numel(x));
 
N = 30;
idx = idx(1:30);
 
x = x(idx);
y = y(idx);
z = z(idx);
 
x = x.*rand(30,1);
y = y.*rand(30,1);
z = z.*rand(30,1);

Tout en veillant à respecter la condition sur r

[paradize3]

Dut, je suppose que tu additionnes un nombre aleatoire plutot que multiplier... et comment tu maintiens la condition distance minimum (ce qui est le probleme de depart)?

[Jerome Briot]

Tu as raison, j'ai formulé ma solution trop vite (ou peut être trop tôt )

Prenons le cas en 1D :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
% Distance a respecter
r = .9;
 
% Distance de variation possible 
f = .1;
 
% Nombre de points
N = 10;
 
% Points equidistant de r+f
x1 = 1:r+f:N*(r+2*f)
 
% Distance entre les points equidistants
d = sqrt((x1(2:end)-x1(1:end-1)).^2)
% Vérification de distance inférieure à r
any(d<=r)
 
% On déplace chaque point aléatoirement de +/- la valeur f/2
x2 = x1 + f*(rand(1,numel(x1))-.5)
 
% Distance entre les points modifiés
d = sqrt((x2(2:end)-x2(1:end-1)).^2)
% Vérification de distance inférieure à r
any(d<=r)
 
% Affichage
figure
p = plot(x1,zeros(1,numel(x1)),'rs',x2,zeros(1,numel(x2)),'g*');
set(gca,'ylim',[-1 1])
legend(p,{'Points initiaux' 'Points déplacés'})

Ceci est facilement transposable dans le dimensions supérieures :

• en 2D en prenant f comme le rayon d'un cercle autour de chaque points
• en 3D en prenant f comme le rayon d'une sphère autour de chaque points