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 :

Question à propos de Delaunay..


Sujet :

Algorithmes et structures de données

  1. #1
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut Question à propos de Delaunay..
    Bonjour à tous..

    Une petie question...

    Contexte : soit un polygone, et une triangulation de Delaunay de ce polygone..


    Question : peut-on dire que la triangulation Delaunay consiste à trouver les segments les plus proches maximisant les angles relatifs ??


    Je m'explque : Delaunay est censé éviter les triangles aplatis : "Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation......However, the Delaunay triangulation does not necessarily minimize the maximum angle."

    Si donc on fait la triangulation d'un polygone (sans ajouter de points), je me pose la question ci-dessus...


    En d'autres termes, si on cherche le segment le plus proche d'un sommet et maximisant l'angle relatif, peut-on dire que l'on a trouvé le segment le plus proche au sens de Delaunay ??
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  2. #2
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Personne pour me fournir une idée, une piste, ou une réfutation ??

    La question est :

    Si j'ai un polygone, et un point intérieur (par exemple) à ce polygone :

    si , parmi l'ensemble des segments du polygone, je ne cherche pas celui qui est le plus proche, mais celui qui est le plus proche ET pour lequel le rapport distance/angle est maximum, est-ce que cela satisfait au critère de Delaunay ?


    Le segment le plus proche peut donner un triangle extrêmement aplati. Si je prend en compte le rapport distance/angle, lje peux éventuellement trouver un segment un peu plus éloigné en distance, mais dont le rapport distance/angle est plus grand.. Est-ce que ce segment correspondrait alors "au segment le plus proche au sens de Delaunay" ?
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  3. #3
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Je me suis trompé dans l'expression ..

    Ce n'est pas :

    Citation Envoyé par souviron34 Voir le message
    pour lequel le rapport distance/angle est maximum
    mais

    pour lequel le rapport de distance est minimum ET le rapport d'angle est maximum...



    Le segment le plus proche peut donner un triangle extrêmement aplati. Si je prend en compte les rapports de distance et d'angle, je peux éventuellement trouver un segment un peu plus éloigné en distance, mais dont le rapport d'angle est plus grand.. En gros, celui qui minimise le rapport de distance tout en maximisant le rapport d'angle... Est-ce que ce segment correspondrait alors "au segment le plus proche au sens de Delaunay" ?
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  4. #4
    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 : 51
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Je ne pense pas qu'il y ait un critère de décision sur la distance point/segment dans une triangulation de Delaunay contrainte.

    Ca peut bien sur être une heuristique pour choisir un segment candidat, mais je ne pense pas que ca soit suffisant pour construire à coup sûr une triangulation de Delaunay.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    J
    Ca peut bien sur être une heuristique pour choisir un segment candidat, mais je ne pense pas que ca soit suffisant pour construire à coup sûr une triangulation de Delaunay.
    Disons que mon questionnement était en sens inverse :

    Si j'obtiens le segment du polygone à la fois le plus proche et donnant l'angle maximum, pourrais-je dire que ce segment définit avec le point un triangle de Delaunay ?


    (dans ce cas, bien que cela ne construise pas la triangulation, on aurait sans conteste un des triangles partant du point. A la limite, on pourrait itérer en laissant ce segment de côté pour obtenir les autres triangles issus de ce point)
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

Discussions similaires

  1. Question à propos des compilateurs
    Par elf dans le forum Autres éditeurs
    Réponses: 4
    Dernier message: 20/07/2005, 18h00
  2. Question à propos des niveaux de transaction
    Par davy.g dans le forum Oracle
    Réponses: 3
    Dernier message: 18/01/2005, 16h31
  3. Petite question à propos du redbook...
    Par Michaël dans le forum OpenGL
    Réponses: 3
    Dernier message: 04/11/2004, 13h54
  4. Petite question à propos d'une requete
    Par ViBy dans le forum Langage SQL
    Réponses: 4
    Dernier message: 15/09/2004, 13h21
  5. Une question à propos des thread
    Par tscoops dans le forum C++Builder
    Réponses: 4
    Dernier message: 07/11/2003, 15h03

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