trouver les deux points les plus éloignés

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: ghghgh

... dans une nuée de points.

Bonjour le monde,

S'il vous plaît, je cherche le moyen de trouver le plus rapidement possible les deux points les plus éloignés dans une nuée de points comme le précise le titre de ce post...

Au début donc, je construis l'enveloppe convexe avec un balayage de graham
car les deux points se situent forcément sur cette enveloppe, ensuite, pour l'instant je compare tout les points (en O(n^2) donc) pour trouver les plus distants... j'aimerais trouver un moyen de le faire plus rapidement en O(n log n) si possible =)

voilà, merci d'avance, à ceux qui liront et répondront

Bonne soirée


Posted by: olivthill

Une nuée de points
Dans un espace à deux dimensions ? trois dimensions ? autre ?
Dans un espace infini ou borné ?

S'il s'agissait d'un espace à une dimension, il suffirait de rechercher le plus petit et le plus grand. Dans un espace à deux dimensions, on pourrait faire la recherche en ordonnant d'abord les points selon le produit de leur coordonnées xy, puis en considérant en premier lieu les distances entre les plus petits et plus grands xy.

Si c'est un espace borné, on pourrait commencer par rechercher les points qui se trouvent sur la périphérie, en faisant une recherche par cercles concentriques décroissants.

Pour accélerer la comparaison des distances, je crois qu'il n'est pas nécessaire de calculer la racine carré. Mais je ne sais pas si cette optimisation utile en pratique est comptabilisée dans le décompte théorique avec les O().


Posted by: ghghgh

merci, merci, non la faible optimisation sur les racines ne changent en rien la complexité de l'algo, par contre, le coup du produit des coordonnées permet d'arranger un peu les choses... mais les points aux extrémités une fois triés, ne sont pas forcément les plus éloignés, donc, il faut quand même si ce n'est tout, mais presque tout comparer, je pense...
donc, globalement j'ai tout de même du n^2...
je pense il doit y a voir une approche "diviser pour régner" pour résoudre de problème de deux points les plus éloignés dans un polygône convexe...

(c'est une nuée 2d effectivement)


Posted by: ghghgh

re Bonsoir, le monde...
il signale qu'il existe une méthode pour trouver ses deux points dans un polygône convexe en {O}(n \log n) dans le Cormen... par contre j'ai beau cherché, je ne trouve pas la méthode... j'ai notamment trouver un tp de l'X qui cherche à présenter toutes sortes de moyens de faire des enveloppes convexes & cie... puis il touche un mot de la méthode... mais ne la décrive pas... et s'arrête là :x
y a t-il quelqu'un qui a un bon niveau d'algo, ou qui fait des études d'algo géométriques ? :) je lui en serai très reconnaissant... et aussi à tous ceux qui me proposeront quelques idées ^^également

vlà, merci, bonne continuation à tous
à bientôt


Posted by: anima

Citation:
Posté par ghghgh
re Bonsoir, le monde...
il signale qu'il existe une méthode pour trouver ses deux points dans un polygône convexe en {O}(n \log n) dans le Cormen... par contre j'ai beau cherché, je ne trouve pas la méthode... j'ai notamment trouver un tp de l'X qui cherche à présenter toutes sortes de moyens de faire des enveloppes convexes & cie... puis il touche un mot de la méthode... mais ne la décrive pas... et s'arrête là :x
y a t-il quelqu'un qui a un bon niveau d'algo, ou qui fait des études d'algo géométriques ? :) je lui en serai très reconnaissant... et aussi à tous ceux qui me proposeront quelques idées ^^également

vlà, merci, bonne continuation à tous
à bientôt

Tu as l'enveloppe? Si oui, il te suffit de prendre tous les points sur cette enveloppe et de regarder les distances entre tous ces points "limites"; je te garantis que si c'est en 2 dimensions, un couple extérieur (PointA,PointB) sera ce que tu cherches.

Somme toute, si ton enveloppe est formée de n points, alors... il te faudra n(n-1) opérations


Posted by: ghghgh

Salut Anima,
Yep, j'sais, c'est déjà ce que j'ai fait... la construction de l'enveloppe est rapide... et les deux points sont forcéments sur cette enveloppe...
par contre, après comme tu l'as dit je dois vérifier toutes les distances des n points de l'enveloppe en n(n-1) donc en {O}(n^2)
et ça c'est pas top, surtout, si tu as une très grosse enveloppe...
d'où mon problème...
mais dans certains bouquins d'algos, ils affirment que c'est possibles de trouver ces deux points sur l'enveloppe en points d'opérations que n(n-1), mais ils ne disent pas comment ^^'.

Voilà, merci qund même !


Posted by: anima

Citation:
Posté par ghghgh
Salut Anima,
Yep, j'sais, c'est déjà ce que j'ai fait... la construction de l'enveloppe est rapide... et les deux points sont forcéments sur cette enveloppe...
par contre, après comme tu l'as dit je dois vérifier toutes les distances des n points de l'enveloppe en n(n-1) donc en {O}(n^2)
et ça c'est pas top, surtout, si tu as une très grosse enveloppe...
d'où mon problème...
mais dans certains bouquins d'algos, ils affirment que c'est possibles de trouver ces deux points sur l'enveloppe en points d'opérations que n(n-1), mais ils ne disent pas comment ^^'.

Voilà, merci qund même !

J'ai bien une idée. Tu peux trouver le centre de ton enveloppe, et ensuite couper cette "zone" délimitée par l'enveloppe en quatre cadrans. Ensuite, tu peux peut-etre dire que la plus grande distance entre 2 points de l'enveloppe se fera sur des quadrants opposés. Exemple:


Cadrans:
1 2
X
3 4
Dans ce cas précis, une distance de 1 a 4 sera bien plus longue que 2 a 4, 3 a 4 etc... C'est peut-etre une piste a suivre.


Posted by: ghghgh

juste pour ceux qui rencontreraient le même problème, ou qui souhaiteraient connaître la solution :

http://w3.jouy.inra.fr/unites/miaj/...s/avigneron.pdf

:D


Posted by: Flodelarab

Citation:
Posté par ghghgh
juste pour ceux qui rencontreraient le même problème, ou qui souhaiteraient connaître la solution :

http://w3.jouy.inra.fr/unites/miaj/...s/avigneron.pdf

:D
Super ton pdf.


Ce que je retiens pour trouver les 2 points les plus éloignés dans un nuage de points dont nous n'avons que les coordonnées:
c'est bon ?










-