Forums Développement Multimédia

Aller au contenu

Cacluler l'intersection de deux courbe de Bezier( quadratique)

CODE Actionscript

5 réponses à ce sujet

#1 Flaxe

  • Guests

Posté 11 February 2010 - 19:21 PM

Bonjour a tous,

Je cherche le moyen de calculer l'intersection entre deux courbes de Bézier quadratique en ActionScript.

Auriez-vous des piste, lien, sources ?

merci

Modifié par Flaxe, 11 February 2010 - 19:21 PM.


#2 tlecoz

  • Honoris
  • PipPipPipPipPipPipPipPip
  • 3486 messages

Posté 12 February 2010 - 00:58 AM

Hello !

La solution la plus simple (et l'unique que je connaisse d'ailleur) passe par l'approximation.
Utilise les barycentre pour décomposer chaque courbe en une suite de segments (genre 100).
Ensuite il suffit de boucler sur tout les segments d'une courbe et de vérifier l'intersection avec les segments de l'autre courbes.

Bon courage !

#3 Flaxe

  • Guests

Posté 12 February 2010 - 22:28 PM

Yop

Finalement c'est tout bête ^^

Je sais qu'une courbe quadratique de Bézier est de la forme :
Image IPB
Où les Pi sont les points de contrôles.


Si je veux l'intersection deux deux courbe, je dit : B1( t) = B2( t), où chaque Bi( t) représente une courbe de Bézier t € [0, 1]
D'où un polynôme du second degré.
B( t) = a.t² + b.t + c

Il suffit de calculer les racine évidente de B( t) Comme au colège :texas:

Enjoy it ;-)

#4 Flaxe

  • Guests

Posté 13 February 2010 - 00:12 AM

Yup,

j'en arrive a calculer l'intersection de deux courbe de Bézier cubic, soit :

Image IPB

la j'fait moins mon malin :mrgreen: finalement, c'est plus si bête que ca^^

Pour résoudre une équation du troisième ou du quatrième degré, on peut tenter...

A ce niveau je pense que la méthode de tlecoz serrai plus rapide


Voila, Hop, c'est archivé.

#5 tlecoz

  • Honoris
  • PipPipPipPipPipPipPipPip
  • 3486 messages

Posté 13 February 2010 - 14:52 PM

Maintenant que j'y pense, il existe une autre méthode ultra simple :smile:


1) créé un Sprite
2) dessine ta premiere courbe avec une epaisseur de 1-2 px, en noir.
3) dessine ta deuxieme courbe avec une epaisseur de 1-2 px, en blanc, avec un alpha de 0.5.
4)Draw ton sprite dans un bitmapData disposant de transparence, ayant en couleur par defaut 0;
5) fais un getColorBoundRect (ou un truc du genre) sur ton bitmapdata en cherchant les pixels gris.


Si le rect que l'on te sors fait 1px de coté, il n'y a eu qu'un seul point de collision correspondant au coordonnée du rectangle.

si le rect est plus grand, c'est qu'il contient plusieur pixel gris, donc plusieurs points de collisions.
Je te laisse te débrouiller pour les retrouver ;-)

Bon courage !

#6 exodus93

    Ceinture Blanche

  • Members
  • Pip
  • 1 messages

Posté 16 June 2017 - 13:26 PM

Bonjour tout le monde, si je peux me permettre on peut aussi faire une double boucle pour chercher les points les plus proches.
Et attention il peut y avoir plusieurs points d'intersection soit-dit en passant !
Admettons 2 courbes de Bezier C1 et C2.

On utilise une petite fonction paramétrique pour calculer x et y en fonction de t compris entre 0 et 1 pôur chaque courbe :


Procedure CBPCalculXY(x1#, y1#, x2#, y2#, x3#, y3#, x4#, y4#, t#, ByRef x#, ByRef y#)
  x = x1 * (1 - t) ^ 3 + 3 * x2 * t * (1 - t) ^ 2  + 3 * x3 * t ^ 2 * (1 - t)  + x4 * t ^ 3
  y = y1 * (1 - t) ^ 3 + 3 * y2 * t * (1 - t) ^ 2  + 3 * y3 * t ^ 2 * (1 - t)  + y4 * t ^ 3
EndProc
 

Et on fait une première boucle avec 13 points pour la première courbe C1 dans la quelle on insère une seconde boucle pour C2 avec 13 subdivisions aussi.

Je choisis 13 parce-que ça correspont aux nombre de subdivisions nécéssaires pour que les courbures soient entièrement parcourures
P1 i2 i3 i4 P2 i6 i7 i8 P3 i10 i11 i12 P4
Ca donne un truc du genre ( à optimiser ensuite bien sûr...) :



pt=1/13
For i1=1 to 13
 t1=Borne1Start+(i1-1)*pt
 .... calcul de px1 et py1
  For i2=1 to 13
    t2=Borne2Start+(i2-1)*pt  
     .. calcul de px2 et py2
    ... prendre la distance entre les points et garder en mémoire la plus petite et les t1 et t2 associés
    ... on peut le mémoriser dans hmin, t1best et t2best
  Next i2
Next i1
 

On recommence en bornant t1 entre t1best - 1/13 et t1best + 1/13
Idem pour T2 avec t2best.
Et on garde hmin en mémoire et on divise pt par 6 (moitié de 13) pour parcourrir toute la nouvelle subdicision.

On fait ça 40 fois, au delà desquel il n'y a plus de chiffre significatifs pour des variables de type double.
Donc en gros il faut insérér tout ça dans une petite bouboucle à sa mémère.
Le résultat final sera avec t = t1best dans la courbe C1 :

x = x1 * (1 - t) ^ 3 + 3 * x2 * t * (1 - t) ^ 2 + 3 * x3 * t ^ 2 * (1 - t) + x4 * t ^ 3
y = y1 * (1 - t) ^ 3 + 3 * y2 * t * (1 - t) ^ 2 + 3 * y3 * t ^ 2 * (1 - t) + y4 * t ^ 3

et il y a intersection si hmin = 0 (ou très proche de zéro)

Voilà.



1 utilisateur(s) li(sen)t ce sujet

0 membre(s), 1 invité(s), 0 utilisateur(s) anonyme(s)

authorised training centre

Centre de Formation Mediabox - Adobe et Apple Authorised Training Center.

Déclaré auprès de la Direction du Travail et de la Formation Professionnelle

Mediabox : SARL au capital de 62.000€ - Numéro d'activité : 11 75 44555 75 - SIRET : 49371646800035

MEDIABOX, 23, rue de Bruxelles, 75009 PARIS

FFP