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 :

Sélection des points les moins alignés/proches


Sujet :

Algorithmes et structures de données

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

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

    Informations forums :
    Inscription : janvier 2006
    Messages : 5 791
    Points : 9 857
    Points
    9 857
    Par défaut Sélection des points les moins alignés/proches
    Bonjour,

    j'ai un petit problème de sélection de points... que voilà :
    - parmi un ensemble de N points (N petits, donc recherche exhaustive possible)
    - je veux sélectionner quatre points qui sont les moins alignés (en priorité) et si possible qui sont aussi les moins proches.

    *** Pour cela j'ai déjà imaginé de parcourir tous les quadruplés possible et pour chacun, calculer la sommes des angles formés par tous les triplets de points du quadruplés étudié.

    *** Une variante serait de parcourir tous les quadruplés et le score de chacun serait l'angle minimum des triplets.

    Cette dernière me m'assurerait de ne pas avoir les points alignés. Ensuite il faudrait que je discrimine pour rapport à la distance (ce qui est plus facile), comme par exemple calculer la somme des distances au barycentre de chaque quadruplé.


    Est ce que quelqu'un verrait d'autres solutions ?
    Merci par avance.
    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.

  2. #2
    Membre expérimenté
    Homme Profil pro
    Chercheur
    Inscrit en
    mars 2010
    Messages
    1 218
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : mars 2010
    Messages : 1 218
    Points : 1 685
    Points
    1 685
    Par défaut
    Bonsoir,

    en quelle dimension travailles-tu?

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

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

    Informations forums :
    Inscription : janvier 2006
    Messages : 5 791
    Points : 9 857
    Points
    9 857
    Par défaut
    Citation Envoyé par Aleph69 Voir le message
    en quelle dimension travailles-tu?
    juste 2, faudrait pas que ce soit trop dur ;-)
    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
    Invité(e)
    Invité(e)
    Par défaut
    Bonsoir,

    A votre place, je trierai les quadruplets suivant le résultat de cette valeur V :

    V(A,B,C,D) = ABxCD + ACxBD + ADxBC.

    Où AB est le vecteur AB, et x le produit scalaire.

    Plus V est grand, plus les points sont non-alignés.
    Dernière modification par Invité(e) ; 27/09/2010 à 23h48.

  5. #5
    Expert éminent sénior

    Profil pro
    Inscrit en
    janvier 2007
    Messages
    10 591
    Détails du profil
    Informations personnelles :
    Âge : 64
    Localisation : France

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 591
    Points : 17 295
    Points
    17 295
    Billets dans le blog
    2
    Par défaut
    je propose :

    • un quck sort sur les distances

    • suivi d'une exploration à partir de la fin du tableau pour éliminer les points alignés



    Maintenant, en prenant les critères d'alignement en tête :

    • une régression linéaire

    • suivie d'un tri par rapport à la distance à cette régression (et le delta)

    • suivi d'un tri sur les distances point à point



    Solutions à 2 balles, vite fait..

    "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

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 062
    Points : 15 892
    Points
    15 892
    Par défaut
    Ca ressemble à la détection d'outlier dans un modèle linéaire. Je pense que le sujet à déjà été traité dans la littérature.

    Perso, je vote pour RANSAC, ou une de ses variantes.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

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

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

    Informations forums :
    Inscription : janvier 2006
    Messages : 5 791
    Points : 9 857
    Points
    9 857
    Par défaut
    Citation Envoyé par mabu Voir le message
    A votre place, je trierai les quadruplets suivant le résultat de cette valeur V :
    V(A,B,C,D) = ABxCD + ACxBD + ADxBC.
    Où AB est le vecteur AB, et x le produit scalaire.
    Plus V est grand, plus les points sont non-alignés.
    Intéressant... je vais tester.

    Citation Envoyé par souviron34 Voir le message
    je propose :
    • un quck sort sur les distances
    • suivi d'une exploration à partir de la fin du tableau pour éliminer les points alignés

    Maintenant, en prenant les critères d'alignement en tête :
    • une régression linéaire
    • suivie d'un tri par rapport à la distance à cette régression (et le delta)
    • suivi d'un tri sur les distances point à point

    Solutions à 2 balles, vite fait..
    Les solutions les plus simples sont souvent les meilleures, mais ici je risque de n'avoir que très peu de quadruplés. D'un point de vue statistique, je crains que le la régression soit instable car le nombre de points pour la construire est très/trop faible. De plus, la régression est intéressante mais je crains particulièrement l'alignement de triplets.


    Citation Envoyé par pseudocode Voir le message
    Ca ressemble à la détection d'outlier dans un modèle linéaire. Je pense que le sujet à déjà été traité dans la littérature.
    Perso, je vote pour RANSAC, ou une de ses variantes.
    Mmm... détection d'outliers sur un aussi petit nombre de points... ça risque d'être difficile. Non ?
    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.

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 062
    Points : 15 892
    Points
    15 892
    Par défaut
    Citation Envoyé par ToTo13 Voir le message
    Mmm... détection d'outliers sur un aussi petit nombre de points... ça risque d'être difficile. Non ?
    Bah ca dépend de ta définition de petit.

    A bien relire le PO, je me rend compte que les 4 points que tu cherches ne sont pas forcément des outliers comme je le pensais. Ca m'apprendra a lire une question aussi tard. En effet, il ne s'agit pas forcément de trouver les ponts qui correspondent le moins a un modèle linéaire.

    Donc je retire ma suggestion initiale.

    Est-ce que ca ne serait pas plutot des points situés aux extrémités des deux axes principaux ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

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

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

    Informations forums :
    Inscription : janvier 2006
    Messages : 5 791
    Points : 9 857
    Points
    9 857
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    Est-ce que ca ne serait pas plutot des points situés aux extrémités des deux axes principaux ?
    Non plus :-(
    Ceux sont des points répartis de manière quelconque, voire quasi aléatoire dans un espace 2D.
    Et pour la suite de mon traitement, je dois prendre le quadruplé qui doit contenir les points les moins alignés possibles, car plus ils sont alignés, moins les résultats sont pertinents (erreurs d'approximation numérique).
    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.

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 062
    Points : 15 892
    Points
    15 892
    Par défaut
    Citation Envoyé par ToTo13 Voir le message
    Non plus :-(
    Ceux sont des points répartis de manière quelconque, voire quasi aléatoire dans un espace 2D.
    Et pour la suite de mon traitement, je dois prendre le quadruplé qui doit contenir les points les moins alignés possibles, car plus ils sont alignés, moins les résultats sont pertinents (erreurs d'approximation numérique).
    Je pense qu'il faudrait définir plus rigoureusement la notion de "4 points les moins alignés possibles".

    En gros, La proposition de mabu semble etre la maximisation de l'aire du quadrilatère, celle se Souviron le maximum de variance et la mienne (PCA) le maximum de décorrélation.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

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

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

    Informations forums :
    Inscription : janvier 2006
    Messages : 5 791
    Points : 9 857
    Points
    9 857
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    Je pense qu'il faudrait définir plus rigoureusement la notion de "4 points les moins alignés possibles".
    En étant exact, il ne faut surtout pas que j'ai trois points alignés dans le quadruplé. Donc c'est pour ça que je parlais de quatre points les moins alignés possibles.
    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.

  12. #12
    Membre éprouvé Avatar de Nemerle
    Inscrit en
    octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 51

    Informations forums :
    Inscription : octobre 2003
    Messages : 1 106
    Points : 1 199
    Points
    1 199
    Par défaut
    Pour chacun des quadruplets de point (P1...P4):

    - tu prends i,j tel que d1=d(Pi,Pj) soit maximal
    - tu calcules pour les 2 autres point Pk,Pl leurs distances à la droite (PiPj),
    et tu notes d2 la somme de ces deux distances

    Tu cherches alors le quadruplets tel que d1*d2 soit maximal par exemple.
    Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre

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

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

    Informations forums :
    Inscription : janvier 2006
    Messages : 5 791
    Points : 9 857
    Points
    9 857
    Par défaut
    Finalement, il semble que prendre le quadruplé qui possède le plus grand des plus petits angles formés par les triplets qui le compose, soit une bonne solution.


    PS :
    Citation Envoyé par mabu Voir le message
    A votre place, je trierai les quadruplets suivant le résultat de cette valeur V :
    V(A,B,C,D) = ABxCD + ACxBD + ADxBC.
    Où AB est le vecteur AB, et x le produit scalaire.
    Plus V est grand, plus les points sont non-alignés.
    Je suis très étonné, mais cette méthode n'a pas donné de bons résultats :-(
    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.

  14. #14
    Membre éprouvé Avatar de Nemerle
    Inscrit en
    octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 51

    Informations forums :
    Inscription : octobre 2003
    Messages : 1 106
    Points : 1 199
    Points
    1 199
    Par défaut
    Citation Envoyé par ToTo13
    Finalement, il semble que prendre le quadruplé qui possède le plus grand des plus petits angles formés par les triplets qui le compose, soit une bonne solution.
    A mon tour d'être étonné... une condition uniquement angulaire donnera effectivement de bon résultats concernant l'éloignement mutuel des 4 points, mais ne tiendra pas compte réellement de la notion d'éloignement de DISTANCE.

    Si tu prends une configuration de 4 points, que tu effectues une homothétie de rapport >1 et de centre la moyenne des 4 points, tu auras le même plus grands des petits angles, mais tes points seront "plus" éloignés...
    Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 062
    Points : 15 892
    Points
    15 892
    Par défaut
    Citation Envoyé par ToTo13 Voir le message
    Je suis très étonné, mais cette méthode n'a pas donné de bons résultats :-(
    Si le but était de trouver le quadrilatère d'aire maximale, j'aurais pris le Max des 3 produits plutot que la somme. J'aurais également essayé de normaliser un peu le résultat, par exemple en divisant par le périmètre.

    Faudra que je teste pour voir ce que ca donne.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

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

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

    Informations forums :
    Inscription : janvier 2006
    Messages : 5 791
    Points : 9 857
    Points
    9 857
    Par défaut
    Citation Envoyé par Nemerle Voir le message
    A mon tour d'être étonné... une condition uniquement angulaire donnera effectivement de bon résultats concernant l'éloignement mutuel des 4 points, mais ne tiendra pas compte réellement de la notion d'éloignement de DISTANCE.
    C'est l'alignement qui me causait principalement des problèmes !
    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.

  17. #17
    Membre expérimenté
    Homme Profil pro
    Chercheur
    Inscrit en
    mars 2010
    Messages
    1 218
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : mars 2010
    Messages : 1 218
    Points : 1 685
    Points
    1 685
    Par défaut
    Bonjour,

    je me demande s'il ne serait pas possible d'accélérer un peu le calcul en considérant d'abord les triplets de points et en regardant la qualité du triangle qu'ils forment. J'entends par qualité les mesures qu'on utilise habituellement dans les triangulations de Delaunay, par exemple le rapport entre l'aire du cercle inscrit dans un triangle et le diamètre de ce triangle. Si le triangle est trop aplati, alors ça n'est pas utile de considérer les quadruplets qu'il définit car, si j'ai bien compris, quatre points le moins alignés possible forment un carré parfait.

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

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

    Informations forums :
    Inscription : janvier 2006
    Messages : 5 791
    Points : 9 857
    Points
    9 857
    Par défaut
    Citation Envoyé par Aleph69 Voir le message
    je me demande s'il ne serait pas possible d'accélérer un peu le calcul en considérant d'abord les triplets de points et en regardant la qualité du triangle qu'ils forment. J'entends par qualité les mesures qu'on utilise habituellement dans les triangulations de Delaunay, par exemple le rapport entre l'aire du cercle inscrit dans un triangle et le diamètre de ce triangle. Si le triangle est trop aplati, alors ça n'est pas utile de considérer les quadruplets qu'il définit car, si j'ai bien compris, quatre points le moins alignés possible forment un carré parfait.
    Effectivement, c'est un critère très intéressant. Il faut que je teste.
    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.

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

Discussions similaires

  1. Algorithme de sélection des points pour construire un modèle numérique de terrain
    Par Senadin dans le forum Algorithmes et structures de données
    Réponses: 0
    Dernier message: 06/06/2014, 10h18
  2. Sélection des points avec OpenGl
    Par moooona dans le forum OpenGL
    Réponses: 6
    Dernier message: 11/07/2011, 11h56
  3. algorithme des deux points les plus proches
    Par biba1980 dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 10/11/2009, 05h18
  4. [Complexité] recherche des n points les plus proches d'un point dans une liste
    Par Benoit_T dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 20/06/2009, 16h55
  5. Sélection des doublons les plus récents
    Par nitramm dans le forum Langage SQL
    Réponses: 2
    Dernier message: 13/06/2008, 10h37

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