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 :

Intersections de splines


Sujet :

Algorithmes et structures de données

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

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 717
    Points : 741
    Points
    741
    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 & Livres


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

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

    Informations forums :
    Inscription : Août 2008
    Messages : 26 609
    Points : 188 582
    Points
    188 582
    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 (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 !

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

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 717
    Points : 741
    Points
    741
    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 & Livres


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

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

    Informations forums :
    Inscription : Août 2008
    Messages : 26 609
    Points : 188 582
    Points
    188 582
    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 (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 !

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

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 717
    Points : 741
    Points
    741
    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
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 410
    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 410
    Points : 5 801
    Points
    5 801
    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 éclairé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 717
    Points : 741
    Points
    741
    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 : 511
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
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 410
    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 410
    Points : 5 801
    Points
    5 801
    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 éclairé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 717
    Points : 741
    Points
    741
    Par défaut
    Merci beaucoup anapurna

  10. #10
    Membre expérimenté
    Profil pro
    chercheur
    Inscrit en
    Avril 2004
    Messages
    830
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : Avril 2004
    Messages : 830
    Points : 1 453
    Points
    1 453
    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 éclairé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 717
    Points : 741
    Points
    741
    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 : 484
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

  12. #12
    Membre éclairé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 717
    Points : 741
    Points
    741
    Par défaut
    Bonjour,

    l'itération jusqu'à i = 3 se passe bien, cet algo a l'air pas mal optimisé pour le moment je laisse en l'état. Je peux donc détecter si une spline chevauche une autre et interdire ou non la construction d'une route. A présent je dois gérer la possibilité de créer une route qui rejoins une autre pour obtenir un carrefour.

    Soient A la route existante et B la route en cours de prévisualisation. A et B sont courbes. Si B chevauche A je suis sensé interdire la validation de B sauf que si la souris est suffisemment proche de de la spline de A alors B est validéé et un carrefour est créé.

    Nom : 6.jpg
Affichages : 456
Taille : 259,4 Ko

    Que B chevauche A ou non, si la souris est dans le triangle T englobant la totalité de la spline de A ainsi que l'épaisseur de la route ( triangle T en mémoire mais pas sur l'image), alors il peut y avoir carrefour. Etape suivante de l'algo : trouver le point p sur la spline de A le plus proche de la souris et mesurer la distance d entre cette dernière et p. Si d < tolérance, alors on valide le tracé de B et le carrefour.

    Quel algo peu couteux (car appelé 40 fois par secondes) svp permet de trouver le point d'une spline à distance minimale d'un point quelconque ?

  13. #13
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    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 : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Intersections de splines
    Bonjour,

    Citation Envoyé par guitz Voir le message
    ... Quel algo peu couteux (car appelé 40 fois par secondes) svp permet de trouver le point d'une spline à distance minimale d'un point quelconque ?
    La spline (SA) étant paramétrée par une variable (t) du domaine [0 ; 1], la recherche de son point (A) le plus proche d'un centre (C) relève de la localisation progressive du minimum de la fonction h = AC2 = F(t) = (XA(t) - XC)2 + (YA(t) - YC)2 .

    Partir pour cela de l'intervalle initial I0 = [tmin ; tmax], que l'on partage en (N = 10) sous-domaines, de largeur Delta0 = (tmax - tmin) / N = (1 - 0)/10 = 0.1 ;

    # calculer la suite des (N + 1) termes hk = F(k*Delta0) pour (k) variant de (0) à (N), et repérer la plus faible hm , ainsi que l'indice (m0) et l'argument correspondants (t0 = m0 * Delta0 = m0 / N) ;

    # passer à la nouvelle suite de (2*N + 1) termes hk = F(t0 + k*Delta1) pour (k) variant désormais de (-N) à (+N), et une largeur (N) fois plus faible Delta1 = Delta0 / N ;
    le nouveau domaine exploré est ainsi borné par les valeurs: (tmin = t0 - N*Delta1 = t0 - Delta0 , tmax = t0 + N*Delta1 = t0 + Delta0);
    repérer le nouveau minimum (hm), ainsi que son indice (m1) et son nouvel argument (t1 = t0 + m1 * Delta1 = t0 + m1 / N2) ;

    # reprendre le processus précédent, jusqu'à parvenir à la précision nécessaire Deltaj = Delta0 / N(j) = 1 / 10(j+1) .
    Six ou huit étapes devraient suffire; cela dépend évidemment de la précision attendue.

    On peut aussi, par un procédé analogue, repérer le zéro de l'expression des différences successives:
    gik = F(ti-1 + (k+0.5)*Deltai) - F(ti-1 + (k-0.5)*Deltai) .

    Je crains cependant que tout cela ne devienne très long, pour de très nombreuses recherches.
    S'il faut comparer un grand nombre de splines à une nouvelle pour s'assurer de leur non-superposition, il paraît plus rentable de travailler sur la matrice de pixels correspondant au corps de l'image (la grille 2D ?), comme cela a déjà été dit.


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

  14. #14
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    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 : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Intersections de splines
    Si ton logiciel te permet de tracer chaque courbe sous la forme d'un ruban de largeur finie, il y a un moyen rapide de tester l'empiètement éventuel des (Ns) splines présentes avec une nouvelle.
    # Sur le fond d'image initialement noir (couleur 000), tracer les (Ns) splines connues avec la même couleur (par ex. rouge m00), ce qui revient à imposer à chaque pixel du ruban la valeur (255, 0, 0) indépendamment de sa valeur précédente;
    # Tracer la nouvelle spline en attribuant à tout pixel de son ruban une valeur dépendant de sa valeur actuelle:
    noir (000) ---> bleu (00m) ou rouge (m00) ---> vert (0m0) .

    Ainsi toute zone de chevauchement se signalera par la plus brillante coloration (vert).
    Le test visuel est suffisamment sensible pour dispenser de tout algorithme de vérification.

    Cela implique un contrôle local de la couleur qui ne va peut-être pas de soi. Peut-on envisager par exemple un tracé en semi-transparence, qui préserverait la mémoire de la couleur antérieure ? Cela permettrait de retrouver les zones de chevauchement dans l'image finale.

    PS: Nebulix proposait un moyen apparenté (#10)


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

  15. #15
    Membre éclairé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 717
    Points : 741
    Points
    741
    Par défaut
    Citation Envoyé par wiwaxia Voir le message
    Je crains cependant que tout cela ne devienne très long, pour de très nombreuses recherches.
    S'il faut comparer un grand nombre de splines à une nouvelle pour s'assurer de leur non-superposition, il paraît plus rentable de travailler sur la matrice de pixels correspondant au corps de l'image (la grille 2D ?), comme cela a déjà été dit.
    Merci wiwaxia pour ta réponse.

    Pas de besoin d'effectuer ce calcul pour toutes les splines. En effet toutes les splines déjà validées ont un triangle englobant Ti (en mémoire, pas sur l'image) qui englobe la spline Ai et aussi l'épaisseur de route.

    1. Si la souris est dans l'un des Ti ET que un chevauchement de la spline B a été détecté sur Aj (avec j != i) on ne valide pas B
    2. Si la la souris est dans l'un des Ti ET (que un chevauchement de la spline B a été détecté sur Ai OU aucun chevauchement n'a été detecté avec tous les Ai (pour 1 allant de 1 à nombre de spline validées)), alors on utilise éventuellement ton algo pour voir si la souris est suffisamment proche de la spline Ai pour valider ou non un carrefour

    Donc ton algo serait appliqué que sur une seule spline.

    Je vais tester ton algo

    Edit : malheureusement ce n'est pas possible ta solution avec la superposition de couleurs de pixels sur UE4

  16. #16
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    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 : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Intersections de splines
    Citation Envoyé par guitz Voir le message
    ... Pas de besoin d'effectuer ce calcul pour toutes les splines ...
    Donc ton algo serait appliqué que sur une seule spline ...
    Bonne nouvelle, donc: le procédé est envisageable.

    Le nombre d'étapes dépend de la précision du type des flottants en cause.
    Comme il s'agit sans doute de splines d'ordre 3 (ou 4, tout au plus), les sinuosités de la courbe sont relativement douces, comme les variations locales des grandeurs qui leur sont attachées (coordonnées, courbures, distances).
    On ne trouvera donc pas de fantaisie brutale au mauvais endroit (du genre de celle représentée ci-dessous):

    Nom : Spline.png
