Discussion :

[moooona]

Bonjour,
J'ai un ensemble des points en 3D. je suis en train de chercher les deux points les plus éloignés.
J'ai pas trouvé un algorithme qui permet de trouver les deux points les plus éloignés

[TNT89]

Salut,

On peut penser à une double boucle For qui balaie l'ensemble des couples de points et qui ne retient les indices des points que du couple celui qui présente la plus grande distance (version bourrine, en N²).

On peut aussi penser à essayer de faire un peu plus fin : chercher l' isobarycentre, puis chercher le point le plus éloigné de ce dernier et enfin chercher le point le plus éloigné du précédant (en N, je ne garantie pas que ça fonctionne, mais je n'arrive pas à trouver de contre-exemple).

Cdt,

[Kalith]

Ta seconde méthode doit bien fonctionner si la répartition des points est relativement uniforme.

Ca ne fonctionnera pas dans ce genre de situations :


L'ensemble de point initial est représenté en noir, avec les trois points particuliers A, B et C.
Le centre de gravité est noté G (en rouge).

Les lignes noires transparentes sont juste là pour la construction (il faut que C soit le point le plus éloigné de G).

Les lignes bleues sont le résultat de ton algo, et la ligne verte, le vrai résultat.

... si je ne me trompe pas

[TNT89]

Bien vu Kalith!



Donc 'exit' cette solution... reste le N²...

[Kalith]

Beh ca dépend de la distribution de points. Si tu sais qu'elle est bien uniforme, tu peux utiliser ta solution sans problème je pense. A vérifier

[moooona]

Bonjour,
J'ai un ensemble de points très grands donc je peux pas utiliser la distance car elle va consommer beaucoup de temps.
Est ce qu'il y une autre méthode avec laquelle je peu déterminer les deux points les plus éloignés dans un énorme nuage des points

[Kalith]

Puisque tu utilises des comparaisons de distances, tu peux te passer de calculer la racine carrée, et juste sommer le carré des coordonnées. C'est pas si lourd que ça à calculer

[moooona]

J'ai 1 000 000 points et même parfois plus. J'ai trouvé une méthode qui consiste à calculer le convex Hull mais comme meme elle est un peu lourd.
Je veux une méthode plus rapide que ça.
Est ce que vous pouvez me donner un autre piste où je peux chercher.
Merci d'avance

[Invité]

Je dirais que ça dépend de la distribution de tes points, si ils ont tendance à faire des amas ou pas.

Si la distrib est plus ou moins uniforme :
- mets tes points dans un grille 3D avec une taille de cellule a ajuster
- tout en maintenant la distance max courante, tu prend les cellules non-vides deux par deux et tu compares leurs points un par uns
- tu peux discarder un couple de cellule sans regarder ses points si la distance max possible est < la distance max courante


C'est toujours du O(n²) mais probablement avec une meilleure constante.


Si tous les points se retrouvent dans les mêmes case de la grille alors remplace la structure grille par un octree (et bonne chance).

[moooona]

Bonjour,
la distribution des points n'est pas uniforme. Ils sont dispersés aléatoirement dans l'espace.
Merci

[plegat]

la distribution des points n'est pas uniforme. Ils sont dispersés aléatoirement dans l'espace.

