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 :

Détermination de l'appartenance d'un point à un carré


Sujet :

Algorithmes et structures de données

  1. #1
    Membre régulier
    Profil pro
    Inscrit en
    mars 2003
    Messages
    121
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mars 2003
    Messages : 121
    Points : 81
    Points
    81
    Par défaut Détermination de l'appartenance d'un point à un carré
    Bonjour à tous,

    Je dispose d'un série de carrés formant une grille carrée de N carrés par N carrés. N est impair et peut aller jusqu'à 11 ou 13 grand maximum, mais je n'ai cette information qu'à l'exécution.
    Je dois déterminer à quel carré appartient chaque point d'une liste de coordonnées.
    Rien de compliqué en approche naïve, sauf que la liste à traiter contient plus d'un million de points, et qu'il faut donc soigner les performances de l'algorithme.
    Je pensais éventuellement travailler par dichotomie ou groupes de carrés pour éliminer des cas plus rapidement, mais je ne vois rien d'autre. Y a-t-il quelque chose d'optimal?
    Things working well, no problems. Time to upgrade.

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    3 095
    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 : 3 095
    Points : 7 071
    Points
    7 071
    Par défaut
    Tu as NxN carrés.
    Tu es en dimension 2 ; chaque point (1 Million de points) est connu par (x,y) et les carrés aussi sont donnés par des équations en x,y.

    Je fais une hypothèse : les carrés sont parallèles aux axes. Ca simplifie les calculs, et c'est une hypothèse très plausible. Si ce n'est pas le cas, tout ça va s'adapter, mais ce sera un peu plus compliqué.

    Déjà, peux-tu confirmer si c'est le cas.
    Ensuite, oublie la dichotomie, c'est BEAUCOUP plus simple que ça.
    Enfin pour continuer le 'débat', peux tu proposer des notations, pour ta série de 13x13 carrés. Pour qu'on parle directement dans le langage qui te convient le mieux.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Membre régulier
    Profil pro
    Inscrit en
    mars 2003
    Messages
    121
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mars 2003
    Messages : 121
    Points : 81
    Points
    81
    Par défaut
    Alors, les carrés sont effectivement tous parallèles aux axes.
    Je n'ai pas spécialement de notation idéale en tête.
    Du coup, tu m'as fait un sacré teasing avec ton "BEAUCOUP plus simple".
    Je me demande si ça ne va pas tout simplement passer par une multiplication/division par un facteur représentant la ligne ou la colonne du carré, à comparer avec les coordonnées du point. Mais ce sont des opérations coûteuses...
    Things working well, no problems. Time to upgrade.

  4. #4
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    3 095
    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 : 3 095
    Points : 7 071
    Points
    7 071
    Par défaut
    X0 = l'abscisse du 1er coin du 1er carré.
    Y0 = l'ordonnée du 1er coin du 1er carré.
    L = la largeur (ou la longueur) de chaque carré.

    X,Y les coordonnées du point cherché.

    trunc( (X-X0)/L ) et trunc ( (Y-Y0)/L) vont te donner le n° de ligne et le n° de colonne de ton carré.
    Attention aux +1 à ajouter éventuellement, si les numérotations ne commencent pas à 0 ou des pièges du genre.

    Oui, il y a une division pour chaque calcul. Mais même si une division est un peu plus coûteuse qu'une addition, ça me paraît vraiment le plus efficace.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  5. #5
    Membre régulier
    Profil pro
    Inscrit en
    mars 2003
    Messages
    121
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mars 2003
    Messages : 121
    Points : 81
    Points
    81
    Par défaut
    Ok, c'est compris. Merci!
    Things working well, no problems. Time to upgrade.

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

Discussions similaires

  1. Vérifier l'appartenance d'un point à un triangle
    Par ines ben alaya dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 08/07/2015, 05h57
  2. Appartenance d'un point à un path
    Par hl037 dans le forum Mathématiques
    Réponses: 1
    Dernier message: 27/07/2012, 01h25
  3. appartenance d'un point a une "shape"
    Par Torx26 dans le forum Mathématiques
    Réponses: 2
    Dernier message: 11/04/2012, 09h44
  4. Appartenance d'un point à un losange
    Par Viish dans le forum Mathématiques
    Réponses: 6
    Dernier message: 28/03/2012, 12h56
  5. Appartenance d'un point à une droite
    Par x0rster dans le forum C
    Réponses: 3
    Dernier message: 01/04/2007, 00h33

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