Calculer les coordonnées d'intersection courbe et droite

[math17]

Bonjour !

J'ai besoin de calculerun point d'intersection entre une courbe bézier cubique et un segment.
Mais je n'arrive pas à trouvé la solution...celà fait longtemps que j'ai quitté l'école ce qui fait que j'ai du mal a me replonger dans les maths

Voici un shéma :



Le but c'est donc de trouver la bonne formule pour calculer I, sachang qu'on connait tous les autres points D1, D2, P0, P1, P2 et P3.

Merci si vous pouvez m'éclairer sur la façon de procéder !

[anthony_unac]

Salut, connaissant D2 et D1, vous pouvez déjà calculer l'équation de la droite

[GaBuZoMeu]

Tu as une paramétrisation de ta courbe de Bézier (paramétrisation de degré 3 en ). Reste à exprimer que le point est aligné avec et , ce qui peut se faire par l'annulation du déterminant

Ça fait une équation de degré 3 en . C'est la vie !
Dans les solutions de cette équation, il faut que tu retiennes celles dans , et que tu vérifies que le point obtenu est bien entre et .

[math17]

GaBuZoMeu

Rien que dans la première ligne je suis out

Mais ça a l'air bien comme ça !

Si j'ai bien compris, "t" c'est en fait le paramètre qui doit être utilisé pour déterminer comment calculer le point d'intersection...
Mais alors comment faire ?
Il faut tester plusieurs paramètres ?

[LB2]

Tu développes le déterminant qui est un polynôme de degré 3 en t (donc les coefficients dépendent des coordonnées de tes points), et tu résous ce polynôme = 0 (avec un calculateur), en conservant les solutions dans [0,1] comme l'a indiqué GBZM.
J'imagine que tu ne sais pas développer ce déterminant : tu peux utiliser la méthode de Sarrus ou développer par rapport à une ligne ou colonne : c'est une somme de 6 termes au total.

Les coordonnées de M(t) sont les coordonnées d'un point quelconque de ta courbe de Bézier passant par P0,P1,P2,P3 : c'est ce qu'on appelle l'équation paramétrique de ta courbe (paramétrée par t, donc). C'est également un polynôme de degré 3 en t. Si tu ne disposes pas de ce polynôme, il faut commencer par le calculer explicitement.

[GaBuZoMeu]

Commençons par le début. Ne connais-tu pas la paramétrisation

?

Tu peux difficilement travailler avec des courbes de Bézier sans connaître cette paramétrisation. Elle figure dans le b-a-ba donné par la page wikipedia.

[math17]

Merci pour vos réponses.


En fait je ne connais pas en détail la paramétrisation mais étant donné que je fais du code j'ai compris instinctivement comment ça fonctionne.

Dans mon cas il s'agit de déplacer un élément le long d'une courbe.
J'ai donc appliqué cette formule en considérant t par rapport a la longueur de la courbe que je multiplie par une distance et un temps pour le faire avancer.
En l'occurance j'ai plusieurs courbes donc C représente la courbe dans laquelle se trouve l'élément.

Concrètement ça donne, en java :

Code: Tout sélectionner

                var T = ((positionObj - courbesParcouru) / courbes[C].longueur);

                obj[i].x = Math.pow((1 - T), 3) * courbes[C].P0.x
                    + 3 * T * Math.pow((1 - T), 2) * courbes[C].P1.x
                    + 3 * Math.pow(T, 2) * (1 - T) * courbes[C].P2.x
                    + Math.pow(T, 3) * courbes[C].P3.x;

                obj[i].y = Math.pow((1 - T), 3) * courbes[C].P0.y
                    + 3 * T * Math.pow((1 - T), 2) * courbes[C].P1.y
                    + 3 * Math.pow(T, 2) * (1 - T) * courbes[C].P2.y
                    + Math.pow(T, 3) * courbes[C].P3.y;


Et ça marche.
Sauf que mon but maintenant est de calculer le cas ou un autre objet vient de cette droite D et croise une courbe. Il faut qu'il s'arrête précisément à l'interséction...

Et si j'ai bien compris ce que vous dites, c'est qu'il faudra calculer ce point en utilisant plusieurs paramètre jusqu'à trouver le plus approchant ?

Dsl j'ai vraiment peu de notions de maths donc c'est pas trés clair tout ça.
Idéalement j'aimerais pouvoir trouver une formule comme celle de f.legrand qui me donne d'un coup le résultat de l'intersection...est-ce seulement possible ?