Affichages : 492
Taille : 6,5 Ko

    En conséquence, il ne sera pas nécessaire de poursuivre au-delà de la seconde étape (jfinal = 1) si l'on trouve D2min >~ 1.5 * Lroute .

    Les instructions données n'excluent pas une recherche de la racine hors de l'intervalle [0 ; 1]; cela ne présente pas d'inconvénient calculatoire dans la mesure où interviennent des polynômes, donc des fonctions dépourvues de singularité aux frontières du domaine; le débordement est de plus limité: (0.888...) < t < (1.111...) .
    On peut insérer des critères d'arrêt du type:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    IF (t<sub>max</sub> < 0) THEN t<sub>lim</sub>:= 0
    IF (t<sub>min</sub> > 1) THEN t<sub>lim</sub>:= 1     // instructions à traduire et compléter
    déplacer l'une des bornes du nouveau domaine ou terminer le procédé initial par les corrections:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    IF (t<sub>lim</sub> < 0) THEN t<sub>lim</sub>:= 0
    IF (t<sub>lim</sub> > 1) THEN t<sub>lim</sub>:= 1


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

  17. #17
    Membre éclairé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 717
    Points : 741
    Points
    741
    Par défaut
    wiwaxia, je me suis trompé.

    Il se peut que la souris soit dans plusieurs triangles englobant (qui incluent l'épaisseur de route). Donc l'algo de minimisation de distance entre souris et spline va concerner plusieurs spline. Ta technique itérative qui fait une partition de [0, 1] serait alors peut être trop couteuse ( comme tu l'as redouté). Je garde ta technique sous le coude mais je vais tenter d'abord cet essai.

    Autre chose, ma spline est quadratique (d'ordre 2), car elle a 3 points de contrôle (les 2 points + la tangente). Je sais pas si ça peut t'aider

    Nom : 7.gif
Affichages : 467
Taille : 27,2 Ko

    Soient P le point de la souris, S(tmin) le point sur la spline, tel que S(tmin) = min({ pour tous t appartenant à [0,1], norme(P-S(t)) tq (P - S(t)).T(t) = 0 } . T(t) étant bien entendu la tangente.

    J'aimerais trouver l'algo qui va trouver dans un nombre minimale d'itérations, 2 t successifs, où le produit scalaire change de signe, afin de trouver un sous ensemble de [0,1] le plus plus petit possible, qui contient tmin.

    Intuitivement j'aurais envie de tester :

    t=0
    t=0.5
    si pas changement de signe alors tmin est dans [0.5, 1]
    t=0.75
    t=1
    si pas changement de signe alors tmin est dans [0.5, 0.75]

    etc...

    Pensez vous qu'on peut optimiser le balayage ?

  18. #18
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    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 : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Intersections de splines
    J'avais bien songé à la recherche du zéro de la dérivée, mais la lourdeur des calculs (relatifs à des splines supposées d'ordre 3, que suggéraient les dessins) m'en avaient dissuadé.

    Tu as trouvé par intuition une solution géométrique, qui correspond effectivement au minimum du carré de la distance; on a en effet:

    D2 = PS2 = PSPS (produit scalaire du vecteur par lui-même), d'où par dérivation:

    (d/dt)D2 = (d/dt)(PSPS) = 2*(PS│(d/dt)PS) = 2*(PSST) , en notant (ST) le vecteur tangent en (S) à la spline orientée par le paramètre (t).

    Le minimum de la distance est bien caractérisé par l'orthogonalité des deux vecteurs, (d/dt)D2 = 0 impliquant PSST = 0 .

    Nom : Spline_2_Tangentes_01.png
Affichages : 467
Taille : 55,6 Ko

    Passons au cas particulier d'une courbe du second ordre: en notant (K0, K1, K2) les points de contrôle, il vient (citation de mémoire, tu corrigeras les éventuelles incorrections):

    OS = (1 - t)2.0K0 + 2*t*(1 - t).0K1 + t2.0K2 , d'où:

    (d/dt)OS = -2*(1 - t).0K0 + 2*(1 - 2*t).0K1 + 2*t.0K2 = ST , ainsi que l'expresion du produit scalaire:
    F(t) = PSST = -2*(1 - t)*(PS0K0) + 2*(1 - 2*t)*(PS0K1) + 2*t*(PS0K2) .

    Il suffit donc de repérer le plus petit intervalle aux extrémités duquel la fonction change de signe, et vérifiant par conséquent: F(tj)*F(tj+1) < 0 .

    Ce que tu as suggéré
    ... Intuitivement j'aurais envie de tester :
    t=0
    t=0.5
    si pas changement de signe alors tmin est dans [0.5, 1]
    t=0.75
    t=1
    si pas changement de signe alors tmin est dans [0.5, 0.75]

    etc ...
    correspond à la recherche classique d'une racine par dichotomie.

    Une division par 10 du domaine initial [0 ; 1], systématiquement reprise pour les nouveaux intervalles jusqu'à la précision attendue (DeltaT = 10-8 ?) serait peut-être plus rapide.

    PS: les signes mentionnés sur la figure sont à inverser à cause du choix de mes vecteurs, mais c'est tout à fait secondaire.


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

  19. #19
    Membre éclairé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 717
    Points : 741
    Points
    741
    Par défaut
    Merci wiwaxia, et toutes mes escuses car cette fonction est en fait native dans UE4. Je n'ai pas pensé à regarder car je doutais qu'elle y soit.

    Mais notre algo servira quand même à d'autres

  20. #20
    Membre chevronné

    Profil pro
    Inscrit en
    Juin 2002
    Messages
    1 374
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2002
    Messages : 1 374
    Points : 1 759
    Points
    1 759
    Par défaut
    Salut !

    Mon intervention va paraître de trop ici, mais as-tu pensé à développer une interface pour le design du décor (réseau routier, bâtiments etc...).
    Auquel cas, il suffit de travailler en fil de fer, vue de dessus sans jamais être ennuyé par les procédures graphiques qui sont toujours très lourdes.
    Cela permet aussi à l'aide de quelques fonctionnalités très simples de repositionner les objets et donc de remodeler à souhait ce qui peut et doit l'être.

    La détection des intersections relève plus de l'urbanisation par la machine (au quel cas c'est indispensable) et moins pour un urbaniste humain.

    Pour info, j'utilise la fonction sinusoïdale pour tracer mes courbes.
    Il suffit pour cela d'associer au segment AB un handle (comme on le ferait pour une courbe de Bezier) pour en fixer l'amplitude, le signe (localement convexe ou concave) et la symétrie (courbe d'apparence exotique)!
    Donc tout ça se fait facilement à vue !

    On passe toujours du temps à développer mais on peut en passer beaucoup plus à en utiliser le résultat !
    Donc autant ajouter quelque chose qui va simplifier l'usage (pour toi comme pour tout autre utilisateur)!

    Bonne urbanisation !

Discussions similaires

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

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