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

Mathématiques Discussion :

Plus petit quadrilatère quelconque englobant un ensemble de points en 2D


Sujet :

Mathématiques

  1. #1
    Membre régulier
    Profil pro
    Inscrit en
    Septembre 2008
    Messages
    248
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : Canada

    Informations forums :
    Inscription : Septembre 2008
    Messages : 248
    Points : 119
    Points
    119
    Par défaut Plus petit quadrilatère quelconque englobant un ensemble de points en 2D
    Salut,

    Connaissant les coordonnées d'un ensemble de points dans le repère (XY), je cherche un algorithme permettant de trouver les 4 sommets du plus petit quadrilatère englobant ces points ou du quadrilatère approximant le mieux possible la surface formée par ces points.

    Il existe des algorithmes permettant de trouver l'envellope convex d'un ensemble de points (Graham scan) mais le problème c'est que cette enveloppe n'est pas necessairement un quadrilatère.

    - Les 4 sommets du quadrilatère recherchés peuvent faire partie de l'ensemble de points ou non, ca dérange pas.

    toute suggestion, complète ou non est appréciée !

  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
    Citation Envoyé par Nehmé Voir le message
    toute suggestion, complète ou non est appréciée !
    et tout effort de ta part, complet ou non, dans la recherche et l'exposé de ta pensée et de ta solution, est apprécié
    "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
    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
    Bonjour,

    renseigne toi sur tout ce qui est : "bounding box" ou "oriented bounding box". c'est comme cela que ce nomme ton problème.

    Tu peux utiliser l'enveloppe convexe pour diminuer le nombre de point dans la recherche de solution.
    Ensuite l'axe principal permet d'avoir une bonne première boite pour initialiser la recherche.
    Ensuite comme tu es en 2D, je te conseille une petite recherche exhaustive...
    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.

  4. #4
    Inactif  
    Profil pro
    Inscrit en
    Septembre 2008
    Messages
    357
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2008
    Messages : 357
    Points : 637
    Points
    637
    Par défaut
    Commencer par une enveloppe convexe puis énumérer les quadrilatères passant par les sommets de l'enveloppe ? Même en 2D ça risque d'être violent.

    Les algos bounding box construisent des rectangles ? Pour un quadrilatère quelconque ça change beaucoup de choses.

  5. #5
    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
    En premiere approximation, est-ce que les sommets du quadrilatere recherché ne seraient pas sur les 2 axes principaux (analyse PCA) ?

    Il y a également le problème des quadrilateres non-convexe, mais je suppose que c'est hors sujet.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  6. #6
    Membre régulier
    Profil pro
    Inscrit en
    Septembre 2008
    Messages
    248
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : Canada

    Informations forums :
    Inscription : Septembre 2008
    Messages : 248
    Points : 119
    Points
    119
    Par défaut
    Merci pour vos réponses.

    J'ai dejà réussi à trouver la bounding box orientée qui est effectivement un rectangle. J'ai fait ceci en faisant une rotation de points de 0 à 90 degrés avec un pas choisi. A chaque pas je trouve l'aire de la bounding box et une fois les 90 degrés parcourus je prends la bounding box ayant l'aire la plus petite et je la retourne de -theta à la position initiale des points.
    Le problème que c'est un rectangle que j'ai ici et pour plusieurs cas c'est une mauvaise approximation.
    C'est pourquoi je cherche un quadrilatère quelconque qui pourra s'adapter au cas et à la forme de l'enveloppe formée par les points.
    J'ai cherché longtemps sur google et j'ai essayé de trouver une solution mais j'ai pas encore trouvé mieux que la bounding box orientée.
    Je cherche pas une solution complète mais des idées...
    Merci encore !

    Il existe aussi l'idée du plus petit parallélogramme, mais c'est une solution limitée aussi et une mauvaise approximation pour plusieurs cas.

  7. #7
    Membre éclairé
    Profil pro
    Inscrit en
    Août 2008
    Messages
    505
    Détails du profil
    Informations personnelles :
    Localisation : France, Puy de Dôme (Auvergne)

    Informations forums :
    Inscription : Août 2008
    Messages : 505
    Points : 712
    Points
    712
    Par défaut
    Ca veut dire quoi, le plus petit quadrilatère ?
    Celui dont l'aire est minimale ? Celui dont le périmètre est minimal ? C'est pas forcément la même chose. Je me trompe ?

  8. #8
    Membre régulier
    Profil pro
    Inscrit en
    Septembre 2008
    Messages
    248
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : Canada

    Informations forums :
    Inscription : Septembre 2008
    Messages : 248
    Points : 119
    Points
    119
    Par défaut
    je suis d'accord que dans certain cas c'est pas pareil, mais c'est pas important pour moi. L'important c'est que ce quadrilatère approxime le mieux possible l'enveloppe convexe. Dans mon cas le quadrilatère ayant l'aire la plus proche de l'aire de l'enveloppe convexe est le meilleur, mais pour d'autres applications le critère de périmètre serait plus pertinent. De toute façon, que ce soit basé sur le périmètre ou l'aire ça me conviendrai !

    Merci

  9. #9
    Membre éclairé

    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 717
    Points : 858
    Points
    858
    Par défaut
    Citation Envoyé par Nehmé Voir le message
    Connaissant les coordonnées d'un ensemble de points dans le repère (XY), je cherche un algorithme permettant de trouver les 4 sommets du plus petit quadrilatère englobant ces points ou du quadrilatère approximant le mieux possible la surface formée par ces points.
    Je ne comprend pas la fin.

    Pour le plus petit quadrilatère englobant, cela me parait pas très difficile. Il est facile de voir que ce quadrilatère passe forcement par 4 des points (sinon il ne serait pas le plus petit). Du coup il suffit de tester toutes les combinaisons de 4 points et de retenir celle qui donne le plus petit quadrilatère englobant. Si c'est trop lent il doit avoir moyen d'utiliser des heuristiques pour éviter certaines combinaisons.

  10. #10
    Membre régulier
    Profil pro
    Inscrit en
    Septembre 2008
    Messages
    248
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : Canada

    Informations forums :
    Inscription : Septembre 2008
    Messages : 248
    Points : 119
    Points
    119
    Par défaut
    Faut pas oublier aussi la forme du quadrilatère. sinon avec un rectangle on peut obtenir la même air ou le même perimètre. En gros le quadrilatère engloppant tous les points et ayant la plus petite air ou perimètre et le meilleur. Tu peux immaginer 4 ammortisseurs soudés ensembles sur leurs sommets et que tu veux les placer le mieux possible autour de l'enveloppe formée par les points.

    Le quadrilatère passant par 4 points n'est pas souvent le plus petit. fait le pour un hexagonne et tu verras.

    Citation Envoyé par pseudocode Voir le message
    En premiere approximation, est-ce que les sommets du quadrilatere recherché ne seraient pas sur les 2 axes principaux (analyse PCA) ?

    Il y a également le problème des quadrilateres non-convexe, mais je suppose que c'est hors sujet.

    Je ne suis pas sure de qu'est ce que c'est les 2 axes principaux d'un ensemble de points ?

  11. #11
    Membre éclairé

    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 717
    Points : 858
    Points
    858
    Par défaut
    Citation Envoyé par Nehmé Voir le message
    Le quadrilatère passant par 4 points n'est pas souvent le plus petit. fait le pour un hexagonne et tu verras.
    Lequel ? Il y en a une infinité !

    Par contre le plus petit quadrilatère englobant passe forcement par au moins 4 points (de l'enveloppe convexe, d'ailleurs).

  12. #12
    Membre régulier
    Profil pro
    Inscrit en
    Septembre 2008
    Messages
    248
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : Canada

    Informations forums :
    Inscription : Septembre 2008
    Messages : 248
    Points : 119
    Points
    119
    Par défaut
    Citation Envoyé par Sylvain Togni Voir le message
    Lequel ? Il y en a une infinité !

    Par contre le plus petit quadrilatère englobant passe forcement par au moins 4 points (de l'enveloppe convexe, d'ailleurs).
    en pièce jointe un hexagone et un exemple de quadrilatère englobant. trouve moi un meilleur passant par 4 points de l'hexagone
    Images attachées Images attachées  

  13. #13
    Membre éclairé

    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 717
    Points : 858
    Points
    858
    Par défaut
    Petit soucis sémantique peut-être, parce que pour moi ce quadrilatère passe par 4 points (par 6 plus exactement).

  14. #14
    Membre régulier
    Profil pro
    Inscrit en
    Septembre 2008
    Messages
    248
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : Canada

    Informations forums :
    Inscription : Septembre 2008
    Messages : 248
    Points : 119
    Points
    119
    Par défaut
    Citation Envoyé par Sylvain Togni Voir le message
    Petit soucis sémantique peut-être, parce que pour moi ce quadrilatère passe par 4 points (par 6 plus exactement).
    Ok je comprend ce que tu veux dire !
    les segment du plus petit quadrilatère passe par 4 points mais les sommets de ce quadrilatère ne font pas necessairement partie de l'ensemble de points.

    ok oui à première vue je crois que je suis d'accord.

  15. #15
    Membre expérimenté

    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2006
    Messages
    450
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Avril 2006
    Messages : 450
    Points : 1 630
    Points
    1 630
    Par défaut
    Problème intéressant. Je pense qu'avant de commencer à réfléchir sur un algo il faudrait se demander si notre quadrilatère a plus de contraintes que de passer par 4 points de l'enveloppe convexe. Et encore faudrait déjà démontrer ce dernier mathématiquement.

    Comme autre contrainte on pourrait penser qu'il passe par une arête ou deux de l'enveloppe convexe, etc. Mais comme je suis nul en topologie je ne pourrais pas vous aider plus que ça .
    Je ne réponds à aucune question par MP, posez vos questions sur le forum adéquat.
    Profils : G+ - LinkedIn

  16. #16
    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
    Citation Envoyé par TanEk Voir le message
    il faudrait se demander si notre quadrilatère a plus de contraintes que de passer par 4 points de l'enveloppe convexe.
    Contre-exemple: un "cercle" (ou du moins un polygone regulier avec beaucoups de cotés). Les sommets du quadrilatere englobant ne sont pas des points du "cercle".
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  17. #17
    Membre régulier
    Profil pro
    Inscrit en
    Septembre 2008
    Messages
    248
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : Canada

    Informations forums :
    Inscription : Septembre 2008
    Messages : 248
    Points : 119
    Points
    119
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    Contre-exemple: un "cercle" (ou du moins un polygone regulier avec beaucoups de cotés). Les sommets du quadrilatere englobant ne sont pas des points du "cercle".

    TanEk veut dire que les segments du quadrilatère passe par 4 points du cercle ou du polygone et non pas que les sommets du quadrilatère conside avec 4 des sommets du polygone par exemple... on en a dejà en parler dans les messages précedent. regarde ds la page 1 l'exemple de l'hexagone

  18. #18
    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
    Citation Envoyé par Nehmé Voir le message
    TanEk veut dire que les segments du quadrilatère passe par 4 points du cercle ou du polygone et non pas que les sommets du quadrilatère conside avec 4 des sommets du polygone par exemple...
    Ah... ok. Je n'avais pas compris, désolé.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  19. #19
    Expert confirmé
    Homme Profil pro
    Inscrit en
    Septembre 2006
    Messages
    2 934
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Septembre 2006
    Messages : 2 934
    Points : 4 347
    Points
    4 347
    Par défaut
    Citation Envoyé par Nehmé Voir le message
    Salut,

    Connaissant les coordonnées d'un ensemble de points dans le repère (XY), je cherche un algorithme permettant de trouver les 4 sommets du plus petit quadrilatère englobant ces points ou du quadrilatère approximant le mieux possible la surface formée par ces points.

    Il existe des algorithmes permettant de trouver l'envellope convex d'un ensemble de points (Graham scan) mais le problème c'est que cette enveloppe n'est pas necessairement un quadrilatère.

    - Les 4 sommets du quadrilatère recherchés peuvent faire partie de l'ensemble de points ou non, ca dérange pas.

    toute suggestion, complète ou non est appréciée !
    Suggestion donc :

    le meilleur polygone qui englobe le polygone convexe est lui-même mais s'il a plus de côtés que ce qu'autorise l'énoncé du problème, il faut lui en enlever jusqu'au moment où l'on atteint le nombre de côtés autorisés (ici 4)

    la suppression d'un côté se faisant en prolongeant les côtés adjacents jusqu'à leur intersection…
    pour décider quels côtés on supprime, on choisit à chaque fois celui dont la suppression ajoute le plus petit triangle, le polygone convexe est donc modifié à chaque étape…

    pour chaque triangle ajouté on a les 3 angles (180-a1, 180-a2 et a1+a2-180) et la dimension d'un côté, la surface est facile à calculer…

    la condition pour pouvoir supprimer un côté est que la somme des angles intérieurs avec les côtés adjacents soient > 180°…

  20. #20
    Membre régulier
    Profil pro
    Inscrit en
    Septembre 2008
    Messages
    248
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : Canada

    Informations forums :
    Inscription : Septembre 2008
    Messages : 248
    Points : 119
    Points
    119
    Par défaut
    Citation Envoyé par JeitEmgie Voir le message
    Suggestion donc :

    le meilleur polygone qui englobe le polygone convexe est lui-même mais s'il a plus de côtés que ce qu'autorise l'énoncé du problème, il faut lui en enlever jusqu'au moment où l'on atteint le nombre de côtés autorisés (ici 4)

    la suppression d'un côté se faisant en prolongeant les côtés adjacents jusqu'à leur intersection…
    pour décider quels côtés on supprime, on choisit à chaque fois celui dont la suppression ajoute le plus petit triangle, le polygone convexe est donc modifié à chaque étape…

    pour chaque triangle ajouté on a les 3 angles (180-a1, 180-a2 et a1+a2-180) et la dimension d'un côté, la surface est facile à calculer…

    la condition pour pouvoir supprimer un côté est que la somme des angles intérieurs avec les côtés adjacents soient > 180°…
    Merci pour ton idée, ca l'air intéressant !
    Je vais voir ca plus en détails et je te donnerai des nouvelles.

Discussions similaires

  1. algo pour déterminer le plus petit cercle circonscrit d'un convexe quelconque
    Par [Hugo] dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 27/02/2008, 13h06
  2. Afficher le plus petit des nombres
    Par wkm1807 dans le forum Access
    Réponses: 1
    Dernier message: 06/10/2005, 00h46
  3. [TP] Tirer 10 dates et afficher la plus petite
    Par moustaphes dans le forum Turbo Pascal
    Réponses: 5
    Dernier message: 16/08/2005, 10h54
  4. [CR8.5] le plus petit numéro de commande
    Par Damien69 dans le forum Formules
    Réponses: 3
    Dernier message: 26/05/2004, 11h35
  5. Réponses: 3
    Dernier message: 16/12/2002, 17h12

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