[GaBuZoMeu]

Ce que je dis, c'est qu'on trouve les paramètres correspondant à l'intersection de la courbe de Bézier avec une droite en résolvant une équation du troisième degré en . Cette équation est facile à écrire à partir des données (les coordonnées des points ). Pourquoi le degré 3 ? Parce que tu utilises des courbes de Bézier cubiques. Résoudre une équation de degré 3 est l'enfance de l'art pour n'importe quel logiciel scientifique. Mais je ne sais pas avec quoi tu travailles.

Je ne comprends pas ton histoire "en considérant t par rapport a la longueur de la courbe que je multiplie par une distance et un temps pour le faire avancer" et ton bout de code

Code: Tout sélectionner

var T = ((positionObj - courbesParcouru) / courbes[C].longueur);

Le paramètre d'une courbe de Bézier cubique n'a rien à voir avec la longueur parcourue sur cette courbe.

[GaBuZoMeu]

Un petit code dans le logiciel scientifique que j'utilise (SageMath) :

Code: Tout sélectionner

t=var('t')
B=[binomial(3,i)*t^i*(1-t)^(3-i) for i in range(4)]

def intersection(path,segment):
    xM=sum(B[i]*path[i][0] for i in range(4))
    yM=sum(B[i]*path[i][1] for i in range(4))
    xOr=segment[0][0] ; yOr=segment[0][1]
    xFi=segment[1][0] ; yFi=segment[1][1]
    Eq=xM*(yOr-yFi)-yM*(xOr-xFi)+xOr*yFi-yOr*xFi
    sols=[sol[0] for sol in Eq.roots(t,ring=RR)]
    sols=filter(lambda s : 0<=s and s<=1, sols)
    inter=[(xM.subs(t=s),yM.subs(t=s)) for s in sols]
    entre=lambda (x,y) : (x-xOr)*(x-xFi)<0 or (y-yOr)*(y-yFi)<0
    return filter(entre,inter)
   

Voyons ce que ça donne sur un exemple :

Code: Tout sélectionner

path=[(0,-1),(0,1),(1,1),(2,0)]
segment=[(1/2,0),(1,1)]
I=intersection(path,segment)
I

Réponse :

Code: Tout sélectionner

[(0.828427124746190, 0.656854249492380)]

Vérifions avec un dessin :

Code: Tout sélectionner

b=bezier_path([path],color='red')
s=line(segment)
i=point(I,size=30,color='black')
show(b+s+i)

Un exemple un peu plus sioux :

Code: Tout sélectionner

path=[(0,-1),(1,5),(1,-1),(-1,0)]
segment=[(1/2,1),(-1/2,-1)]
I=intersection(path,segment)
I

et la réponse

Code: Tout sélectionner

[(0.298026915852613, 0.596053831705225),
 (0.120851216242631, 0.241702432485262)]

avec le dessin pour vérifier :

[math17]

cool !
C'est exactement ça dont j'ai besoin !
Malheureusement j'ai pas accès à ce genre de fonctions avec javascript, sauf erreur.

Idéalement j'aimerai pouvoir retranscrire cette équation en javascript, ou en math.
En somme il faut faire appel à des fonctions de calculatrice spéciales ?

[GaBuZoMeu]

Arriver à l'équation à résoudre ne poe pas de problème, je pense. J'ai utilisé dans mon code quelques raccourcis, par paresse, mais rien qui soit vraiment nécessaire.
Le problème après est de résoudre l'équation du troisième degré.
Il y a des bibliothèques pour javascript qui font ça apparemment, voir par exemple ici.
On pourrait aussi faire quelque chose ad hoc en utilisant que le polynôme dont on cherche les racines réelles est directement donné dans la base de Bernstein.
Mais moi, je m'arrête là, ce n'est plus mon job. Bonne chance !

[math17]

Ok, merci GaBuZoMeu !
Je vais bien relire et peut être par miracle je vais y comprendre quelque chose .
Sinon au pire je bidouillerai une fonction pas trés orthodoxe mais qui calculera un point approximatif.

En tout cas merci ça va certainement m'aider .

[GaBuZoMeu]

Je peux te donner des éclaircissements sur le code que j'ai écrit. Mais je ne peux absolument pas t'aider pour javascript (personne ne fait de calcul scientifique avec).