Trouver les deux points les plus éloignés

Discutez d'informatique ici !
ghghgh
Membre Relatif
Messages: 305
Enregistré le: 04 Aoû 2006, 17:20

trouver les deux points les plus éloignés

par ghghgh » 14 Juil 2007, 21:12

... 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



olivthill
Membre Relatif
Messages: 349
Enregistré le: 21 Avr 2006, 19:17

par olivthill » 14 Juil 2007, 23:51

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().

ghghgh
Membre Relatif
Messages: 305
Enregistré le: 04 Aoû 2006, 17:20

par ghghgh » 15 Juil 2007, 00:42

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)

ghghgh
Membre Relatif
Messages: 305
Enregistré le: 04 Aoû 2006, 17:20

par ghghgh » 11 Aoû 2007, 23:45

re Bonsoir, le monde...
il signale qu'il existe une méthode pour trouver ses deux points dans un polygône convexe en 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

anima
Membre Transcendant
Messages: 3762
Enregistré le: 15 Sep 2006, 13:00

par anima » 12 Aoû 2007, 00:03

ghghgh a écrit:re Bonsoir, le monde...
il signale qu'il existe une méthode pour trouver ses deux points dans un polygône convexe en 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 :zen:

ghghgh
Membre Relatif
Messages: 305
Enregistré le: 04 Aoû 2006, 17:20

par ghghgh » 12 Aoû 2007, 14:52

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
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 ! :happy2:

anima
Membre Transcendant
Messages: 3762
Enregistré le: 15 Sep 2006, 13:00

par anima » 12 Aoû 2007, 15:46

ghghgh a écrit: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
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 ! :happy2:

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.

ghghgh
Membre Relatif
Messages: 305
Enregistré le: 04 Aoû 2006, 17:20

par ghghgh » 08 Sep 2007, 14:05

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

http://w3.jouy.inra.fr/unites/miaj/public/seminaire/complements/avigneron.pdf

:D

Flodelarab
Membre Légendaire
Messages: 6574
Enregistré le: 29 Juil 2006, 16:04

par Flodelarab » 08 Sep 2007, 16:15

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

http://w3.jouy.inra.fr/unites/miaj/public/seminaire/complements/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:
  • Enveloppe de graham: O(n.ln(n))
  • Recherche des paires antipodales avec élimination des plus petites: O(n.ln(n))


c'est bon ?

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 10 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite