bonjour à tous,
je developpe un programme et dans celui là je suis amené à extraire les deux points les plus eloigné dans un nuage de point,
ma methode était de comparer les noeuds entre eux (chaque noeuds comparé au n-1 noeuds restant, puis lautre au n-2 restants ....)
or cette methode est lourde en memoire,
je voudrais savoir sil ya autre moyen plus rapide,
merci
Bonjour,
Ce problème est lié au "Convex-Hull", voir : http://en.wikipedia.org/wiki/Convex_hull_algorithms
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
merci,
c'est un peu compliqué quand même
Tu peux en effet commencer par calculer l'enveloppe convexe du nuage, mais je ne pense pas que tu y gagnes en nombre d'opérations.
Les meilleurs algorithmes de calcul de l'enveloppe convexe sont en nln(n), c'est mieux que n².
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
oui en dimension 2 et 3. Mais une fois que tu as calculé l'enveloppe convexe, il te reste à déterminer les deux points les plus éloignés. En dimension 2 l'enveloppe convexe contient généralement une petite proportion des points du nuage, mais au fur et à mesure que la dimension augmente, cette proportion augmente et en grande dimension tous les points sont sur l'enveloppe convexe et on n'a rien gagné.
est ce que je me trmperais beaucoup si j'utise cette norme:
(x²+y²+z²)^.5 avec x= max(nuage.x) - min(nuage.x) ; y= max(nuage.y) - min(nuage.y) z= max(nuage.z) - min(nuage.z)
si oui dans quel genre de configuration de nuage de point où l'erreur vas etres max
je ne comprend pas. Son problème consiste à trouver le max dans n(n-1)/2 combinaisons. Il fait une boucle sur les combinaisons, en mettant à jour le numéro de la combinaison, chaque fois qu'il a un couple de points plus éloignés. ca lui fait un ordre total de n^2.
L'algorithme qu'il décrit n'est pas clair, probablement sur-calcule inutilement. Enfin, je crois.
comme j'avais dit j'au utilisé l'algorithme dont tu parle, mais j'ai a faire à un million de point ça fait .... beaucoup de calcul. je cherche un moyen plus rapide di ça existe, je cherche pas une exactitude absolu,
quant à ce que j'ai proposé dans le dernier message , c'est faire une norme euclidienne sur la plus grand écart des trois composantes, c'est moins lourd en calcul mais pas précis.
merci pour ta participation
Tu es donc en dimension 3.
si ce que tu cherches est une solution approchée le problème est très différent. Il ne suffit pas de raisonner en nombre d'opérations.
Une chose qui peut être faite c'est chercher la première composante principale. Elle correspond à l'axe d'allongement maximal du nuage, donc la distance entre les points projetés les plus extrêmes pourra être une bonne approximation de la distance que tu cherches. Pour calculer la matrice de variance, tu peux sous-échantillonner. Je dirais au pif que 500 points tirés aléatoirement parmi le million de points du nuage sont largement suffisants.
