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 :

Optimiser un algo de détection de proximité de véhicule ayant priorité à droite


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre très actif Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    728
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 728
    Par défaut Optimiser un algo de détection de proximité de véhicule ayant priorité à droite
    Bonjour,

    J'essaie de simuler un traffic routier, donc potentiellement un très grand nombre de véhicules, et j'en suis à gérer la priorité à droite.

    Nom : intersection.jpg
Affichages : 282
Taille : 75,1 Ko

    V1 va vers le haut ,et V2 va vers le bas. V2 est donc prioritaire sur V1.

    Notez que pour tout V1 de l'intersection j'ai déjà implémenté un tableau de véhicules V2 (ayant potentiellement la priorité à droite).

    Mon algo de detection de proximité de V2 est le suivant : si l'un des deux points rouge est à l'intérieur du rectangle jaune (rectangle aligné sur le repère cartésien, permet d'exclure des véhicules V2 candidats à très faible coût algorithmique) alors on verifie si ce dernier est dans le rectangle vert (enveloppe convexe de V2), si oui, alors on réduit la vitesse de V1

    Est il possible svp d'optimiser d'avantage cet algorithme ?

    Merci

  2. #2
    Membre Expert

    Homme Profil pro
    Directeur de projet
    Inscrit en
    Mai 2013
    Messages
    1 638
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : Mai 2013
    Messages : 1 638
    Par défaut
    Bonjour,

    N'ayant qu'une vision partielle, il est difficile de juger l'algorithme global.

    Cependant la vérification de l'appartenance du point rouge au rectangle vert peut se faire de différentes manières.

    La première consiste à mesurer les distances aux cotés. En s'y prenant bien, on peut se limiter à deux "distances" au lieu de 4 (distances signés au centre du rectangle vert) mais cela fait quelques multiplications (4). Pour éviter d'avoir d'autres opérations coûteuses, on travaillera sur des segments unitaires (cos, sin) afin d'éviter d'avoir un module à calculer et une division. Comme les segments sont orthogonaux, l'un se réduit de l'autre. On travaillera en séquence pour pouvoir exclure certains cas sans avoir à calculer la deuxième projection (gain assez faible mais non négligeable).

    On pourrait aussi faire tourner le point rouge autour du centre commun des deux rectangles pour se placer dans le repère propre au rectangle vert. Cela simplifierait la comparaison mais la rotation demande également 4 multiplications.

    Salutations

  3. #3
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2008
    Messages
    26 772
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Août 2008
    Messages : 26 772
    Par défaut


    Les jeux similaires ont-ils déjà résolu le problème ? Je ne pense pas que Cities Skylines (1 et 2) ou Transport Fever (1 et 2) le gèrent : tu as des cédez le passage, des priorités de rond-point ou des feux de signalisation (comme en Amérique du Nord), mais pas vraiment de priorité à droite ou à gauche comme on la connaît en Europe. Je me suis toujours dit que c'était parce que c'était difficile à implémenter efficacement...
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  4. #4
    Membre très actif Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    728
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 728
    Par défaut
    Merci encore les amis

  5. #5
    Expert confirmé
    Avatar de Mat.M
    Profil pro
    Développeur informatique
    Inscrit en
    Novembre 2006
    Messages
    8 532
    Détails du profil
    Informations personnelles :
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Novembre 2006
    Messages : 8 532
    Par défaut
    il y a très simple :calculer la distance entre un véhicule A et un véhicule B.
    Ensuite si la distance est inférieure à un certain seuil mettons 10 unités 3d , si le véhicule B a un cap et par conséquent une trajectoire selon cet angle compris entre 0 et 180degrés alors il vient de la droite et il y a risque de collision.

  6. #6
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 491
    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 : 3 491
    Par défaut
    bonjour

    intuitivement j'aurais mis les vehicule dans un cercle circonscrit à la taille du vehicule
    selon la distance ou se trouve les vehicules les uns des autres, leurs vitesses et le cadrans dans lequels le contact se ferait
    cela devrais pouvoir determiner qui aura la priorité

Discussions similaires

  1. Algo optimisation de parcours dans un graphe
    Par egu07 dans le forum Intelligence artificielle
    Réponses: 1
    Dernier message: 11/09/2008, 10h20
  2. Question d'optimisation d'algo
    Par snoopo dans le forum Algorithmes et structures de données
    Réponses: 15
    Dernier message: 15/04/2007, 10h10
  3. algo problème d'optimisation (trajet)
    Par gugumon dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 22/06/2006, 17h35
  4. Optimisation et Recherche opérationnelle : quel algo ?
    Par temar dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 01/04/2006, 16h46
  5. Optimisation algo permutations éléments d'1 ensemble
    Par User dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 23/10/2005, 18h29

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