[PYTHON] Je veux trouver l'intersection d'une courbe de Bézier et d'une ligne droite (méthode de découpage de Bézier)

introduction

Dans mes recherches juniors, j'ai dû trouver l'intersection de la courbe de Bézier et de la ligne droite. J'aidais à la recherche

"** Python est une bibliothèque solide ou un exemple d'implémentation concis! Margin **: grin:"

Je réfléchissais, mais je n'ai pas trouvé d'article écrit ** à un niveau que je pouvais comprendre. Il n'y a pas d'autre choix que de se concentrer sur la méthode de découpage de Bézier, qui semble relativement facile et un PDF de commentaire a été trouvé. J'ai lu le document, je l'ai compris et mis en œuvre, alors je vais laisser cette connaissance. Veuillez noter que certaines expressions peuvent être inexactes dans l'article (et veuillez me donner quelques corrections).

Le code implémenté est publié sur GitHub.

Qu'est-ce qu'une courbe de Bézier?

La courbe de Bézier est un type de représentation d'une courbe. Il est souvent utilisé pour représenter des courbes sur un ordinateur telles que les polices vectorielles et CG. La courbe de Bézier se compose de plusieurs points appelés points de contrôle, en plus des points de début et de fin de la courbe. Ci-après, les points de contrôle comprenant le point de départ et le point final seront mentionnés. La courbe de Bézier est exprimée comme suit en utilisant la variable médiatrice $ t $$ (0 \ leq t \ leq 1) $.

\begin{align}
P(t) &= \sum_{i=0}^{n} F_i B_{i}^{n}(t) \\
&= \sum_{i=0}^{n} F_i {n \choose i} t^i \left(1-t \right)^{n-i}
\end{align}

$ F_i $ est le point de contrôle et $ B_ {i} ^ {n} $ est les polynômes de base de Bernstein. De plus, $ {n \ choose i} $ représente une combinaison. La norme mondiale semble être cette façon d'écrire, mais si vous l'écrivez comme vous l'avez appris au lycée japonais, ce sera comme suit.

P(t) = \sum_{i=0}^{n} F_i ~~ {}_n \mathrm{C} {}_r ~~ t^i \left(1-t \right)^{n-i}

Puisque la courbe de Bézier est un ensemble de points à $ t $$ (0 \ leq t \ leq 1) $, Plus la taille de pas de $ t $ est fine, plus la courbe est lisse. Voici un exemple de modification de la taille de pas. Les points gris $ \ times $ représentent les points de contrôle. ** $ (0 \ leq t \ leq 1) Lorsque $ est divisé en 5 (lorsque seulement 5 points sont calculés). ** **

** Lorsque $ (0 \ leq t \ leq 1) $ est divisé en 10 (lorsque seulement 10 points sont calculés). ** **

** Lorsque $ (0 \ leq t \ leq 1) $ est divisé en 50 (lorsque seulement 50 points sont calculés). ** **

** Lorsque $ (0 \ leq t \ leq 1) $ est divisé en 100 (lorsque seulement 100 points sont calculés). ** **

Méthode de découpage de Bézier

Aperçu

La méthode de découpage de Bézier est une méthode permettant de trouver l'intersection d'une courbe et d'une ligne droite en utilisant les propriétés de la courbe de Bézier. Proposé en 1990 par Nishida et al. Les caractéristiques sont les suivantes (extrait partiel).

--Toutes les solutions (intersections) dans la plage spécifiée peuvent être trouvées

Une solution stable est requise
Jugement rapide de l'existence d'une solution
Les solutions peuvent être calculées par ordre croissant --Calcul itératif d'expressions linéaires uniquement ... etc

Il semble qu'il puisse également s'appliquer aux intersections entre les courbes de Bézier et les intersections dans l'espace 3D. Cette fois, nous le limiterons aux courbes de Bézier et aux lignes droites.

algorithme

Le flux général de l'algorithme est le suivant. ** 1. Convertissez la courbe de Bézier cible en une courbe de Bézier qui représente la distance par rapport à la ligne droite (conversion du plan $ xy $ au plan $ td $). ** ** ** 2. Trouvez la coque convexe du point de contrôle de la courbe de Bézier convertie, et trouvez les intersections $ t_ {min} et t_ {max} $ avec l'axe $ t $. ** **

** 3. Divisez la courbe de Bézier par les $ t_ {min} et t_ {max} $ obtenus pour créer une nouvelle courbe de Bézier. ** ** ** 4. Répétez le processus 2-3 jusqu'à ce que l'intervalle $ [t_ {min}, ~ t_ {max}] $ devienne suffisamment petit. ** ** ** 5. Le $ t $ obtenu (point rouge dans la figure ci-dessus) devient la variable médiatrice $ t $ de la courbe de Bézier originale à l'intersection avec la ligne droite. ** **

