1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2017
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Saône et Loire (Bourgogne)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : mai 2017
    Messages : 2
    Points : 1
    Points
    1

    Par défaut Tri d'un ensemble de points 2D

    Bonjour à tous
    Dans le but d'optimiser le parcours d'une machine à commande numerique
    voila une photo de l'application sur bois : (là c'est un essai en petit)

    je cherche un algo qui permet de joindre tous les polygones cote à cote (si possible). (ensuite je trouverais un autre algo qui permettra de creer qu'une seule ligne)
    ca peut etre en spirale en partant de l'exterieur ou en ligne de haut en bas, de gauche à droite puis droite à gauche etc (j'ai une fonction qui permet de calculer le centre de chaque polygone)


    En fait , j'ai fait un premier algo pour essayer de faire qu'une seule ligne:
    Je decomposais tous les polygones puis j'effacais les doublons (lignes et points)
    Apres je cherche les points de degré impairs
    j'applique l'algo de dijskstra pour creer des lignes supplementaires pour joindre les impairs 2 par 2 par leur chemin le + court pour n'avoir que des points de degré pairs et ainsi pouvoir appliquer l'algo de d'euler (mais il ne fallait pas quil y ait 3 segments qui se superposent ...)
    ensuite je fais l'algo d'euler pour joindre toutes les lignes en une seule (qui fonctionne que si tous les points sont de degré pairs)
    le problème c'est qu'il y avait toujours des cas particuliers , c'etait beaucoup trop compliqué , j'y ai passé trop de temps pour que ca ne marche pas. C'est un peu comme qd on attend le bus, a partir de quel moment on s'en va ou non ...

    Avez vous des idées ?

    Pierre
    Images attachées Images attachées  

  2. #2
    Membre éclairé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    349
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 70
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 349
    Points : 716
    Points
    716
    Billets dans le blog
    5

    Par défaut Tri d'un ensemble de points 2D

    Bonjour,

    Tu as à priori fait l'inventaire des polygones, de leurs arêtes et de leurs sommets, ainsi que de leur centre Ck(xk, yk) - barycentre des sommets sans doute ? mais passons. C'est un bon départ.

    Citation Envoyé par bebdoo Voir le message
    ... je cherche un algo qui permet de joindre tous les polygones côte à côte (si possible). (ensuite je trouverais un autre algo qui permettra de créer qu'une seule ligne)
    Ça peut être en spirale en partant de l'extérieur ou en ligne de haut en bas, de gauche à droite puis droite à gauche etc (j'ai une fonction qui permet de calculer le centre de chaque polygone) ...
    C'est là qu'on aborde le fond du problème: l'inventaire systématique des polygones suppose la définition d'une relation d'ordre entre eux (ou leurs centres, ce qui revient au même), définition intrinsèquement liée au mode de parcours du domaine considéré:
    Par exemple (Ci) a préséance sur (Cj) si et seulement si:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    // Critère (1): balayage vertical
     Test1:= ((X[i]<X[j]) OR ((X[i]=X[j]) AND (Y[i]<Y[j])));
    
    // Critère (2): balayage horizontal
     Test2:= ((Y[i]<Y[j]) OR ((Y[i]=Y[j]) AND (X[i]<X[j])));
    
    // Critère (3): balayage en diagonale
     Test3:= ((X[i]+Y[i]<X[j]+Y[j]) OR ((X[i]+Y[i]=X[j]+Y[j])  AND (Y[i]<Y[j])));
    mais le parcours n'aura de sens qu'après installation d'un super-quadrillage comportant (Nx) colonnes et (Ny) lignes, calculées à partir des dimensions du domaine, et du nombre (Np) de polygones présents:
    Nx = Round(Larg / Sqrt(Np)) ; Ny = Round((Haut / Sqrt(Np)) .
    La définition de coordonnées secondaires relatives à la case du damier ainsi défini, et dans laquelle se trouve (C[k])
    U[k] = Trunc(X[k]) / Nx) , V[k] = Trunc(Y[k]) / Ny)
    permet d'envisager un parcours moins chaotique, en raison d'une réduction drastique des choix possibles:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    // Critère (1): balayage vertical de haut en bas
    
    Test1:= ((U[i]<U[j]) OR ((U[i]=U[j]) AND ((V[i]<V[j]) OR ((V[i]=V[j]) AND (Y[i]<Y[j]))))) ;
    
    // Critère (2): balayage horizontal de gauche à droite
    
    Test2:= ((V[i]<V[j]) OR ((V[i]=V[j]) AND ((U[i]<U[j]) OR ((U[i]=U[j]) AND (X[i]<X[j]))))) ;
    Un parcours alternatif , comportant des zigzags, apparaîtra encore plus difficile à coder. Pour une progression spiralaire effectuée à partir du centre, impliquant une comparaison des couples (rk, tk), il faudra constamment ré-évaluer les (Np - k) angles polaires restant, qui ne sont définis qu'à (2*Pi) près; cependant l'obstacle n'est pas rédhibitoire.

    Il faut considérer le graphe dual associé à la partition du domaine, dont les sommets sont les centres des polygones (1), et admettant pour arêtes l'ensemble (EA) des arcs vérifiant:
    (CiCj) appartient à (EA) si et seulement si (Poli) adjacent à (Polj) .
    Tu cherches en fait un parcours hamiltonien, et il n'est pas évident qu'un tel parcours existe, les limites du domaine constituant une contrainte importante.

    Citation Envoyé par bebdoo Voir le message
    ... je cherche un algo qui permet de joindre tous les polygones côte à côte (si possible) ...
    Un parcours en spirale amorcé sur le polygone le plus central, et recherchant en priorité les domaines adjacents les plus proches, constituera une solution acceptable ... mais il ne faudra guère compter sur une suite ininterrompue de polygones adjacents.
    On peut aussi envisager une présélection grossière des centres, utilisant le quadrillage précédemment décrit.

    (1) Plus les quatre coins du domaine ...


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  3. #3
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 246
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 246
    Points : 2 634
    Points
    2 634

    Par défaut

    Ce que tu cherches à faire, c'est :
    - relier tous les polygones par une ligne, en passant une fois et une seule par chaque polygone, point final.
    - relier tous les polygones par une ligne, en passant une fois et une seule par chaque polygone, et en appliquant un thème ( spirale, zig-zag .... )

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 020
    Points : 15 566
    Points
    15 566

    Par défaut

    Citation Envoyé par bebdoo Voir le message
    je cherche un algo qui permet de joindre tous les polygones cote à cote (si possible).
    Ce n'est pas toujours possible.

    +--+---+--+
    |  |   |  |
    +--+   +--+
    |         |
    +---------+
    |         |
    +---------+
    
    Ceci étant posé, comme le dis wiwaxia, il te faut une règle pour définir un ordre.

    Par exemple, se déplacer vers le prochain polygone non traversé qui a son centre le plus près du bord (parcours en spirale).
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2017
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Saône et Loire (Bourgogne)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : mai 2017
    Messages : 2
    Points : 1
    Points
    1

    Par défaut

    Merci pour vos réponses
    Pseudocode, je pense que je n'aurais jamais ce cas de figure car j'aurais toujours un grand nombre de polygones et ce ne sera pas possible qu'un polygone touche à la fois l'arete gauche et droite du rectangle englobant

    Par exemple, se déplacer vers le prochain polygone non traversé qui a son centre le plus près du bord (parcours en spirale).
    c'est une très bonne idée, il faut que je regarde comment je peux coder ca, cet algo ce serait l'idéal, (en zigzag serait bien aussi )


    Pour le moment j'arrive juste à faire un tri d'abord des Y puis des X, ce n'est pas terrible
    voila l'algorithme, en gros: j'explose tous les polygones, je récupere chaque point (Vertices), j'additionne leur (X*1000) + Y pour chaque point, et je fais un tri des polygones avec cette valeur:
    Nom : Capture d’écran 2017-05-23 à 09.22.10.png
