Intersection 2 coubes de bézier quadratiques

[Guitou80]

Bonjour,

Je cherche développer un algorithme qui permet de detecter si 2 courbes de bézier quadratiques ont un point d'intersection, et renvoie ce dernier.

Une courbe de Bézier quadratique est la courbe B(t) définie par les points de contrôle P0, P1 et P2.

B(t) = (1-t)²P0 + 2t(1-t)P1 + t²P2, t appartenant à [0, 1].

Quel vous semble là façon la plus optimisée d'opérer svp ?

[Ben314]

Salut,
Au niveau calcul exact, ça semble mal barré : si tu prend P0 et P2 proche l'un de l'autre et P1 très éloigné, ta courbe fait quasiment un "aller retours". Et si tu fait la même chose avec l'autre courbe mais en tournant de 90°, tu constate qu'il peut y avoir jusqu'à 4 points d'intersections entre tes deux courbes.
Donc quasi surement une équation polynomiale de degré 4 à résoudre et résoudre ce type de truc de façon exacte, c'est bien la m... (la seule formule "théorique", c'est celle de Ferrari qui n'a aucun intérêt numériquemet parlant)
Donc faudra forcément faire autrement (dichotomie ou méthode des tagentes de Newton ou... autre chose...) (*)

Concernant l'équation en elle même, c'est on ne peut plus simple : si tu écrit que les abscisses et les ordonnées de tes deux points doivent être les mêmes (et que tu développe les polynômes du second degré en t et en s), ça te fait un truc du style et où a,b,...f,A,B,...,F sont des constantes et où s et t sont les inconnues.
Si tu fait fois la première équation moins la seconde, ça élimine les et ça permet d'exprimer sous la forme (sauf cas exceptionnel où le coefficient en est lui aussi nul) et si tu réinjecte ça dans une des deux équation de départ, ça te fait bien comme prévu une équation du 4em degré et (dont tu cherche les solutions uniquement entre 0 et 1 et il faudra vérifier que est lui aussi entre 0 et 1)

(*) Un truc pas con du tout à utiliser dans ce type de contexte, c'est le Théorème de Sturm qui permet très rapidement (et très facilement au niveau informatique) de savoir combien de racines réelle possède ton polynôme entre 0 et 1. Ensuite, une fois ce nombre connu, il n'y à "plus qu'à" les localiser.

[Guitou80]

Bonjour Ben314,

Merci pour ta réponse, j'ai bien lu et relu ton explication. J'arrive à développer et à obtenir le système suivant (ce qui est très facile) :

At² + Bt + C
Ds² + Es + F

Mais je n'arrive pas à résoudre At² + Bt + C = Ds² + Es + F

Peux etre as tu oublié de te relire et a fait une erreur ?

[Ben314]

At² + Bt + C
Ds² + Es + F

Euhhhhh, si il y en a un qui a "oublié de se relire", à mon avis.... c'est plutôt toi, vu que je comprend pas trop en quoi ce truc est un "système" (y'a aucun symbole d'égalité...)

Là où éventuellement tu n'a pas compris ce que j'écrivais (j'aurais du préciser), c'est que dans ma prose, a,b,...,f,A,B,...F sont des constantes réelles (et pas des vecteurs). Mais c'est quand même plus que sous entendu par la phrase précédente "si tu écrit que les abscisses et les ordonnées de tes deux points doivent être les mêmes..."

[Ben314]

Un exemple :
Première courbe : Points de contrôle (1;2) , (4;3) , (5,6).
Équation paramétrique :
Deuxième courbe : Points de contrôle (2;3) , (-1;4) , (5,-2).
Équation paramétrique :

Le système à résoudre est
Si on prend 7 fois la première équation plus 9 fois la seconde, ça donne
c'est à dire et il faut donc résoudre l'équation (de degré 4) :

Soit encore
Où on cherche les solutions telles que et

[Guitou80]

Merci beaucoup Ben d'avoir passé le temps pour donner l'exemple qui me permet cette fois ci de comprendre.

C'est vraiment sympa, je vais essayer d'implémenter ça en c++

Bonne journée