1. #1
    Membre averti Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    juillet 2006
    Messages
    568
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : juillet 2006
    Messages : 568
    Points : 408
    Points
    408

    Par défaut Intersections de splines

    Bonjour,

    Dans le cadre du développement de mon city builder je suis confronté à la problématique de ne pas construire de route au dessus de routes existantes (sans parler d'intersection).

    Soient A l'union de splines existantes (les routes qui ont déja été créées) et B la spline en cours de prévisualisation (un premier clic définit le premier point, un second clic le point tangente et des mouvement de souris déplacent le dernier point permettant de visualiser la spline avant validation, cliquer une derniere fois valide le dernier point et donc la spline)

    subdiviser chaque spline de A et la spline de B en segments n'étaient pas couteux algorithmiquement grâce à l'algo de de Casteljau (à condition d'avoir un nombre d'itérations raisonnables), mais là où ça devient très couteux cest quand il s'agit de vérifier si B peut être validé, donc si B n'est pas en intersection avec A. Puisque :

    40 fois par secondes( B est en prévisualisation, donc chaque mouvement de souris, modifient l'apparence de la spline), il ya 3 boucles emboitées :

    Pour tous segments s2 de B -> pour toutes splines de A -> pour tous segments s1 de A (sachant qu'une spline peut contenir une trentaine de segments, donc imaginez si A contient 500 splines...), si s1 est en intersection avec s2 on sort de la fonction en renvoyant false, et B ne peut être validé.

    Je me penche alors vers la solution qui consiste à faire une intersection de chaque spline validée avec une grille 2D (par exemple 5000 x 5000).
    toutes les splines de A ont été snappée précédemment avec un certain pas, sur la grille. Au moment de prévisualiser B je récupère les indices i et j de chaque points xi ([xi xi+1] mesure un certain pas) de la spline qui correspondent à un snap sur la grille, et si Grid[i][j]->IsOccupied = true, je ne valide pas B.

    Cet algo semble bien moins couteux que le précédent, mais y a-t'il mieux svp ?

  2. #2
    Responsable Qt


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherches
    Inscrit en
    août 2008
    Messages
    22 265
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Ingénieur de recherches
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 22 265
    Points : 121 429
    Points
    121 429

    Par défaut



    J'aurais en tête une approche plus analytique : déterminer la forme polynomiale de chacune de ces courbes, puis chercher une solution au système d'équations non linéaire (méthode de Newton, par exemple — les calculs de jacobiennes devraient être assez faciles).

    Ensuite, tu peux probablement implémenter un filtre sur les segments que tu considères : s'il n'y a aucune chance qu'il y ait une intersection, alors inutile de perdre son temps en des calculs lourds. Par exemple, tu pourrais déterminer un triangle dans lequel ta courbe est contenue (parallèle à la tangente à la courbe au niveau des deux extrémités du segment), pour chaque segment, puis vérifier si les triangles des routes existantes et de la nouvelle route ont une intersection
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions) ? Contactez-moi par MP.

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

    Pas de question d'ordre technique par MP !

  3. #3
    Membre averti Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    juillet 2006
    Messages
    568
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : juillet 2006
    Messages : 568
    Points : 408
    Points
    408

    Par défaut

    Merci Dourouc05.

    Bien vu pour les triangles englobants.
    Je vais comparer nos 2 méthodes et garder la moins couteuse

    Un bon informaticien est un flemmard et un radin

  4. #4
    Responsable Qt


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherches
    Inscrit en
    août 2008
    Messages
    22 265
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Ingénieur de recherches
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 22 265
    Points : 121 429
    Points
    121 429

    Par défaut

    Petite trouvaille : si tu passes à des "combinaisons linéaires de cerces positives à support compact minimal" (B-spline), tu pourrais utiliser http://www.sciencedirect.com/science...783968590024X/ (n'oublie pas SciHub ).

    http://cagd.cs.byu.edu/~557/text/ch7.pdf pourrait aussi être utile.
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions) ? Contactez-moi par MP.

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

    Pas de question d'ordre technique par MP !

  5. #5
    Membre averti Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    juillet 2006
    Messages
    568
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : juillet 2006
    Messages : 568
    Points : 408
    Points
    408

    Par défaut

    Ton second pdf a l'air très utile

    Toutefois à vue de nez ça m'a l'air quand même plus couteux que la méthode de la grille, mais peut être que je me trompe. Je vais faire tourner ces 2 algos et les comparer

  6. #6
    Membre expert
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 447
    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 447
    Points : 3 844
    Points
    3 844

    Par défaut

    salut

    l'utilité de tout recalculer me parait un peu folle
    tu ne doit recalculer que la partie modifiée sous le curseur le reste ne bouge pas
    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 averti Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    juillet 2006
    Messages
    568
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : juillet 2006
    Messages : 568
    Points : 408
    Points
    408

    Par défaut

    Salut,

    Dans mon algo foireux d'intersection de segments de splines, je ne calcule pas en temps réel à chaque fois les segments de A, ils sont calculés en amont à chaque fois qu'une nouvelle spline est validée. Mais même ainsi mon algo rame la mort.

    Finalement je vais laisser tomber la grille provisoirement et me pencher sur la solution plus élégante (mais au combien plus compliquée) de dourouc05. Mais j'ai amélioré l'idée en ne calculant le chevauchement avec les splines du plus proche au moins proche de B. Donc à chaque fois que le premier point de B est choisi (avant la prévisualisation puisque la tangente n'est pas encore définie) je fais un tri du tableau qui contient toutes les splines de A de la plus proche à la moins proche. Vu que la proba qu'une spline chevauche une autre spline est plus importante avec une spline voisine, ça évite bien des calculs inutiles.
    Si cet algo me pose trop de pbs et/ou est impossible à assez bien optimiser je rebasculerai sur la matrice de booléens.

    Edit :

    Nom : 4.jpg
Affichages : 38
Taille : 451,8 Ko

    Chaque spline de A (routes déja présentes ) stocke son propre baricentre (segment noir vertical). Je vais calculer le chevauchement ou non de B (route en cours de prévisualisation en vert) avec la spline de A dont le baricentre est le plus proche au plus lointain

  8. #8
    Membre expert
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 447
    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 447
    Points : 3 844
    Points
    3 844

    Par défaut

    salut

    ton problème fait penser furieusement aux théorie de collision dans les jeux video
    regarde ce lien il peut t’intéresser
    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

  9. #9
    Membre averti Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    juillet 2006
    Messages
    568
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : juillet 2006
    Messages : 568
    Points : 408
    Points
    408

    Par défaut

    Merci beaucoup anapurna

  10. #10
    Membre éprouvé
    Profil pro
    Inscrit en
    avril 2004
    Messages
    653
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations forums :
    Inscription : avril 2004
    Messages : 653
    Points : 938
    Points
    938

    Par défaut

    Pour afficher la nouvelle spline, il faut affecter une couleur à un pixel. Il n'est pas beaucoup plus couteux de lire avant la couleur du pixel pour voir s'il appartient à une route ou au fond.
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  11. #11
    Membre averti Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    juillet 2006
    Messages
    568
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : juillet 2006
    Messages : 568
    Points : 408
    Points
    408

    Par défaut

    Merci pour ton conseil Nebulix, mais jignore si c'est faisable sur Unreal Engine. Si mon algo montre ses limites je me pencherai sur ta solution.

    Mais pour le moment avec une seule itération de subdivision de triangles box (algo de Casteljau) c'est parfaitement fluide (le fait de calculer un éventuel chevauchement avec la spline de la plus proche à la plus lointaine aidant puisque ça évite bien souvent des calculs inutiles.

    Nom : 5.jpg
Affichages : 22
Taille : 347,3 Ko

    Les 2 triangles dans le grands sont une subdivision d'itération i = 1.
    L'algo est pas parfait puisque dans la spline de prévisualisation (en vert) le point commun des 2 triangles est décalé de la spline. Mais bon pour le moment j'ai que l'algo de Casteljau à disposition.

    Je vais voir ce que ça donne à itérer jusqu'à i = 3

Discussions similaires

  1. Intersection Droite Spline
    Par Hardgroove dans le forum MATLAB
    Réponses: 6
    Dernier message: 17/12/2013, 17h15
  2. EXCEPT et INTERSECT sous MS SQLServer ?
    Par christie dans le forum MS SQL-Server
    Réponses: 2
    Dernier message: 27/05/2004, 16h47
  3. [prg jeux ]Définir l'intersection de deux rectangles
    Par mat.M dans le forum Général Algorithmique
    Réponses: 6
    Dernier message: 30/07/2003, 18h11
  4. XPath: intersection de chemins
    Par aldo047 dans le forum XSL/XSLT/XPATH
    Réponses: 4
    Dernier message: 13/03/2003, 10h30
  5. [TP]Splines
    Par Eric Sigoillot dans le forum Turbo Pascal
    Réponses: 3
    Dernier message: 30/06/2002, 19h08

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