Affichages : 27
Taille : 107,8 Ko

    Ca me donne ca :

    Nom : Capture d’écran 2017-05-23 à 09.14.33.png
Affichages : 28
Taille : 48,6 Ko

    Je vais laisser tomber le parcours hamiltonien s'il y a trop de cas particuliers

  6. #6
    Membre expert
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 388
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 388
    Points : 3 735
    Points
    3 735

    Par défaut

    salut

    il y a pas de cas particulier
    en prenant les centres des polygones et les arrêtes commune à deux polygones tu devrais t'en sortir sans soucis
    il faut juste vérifier que le lien entre deux polygone n'as pas déjà été créé
    donc on résume
    1°) tu fais la liste de tout les polygone(liste des points et des droite constituant ton polygone)
    2°) tu calcul pour chaque polygone le centre et tu recenses tous ces voisins
    3°)pour chaque polygone tu prend le centre et tu le relis au centre de son voisin en vérifiant que tu n'as pas déjà créé le liens
    normalement une fois fait ça tu as obtenu ton graphe
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  7. #7
    Membre éclairé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    349
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 70
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 349
    Points : 716
    Points
    716
    Billets dans le blog
    5

    Par défaut Tri d'un ensemble de points 2D

    Il me vient une idée idiote, mais qui répond littéralement à l'énoncé de ton projet:
    Citation Envoyé par bebdoo Voir le message
    ... je cherche un algo qui permet de joindre tous les polygones côte à côte (si possible). (ensuite je trouverais un autre algo qui permettra de créer qu'une seule ligne) ...
    appliquer à l'ensemble des centres (Ck) l'algorithme du voyageur de commerce, qui te permettra de relier les points les plus proches, à défaut de correspondre à des polygones adjacents; tu ne perds rien sur ce point, le graphe dual n'étant probablement pas hamiltonien.

    Si l'idée d'une chaîne fermée te gêne, tu peux t'orienter vers la recherche du plus court trajet entre deux points extrêmes, qui n'est qu'une variante du problème précédent.
    Les points en cause seraient donnés par les valeurs extrêmes de la somme (Sk = xk + yk): minimum (coin supérieur gauche) et maximum (coin inférieur droit).

    Cela implique bien sûr de renoncer au type de parcours dont tu rêvais, en zigzags quasi-parallèles à l'un des bords ou l'une des diagonales; cependant cette idée séduisante me paraît tout aussi illusoire que la précédente, ou tout au moins très difficile à réaliser ... Y renoncer t'épargnerait sans doute beaucoup d'ennuis - à moins évidemment qu'un autre intervenant ne propose une solution inattendue.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

Discussions similaires

  1. Réponses: 5
    Dernier message: 16/02/2007, 15h53
  2. Tri par distance d'un point origine
    Par business dans le forum Syntaxe
    Réponses: 4
    Dernier message: 27/04/2006, 07h19
  3. boule minimale contenant un ensemble de points
    Par tlemcenvisit dans le forum Général Algorithmique
    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