IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

ordonner un ensemble de points de façon circulaire


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Futur Membre du Club
    Inscrit en
    Décembre 2008
    Messages
    4
    Détails du profil
    Informations forums :
    Inscription : Décembre 2008
    Messages : 4
    Par défaut ordonner un ensemble de points de façon circulaire
    Bonjour à tous,

    Voici mon problème. J'ai une matrice A (n lignes, 3 colonnes) contenant les 3 coordonnées d'un ensemble de n points. L'ensemble de ces points décrit un contour dans l'espace.

    Pour l'instant, la matrice A n'est pas ordonnée (ce qui signifie que le point n°1 (ligne 1) n'est pas nécessairement le voisin du point 2 (ligne 2)).

    Je souhaiterais ordonner cette matrice, ç-à-d permuter les lignes, de manière à parcourir le contour de façon "cirulaire".

    Dans un premier temps, ma stratégie était la suivante:

    - calculer un centre (moyenne arithmétique des cordonnées de l'ensemble des n points),
    - calculer les vecteurs reliant le centre à chacun des points du contour,
    - calculer (cart2pol) les coordonnées polaires de chaque point par rapport au centre -> theta (n lignes, 1 colonnes),
    - ordonner ce vecteur theta (avec la fonction sort) en stockant les permutations effectuées,
    - re-ordonner la matrice A de départ avec les permutations obtenues au point précédent.

    Malheureusement, si pour un contour convexe, cette méthode convient parfaitement, elle n'est pas toujours valable dans le cas d'un contour concave...

    Je suis donc à la recherche d'un algorithme (ou d'une bonne idée) permettant de faire cela pour des formes convexes et concaves.

    Merci d’avance pour votre aide.

  2. #2
    Membre expérimenté
    Inscrit en
    Novembre 2006
    Messages
    236
    Détails du profil
    Informations forums :
    Inscription : Novembre 2006
    Messages : 236
    Par défaut
    Je suis donc à la recherche d'un algorithme
    Tu devrais donc plutôt poser ta question dans la partie Algorithmes du forum

  3. #3
    Futur Membre du Club
    Inscrit en
    Décembre 2008
    Messages
    4
    Détails du profil
    Informations forums :
    Inscription : Décembre 2008
    Messages : 4
    Par défaut
    Bien reçu, je vais poster ma demande dans la rubrique "Algorithme" également.

    En fait, j'espère pouvoir utiliser certaines commandes Matlab pour me faciliter la tâche (convhull p.ex). D'où mon post dans cette section.

  4. #4
    Expert confirmé
    Avatar de Caro-Line
    Profil pro
    Inscrit en
    Mars 2007
    Messages
    9 458
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2007
    Messages : 9 458
    Par défaut
    Citation Envoyé par Valais04 Voir le message
    Bien reçu, je vais poster ma demande dans la rubrique "Algorithme" également.
    Plus la peine, c'est déplacé

    [EDIT] Et n'hésites pas à revenir au Forum MATLAB lorsque tu auras des questions de programmation.

  5. #5
    Futur Membre du Club
    Inscrit en
    Décembre 2008
    Messages
    4
    Détails du profil
    Informations forums :
    Inscription : Décembre 2008
    Messages : 4
    Par défaut
    Merci!

  6. #6
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 77
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Par défaut
    J'ai regardé ton algo qui a l'air sympa et qui va marcher quand la forme est à peu près circulaire, mais essaie de voir ce qui va se passer si la forme est un croissant fort accentué avec un isobarycentre extérieur à l'enveloppe convexe.
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  7. #7
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    N'aurait-on pas déjà eu une (plusieurs ?) discussion sur les enveloppes non-convexes ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  8. #8
    Futur Membre du Club
    Inscrit en
    Décembre 2008
    Messages
    4
    Détails du profil
    Informations forums :
    Inscription : Décembre 2008
    Messages : 4
    Par défaut
    Ok mais comment puis-je retrouver ces discussions?

  9. #9
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par Valais04 Voir le message
    Ok mais comment puis-je retrouver ces discussions?
    Grace à la fonction "Recherche" de la barre d'outils du site.

    http://www.developpez.net/forums/d47...rnes-polygone/
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  10. #10
    sdx
    sdx est déconnecté
    Membre confirmé Avatar de sdx
    Profil pro
    Inscrit en
    Janvier 2004
    Messages
    106
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2004
    Messages : 106
    Par défaut
    ça me rappelle ce problème :

    http://myismail.chez.com/mp/cf/ensimp01info.pdf

    Dans la partie "Algorithmique et programmation" (caml ou pascal), tu dois pouvoir réutiliser les notions traitées en 1.4, 1.5, et 2, et les adapter aux enveloppes non convexes. (cf "2. relation d'ordre polaire")


    [edit: lien corrigé]

Discussions similaires

  1. Intersection d'ensembles de points en 3D
    Par dodup64 dans le forum Calcul scientifique
    Réponses: 4
    Dernier message: 04/03/2008, 23h35
  2. Réponses: 5
    Dernier message: 16/02/2007, 15h53
  3. boule minimale contenant un ensemble de points
    Par tlemcenvisit dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 28/02/2006, 10h36
  4. Récupérer l'ensemble des points d'une droite
    Par Psycho_Kwak dans le forum AWT/Swing
    Réponses: 4
    Dernier message: 18/01/2006, 11h42
  5. Réponses: 3
    Dernier message: 12/06/2002, 19h03

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo