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 :

Polygone au volume minimum


Sujet :

Algorithmes et structures de données

  1. #1
    Membre régulier
    Inscrit en
    Décembre 2009
    Messages
    95
    Détails du profil
    Informations forums :
    Inscription : Décembre 2009
    Messages : 95
    Points : 77
    Points
    77
    Par défaut Polygone au volume minimum
    Bonjour,

    Voici mon problème :

    J'ai un ensemble de 256 points dans un espace 3D, chaque point est donc représenté par 3 valeurs (x, y, z) tel que 0 <= x, y, z <= 511.

    J'aimerais savoir s'il existe un algorithme permettant, pour un nombre T de points, de sélectionner parmi mes 256 points T points de façon a respecter les deux conditions suivantes :
    - le polygone créé à partir des T points contient tous les autres 256-T points
    - le polygone créé à partir des T points possède le volume minimum parmi les autres polygones possibles respectant la première condition

    Je vous remercie d'avance de votre aide, ne serait-ce que si vous avez une piste

    Bonne soirée !

  2. #2
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    Tu peux déjà commencer par une enveloppe convexe, ce qui assure la première condition.
    Ensuite, pour la deuxième c'est très délicat de par sa définition. Parce que si l'on pousse à l'extrême, la solution finale est en fait un graphe reliant tous les T-Points.
    Mais à partir de l'enveloppe convexe, tu peux faire une méthode itérative :
    - pour chaque point ne formant pas l'enveloppe
    - trouver les trois points de l'enveloppe les plus proches
    - déformer l'enveloppe en incluant le nouveau point si cela ne fait pas sortir un autre T-Point.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  3. #3
    Rédacteur

    Homme Profil pro
    Comme retraité, des masses
    Inscrit en
    Avril 2007
    Messages
    2 978
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 83
    Localisation : Suisse

    Informations professionnelles :
    Activité : Comme retraité, des masses
    Secteur : Industrie

    Informations forums :
    Inscription : Avril 2007
    Messages : 2 978
    Points : 5 179
    Points
    5 179
    Par défaut
    Salut!
    Juste une petite remarque concernant le vocabulaire: dans un espace 3d, il ne s'agit pas d'un polygone mais d'un polyèdre.
    Jean-Marc Blanc
    Calcul numérique de processus industriels
    Formation, conseil, développement

    Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)

  4. #4
    Membre régulier
    Inscrit en
    Décembre 2009
    Messages
    95
    Détails du profil
    Informations forums :
    Inscription : Décembre 2009
    Messages : 95
    Points : 77
    Points
    77
    Par défaut
    Bonjour,

    Tout d'abord merci à vous deux pour vos réponses, et particulièrement à ToTo13 dont la réponse m'a été très utile. Merci à FR119492 pour cette précision

    Pour apporter un petit complément d'information, voici la page wikipédia relatant les algorithmes pour former l'enveloppe convexe :
    http://en.wikipedia.org/wiki/Convex_hull_algorithms

    Tous ne se généralise pas à des points en 3D. La complexité temporelle de ces algorithmes est au minimum en O(n log n), n étant le nombre de points en entrée. Cependant, certains algorithmes ont une complexité temporelle qui se caractérise en fonction de n et de h, h étant le nombre de points nécessaire pour former l'enveloppe. Ces algorithmes sont appelés output-sensitive algorithms. C'est notamment le cas de l'algorithme de Chan (http://en.wikipedia.org/wiki/Chan%27s_algorithm) dont la complexité est en O(n log h) et qui se généralise à des points en 3D.

    Parfait Merci encore !

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Polygone minimum englobant
    Par Chekov dans le forum Mathématiques
    Réponses: 16
    Dernier message: 06/09/2007, 19h33
  2. Triangulation de Polygones
    Par seb_lisha dans le forum DirectX
    Réponses: 1
    Dernier message: 01/07/2003, 13h40
  3. [Algo] Point à l'intérieur d'un polygone ?
    Par kebby dans le forum C++Builder
    Réponses: 5
    Dernier message: 23/05/2003, 14h22
  4. volume de windows
    Par RCA dans le forum API, COM et SDKs
    Réponses: 4
    Dernier message: 20/03/2003, 18h20
  5. une ligne et un polygone convexe
    Par rekam dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 20/12/2002, 11h39

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