J'ai un peu de mal à me représenter une dispersion aléatoire qui ne soit pas plus ou moins uniforme... Si la distribution n'est pas uniforme, on peut définir des zones privilégiées (et donc on n'est plus en aléatoire...).

Sinon +1 avec ponce et sa grille... on accélère les calculs en déterminant les cases non-vides les plus éloignées, et on fignole sur les éléments de ces cellules (ou on peut pousser encore plus loin en redéfinissant des grilles internes et en rajoutant une boucle de calcul). Attention à bien définir les critères de distance sur ces cases par contre...

[Mikmacer]

Gérer un nuage de points sans structure de données? J'opterais pour la grille aussi. Il y aurait peut-être la solution simple: À chaque ajout d'un point dans le nuage, on le test avec tout les points ajoutés afin de déterminer la plus grand distance possible(La distance^2), si aucune meilleur distance existe ou que la distance est plus grande que celle existante, on la garde comme meilleur distance.

Autre idée, disont qu'a chaque X ajouts de points, un convex hull est construit pour ce nombre X de points. Ensuite, seul les points qui résides dans ces sous-convexhull seront des points potentiels pour êtes les plus distant. En suite, à chaque Y ajouts de convex hull, les convex hull sont combinés pour en former un plus grand, et ainsi de suite. On éllimine progressivement les points comme ça. L'algorithme du convex hull pourrait être quickhull.

Avec le convexhull final on calcul la matrice de covariance, on en retire les 3 eigenvectors et l'un d'eu contient l'axe sur lequel les points les plus distants seront situés(On doit projeter les points sur chacun des axes pour déterminer). Si les points sont déjà tous ajoutés le calcul du convex hull pourrait probablement être accéléré avec une structure de données comme une grille(Octree). Au lieu de projeter tout les points sur un axe, on peut projeter les 4 coins de chacune des cellules, et tester seulement les points qui résides dans les 2 grilles des extrémités de la projection. (Quand je parle de projection, c'est le produit scalaire(dot product) d'un point sur un vecteur qui représente un axe et/ou direction qui est utilisé dans les algorithmes comme le quickhull)

Pour la matrice de covariance, on peut chercher "covariance" dans le paper de Gottschalk situé ici.

Sinon, sans utiliser la matrice de convariance, on peut faire un test On^2 sur les points qui réside sur le convexhull final(moins optimisé).

Ça risque de ne pas être simple à implémenter.

[victor_gasgas]

Je reviens sur l'algo pour trouver les deux points les plus éloignés : la double for en bien en O(N²), mais il y à un moyen de réduire le nombre de calcul (mais on garde la complexité, voir post en dessous), qui vient de mon prof d'algo :

En effet, pour deux points A et B, on sait que la distance AB est égale à BA, donc pas besoin de re-tester. De plus, pas besoin de tester avec soit même, car la distance serait nulle.
Ce qui nous donne en C++ (le type vec3 est un vecteur de R³ qui viens du GLSL, cf glm) :

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
float distanceMax(const std::vector< vec3 > &tab)
{
    if( tab.size() < 1)
        std::throw runtime_error("Pas assez de point dans le tableau!");
 
    // Valeur la plus petite retournée si on à qu'un point par exemple
    float distMax = 0.0f;
 
 
    // Pour réduire la complexité c'est les bornes qu'il faut regarder
    for(unsigned int i(0); i<(tab.size() - 1); ++i)
    {
        for(unsigned int j(i+1); j<tab.size(); ++j)
        {
            float d = distanceAuCarre( tab[i], tab[j] );
 
            if( d > distMax )
                distMax = d;
        }
    }
 
 
    return sqrt(distMax);
}

Si le raisonement est faux ou que je suis à coté de la faite moi savoir, car je suis bien loin des matrices de covariance et convex hull juste avant

Le code peut contenir des erreurs, j'ai pas testé (dimanche matin...). Il permet d'obtenir la distance max. Si tu veux récupérer les index des 2 vecteurs les plus éloigné t'as pas grand chose à changer.

P.S Quand je compare les distances je calcule la distance au carré, ce qui permet de s'éviter une racine carré à chaque tour (en effet si je me souviens bien des cours de maths, pour tout x,y de R+ | x<y, alors x²<y² car la fonction f(x) = x² est croissante sur R+, ici domaine de définition des distances).

Elle est néanmoins présente à la fin pour obtenir la bonne distance.


Par contre ici la nouvelle complexité n'est pas O(N), mais en O(N log(N)) mais je ne suis pas sur, donc si quelqu'un peut confirmer


EDIT : Correction en fait la complexité reste O(N²) d'après la démonstration ci-dessous. L'algo permet seulement de réduire le nombre de calcul.

[TNT89]

Perso, je trouve toujours ue complexité en O(N²) selon le raisonnement suivant :

Soit un ensemble de N points, l'algorithme ci-énoncé va testé un nombre de cas donné par:

N + N-1 + N-2 + ... + 1
= Sum(i, 1, N)
= (N+1)/2 * N
= O(N²)

[victor_gasgas]

C'est vrai qu'avec ce raisonnement ca fait de suite plus grand, donc au tant pour moi sa reste du O(N²).

Peut-on par contre dire que sa reste une optimisation du fait qu'on réduit le nombre de calcul?

J'édite néanmoins tout de suite le post de au dessus

[Kalith]

Ca reste du O(N²) mais tu divises quand même par deux le nombre d'itérations, ce qui n'est pas rien.
La complexité c'est beau, mais ça ne dit pas tout...

[TNT89]

La complexité te dit tout au niveau de l'algorithme mais pas au niveau de l'architecture sur le quel il va tourner...

Donc, sur une même machine, le second tournera plus vite, c'est tout ce que l'on peut dire...

Et puis, ce n'est pas non plus une division du nombre d'opération par 2 exactement, si tu utilises ce raisonnement...

[Kalith]

Donc, sur une même machine, le second tournera plus vite, c'est tout ce que l'on peut dire...

... et c'est ce qui nous intéresse, non ?

Et puis, ce n'est pas non plus une division du nombre d'opération par 2 exactement, si tu utilises ce raisonnement...

Pas exactement non, mais à peu de chose près oui.
Ca reste un gain de temps, et donc une optimisation (pour en revenir à la question de victor).

[moooona]

Bonjour,
J'ai pas vu l'optimisation de cet algorithme.
On a toujours une complexité O(N²) .
En utilisant cet algorithme ça va consommer beaucoup de temps. Le plus important pour moi est comment je peux avoir le résultat dans le plus courte durée

[Invité]

cf. mon post plus haut.