L'algorithme lui-même est très simple. Probablement l'endroit pour rester coincé

** Processus de conversion de la courbe de Bézier **
** Traitement lorsqu'il y a plusieurs intersections **

Je pense que c'est le cas, alors je vais l'expliquer en détail dans la section suivante.

Processus de conversion de la courbe de Bézier

Il suppose un espace de coordonnées plan bidimensionnel. La droite $ L $ dans l'espace plan peut être exprimée comme suit: $ a, b, c $ sont des constantes.

ax + by + c = 0

La distance $ d $ entre tout point $ (x_1, y_1) $ dans l'espace de coordonnées et la ligne droite $ L $ peut être exprimée comme suit.

d = \frac{ax_1+by_1+c}{\sqrt{a^2 + b^2}}

Ici, le point $ (x, y) $ sur la courbe de Bézier peut être obtenu comme suit avec $ t $ comme variable intermédiaire. $ (x_i, y_i) $ représente le point de contrôle de la courbe de Bézier.

\begin{align}
x(t) &= \sum_{i=0}^{n} x_i B_i^n (t) \\
y(t) &= \sum_{i=0}^{n} y_i B_i^n (t)
\end{align}

En utilisant ces derniers, la distance $ D $ entre la droite $ L $ et la courbe de Bézier peut être exprimée comme suit.

\begin{align}
D &= \frac{ax(t)+by(t)+c}{\sqrt{a^2+b^2}} \\ \\
  &= \frac{1}{\sqrt{a^2+b^2}}\left( a\sum_{i=0}^{n} x_i B_i^n (t) + b\sum_{i=0}^{n} y_i B_i^n (t) + c \right)
\end{align}

$ \ sum_ {i = 0} ^ {n} B_i ^ n (t) = 1 $, donc

\begin{align}
D &= \frac{1}{\sqrt{a^2+b^2}}\left( a\sum_{i=0}^{n} x_i B_i^n (t) + b\sum_{i=0}^{n} y_i B_i^n (t) + c\sum_{i=0}^{n} B_i^n (t) \right) \\ \\
  &= \frac{1}{\sqrt{a^2+b^2}}\sum_{i=0}^{n} (ax_i+by_i+c) B_i^n (t) \\ \\
  &= \frac{1}{\sqrt{a^2+b^2}}\sum_{i=0}^{n} d_i B_i^n (t) 
\end{align}

Ici, $ D $ est une courbe de Bézier rationnelle constituée de points de contrôle $ \ left (\ frac {i} {n}, d_i \ right) $. De plus, $ D $ est la courbe de Bézier dans le plan $ td $, c'est-à-dire la courbe de Bézier dans l'espace plan avec l'axe horizontal $ t $ et l'axe vertical $ d $. Le fait que la courbe de Bézier convertie $ D $ prenne $ d = 0 $ à quelque $ t ~ (0 \ leq t \ leq 1) $ signifie que À cette valeur $ t $, cela signifie que la distance entre la courbe de Bézier et la ligne droite dans le plan $ xy $ avant la conversion est nulle. Par conséquent, la variable médiatrice $ t $ à l'intersection de la droite et de la courbe de Bézier peut être calculée. Après cela, si vous placez la variable médiatrice $ t $ à l'intersection dans l'équation suivante, vous pouvez trouver les coordonnées de l'intersection dans le plan $ xy $.

\begin{align}
x(t) &= \sum_{i=0}^{n} x_i B_i^n (t) \\
y(t) &= \sum_{i=0}^{n} y_i B_i^n (t)
\end{align}

Traitement lorsqu'il y a plusieurs points

Le processus est simple lorsqu'il y a plusieurs intersections. S'il y a plusieurs intersections, le changement entre $ t_ {min} $ et $ t_ {max} $ sera faible. Un exemple est illustré dans la figure ci-dessous. Le point bleu sur la figure représente le point $ t_ {min}, t_ {max} $ précédent.

Première fois Deuxième fois Troisième fois ** 4ème **

A partir de la troisième fois, vous pouvez voir que les positions de $ t_ {min} et t_ {max} $ n'ont pas changé. Dans ce cas, divisez la courbe en un point approprié et appliquez à nouveau la méthode de découpage de Bézier à chaque courbe de Bézier. Il ne semblait pas mentionner le point de division. Dans ma mise en œuvre, j'essaye de le diviser au milieu.

en conclusion

Dans cet article, j'ai expliqué la méthode Bézier Clipping. J'ai eu beaucoup de mal à comprendre la première partie de la conversion. J'espère que le contenu de cet article sera utile à quelqu'un.