Comment calculez-vous le point le plus proche sur 2 courbes?

Compte tenu des points d'une ligne et d'une courbe de Bézier quadratique, comment calculez-vous leur point le plus proche? .... De même, étant donné les points de 2 courbes, comment obtenez-vous le point le plus proche?

Voici mon essai. Les algorithmes suivants sont loin d'être parfaits , mais ils sont simples et je pense que vous devriez commencer par cela, vérifier s'ils fonctionnent dans votre situation et passer à quelque chose de plus rapide et / ou plus précis plus tard.

L'idée est la suivante:

• Échantillonnez la courbe de Bézier, trouvez le point le plus proche sur cet échantillon
• Échantillonner un quartier autour du point trouvé, trouver un nouveau point le plus proche
• Continuez jusqu'à ce que le point ne change plus beaucoup

Algorithme de distance de la courbe de Bézier à la ligne

La courbe de Bézier est paramétrée par une fonction F(t)utilisant un ensemble de points de contrôle et un paramètre variable t. Le nombre de points de génération est sans importance.

La ligne est paramétrée par deux points Aet B.

1. Soit SAMPLES = 10par exemple

2. Commencez par t0 = 0ett1 = 1

3. Laisser dt = (t1 - t0) / SAMPLES

4. Si dt < 1e-10(ou toute autre condition de précision que vous jugez appropriée), l' algorithme est terminé et la réponse estF(t0) .

5. Calculez une liste de SAMPLES + 1points sur la courbe de Bézier:

   • L[0] = F(t0)
   • L[1] = F(t0 + dt)
   • L[2] = F(t0 + 2 * dt)
   • …
   • L[SAMPLES] = F(t0 + SAMPLES * dt)

6. Trouvez le point Ld'index le iplus proche de la ligne. Utilisez n'importe quelle méthode de distance point / ligne que vous connaissez, par exemple la distance carrée ||AB^L[i]A||² / ||AB||²où ^dénote le produit croisé et ||…||est la distance.

7. Si i == 0, réglez i = 1; si i == SAMPLES, réglezi = SAMPLES - 1

8. Soit t1 = t0 + (i + 1) * dtett0 = t0 + (i - 1) * dt

9. Revenez à l'étape 3.

Algorithme de distance de la courbe de Bézier à la courbe de Bézier

Cette fois, nous avons deux courbes de Bézier, paramétrées par F(t)et G(t).

1. Soit SAMPLES = 10par exemple

2. Commencez avec t0 = 0, t1 = 1, s0 = 0ets1 = 1

3. Laisser dt = (t1 - t0) / SAMPLES

4. Laisser ds = (s1 - s0) / SAMPLES

5. Si dt < 1e-10(ou toute autre condition de précision que vous jugez appropriée), l' algorithme est terminé et la réponse estF(t0) .

6. SI c'est la première exécution de la boucle:

   6.1. Calculez une liste de SAMPLES + 1points sur F( voir ci-dessus ).

   6.2. Calculez une liste de SAMPLES + 1points sur G.

   6.3. Trouvez quelle paire de points est la plus proche l'une de l'autre.

   6.4. Mise à jour t0, t1, s0, s1comme on le voit ci - dessus.

7. AUTRE : calculer alternativement une liste de points sur F OU une liste de points sur G, puis trouver quel point Fest le plus proche G(s0)et mettre à jour t0et t1, OU quel point Gest le plus proche F(t0)et mettre à jour s0et s1.

8. Revenez à l'étape 3.

Problèmes

De par leur conception, ces algorithmes convergeront toujours vers un minimum local. Cependant, rien ne garantit qu'ils convergeront vers la meilleure solution. En particulier, l'algorithme de courbe de Bézier n'est pas très bon du tout, et dans le cas où deux courbes sont proches l'une de l'autre à de nombreux endroits, vous risquez malheureusement de manquer la solution de loin.

Mais comme je l'ai dit, avant de commencer à penser à des solutions plus robustes, vous devez d'abord expérimenter ces solutions simples.

1) Traduisez tout en un axe, donc au lieu de devoir calculer la longueur d'un point, la «ligne», la «ligne» est, disons, l'axe Y.

Ensuite, euh, étant donné une courbe de Bézier, je dirais que cela dépend du nombre de points de contrôle.

S'il y en a trois, (début, «contrôle» et fin), je ferais une sorte de scan (disons chacun deux pour cent puis affine entre les plus proches (avec disons une approche «binaire»).

Plus de points, j'essaierais le couple le plus proche de (traduit de l'axe Y).

Je suis sûr qu'un math-guy peut vous donner la solution exacte (en mathématiques) mais si vous voulez trouver la solution / a dans un jeu vidéo, vous pourriez être mieux avec une solution légèrement correcte car la vraie solution peut contenir plusieurs réponses ( Je ne parle même pas de puissance de traitement).

Quelques réponses de la page du blog Algorithmist , qui trouve correctement le point le plus proche sur la courbe de Bézier quadratique donnée.

Démo .

Pour la courbe de Bézier - cas de ligne droite, la façon la plus précise de trouver la réponse est de procéder comme suit:

1. Transformez le problème pour que la ligne droite soit toujours horizontale à Y = 0. Cela se fait en multipliant tous les points de contrôle par une matrice affine appropriée. (Je suppose que vous connaissez la représentation des transformations affines du plan avec des matrices 3x3 avec 3 entrées fixes.)
2. Inspectez les coordonnées Y des points de contrôle. S'ils n'ont pas tous le même signe, il peut y avoir une intersection avec la ligne. Calculez les racines de la partie Y de la courbe de Bézier. Vous pouvez utiliser n'importe quelle méthode de recherche de racine pour les polynômes, il y en a beaucoup dans la littérature. Par exemple, google "marche de coque convexe" - c'est une méthode raisonnablement bonne pour les polynômes utilisés dans les courbes de Bézier. Chaque racine que vous trouvez est une valeur temporelle d'une intersection avec la ligne, où la distance est nulle - votre travail est terminé.
3. Si toutes les coordonnées Y ont le même signe, calculez la dérivée de la partie Y de la courbe de Bézier. Vous pouvez ignorer les coordonnées X des points, car ils ne font aucune différence - la ligne cible est horizontale. Trouvez les racines de ce dérivé. Ce sont les valeurs temporelles auxquelles la courbe est localement la plus proche de la ligne.
4. Évaluez explicitement la courbe de Bézier pour toutes les racines que vous avez trouvées à l'étape précédente et indiquez la racine qui donne la plus petite distance de la ligne. Vous devez également vérifier les points de terminaison - ils peuvent donner une distance plus petite que n'importe quelle racine.