[PYTHON] Ich möchte den Schnittpunkt einer Bezier-Kurve und einer geraden Linie finden (Bezier-Clipping-Methode)

Einführung

In meiner Nachwuchsforschung musste ich den Schnittpunkt der Bezier-Kurve und der Geraden finden. Ich habe bei der Recherche geholfen

"** Python ist eine starke Bibliothek oder ein kurzes Implementierungsbeispiel! Margin **: grin:"

Ich habe nachgedacht, aber ich konnte keinen Artikel finden, der ** auf einem Niveau geschrieben wurde, das ich verstehen konnte. Es bleibt keine andere Wahl, als sich auf die Bezier-Clipping-Methode zu konzentrieren, die relativ einfach zu sein scheint und einige PDF-Kommentare gefunden wurden. Ich habe das Papier gelesen, verstanden und umgesetzt, also werde ich dieses Wissen verlassen. Bitte beachten Sie, dass einige Ausdrücke im Artikel möglicherweise ungenau sind (und geben Sie mir bitte einige Korrekturen).

Der implementierte Code wird auf [GitHub] veröffentlicht (https://github.com/takkaO/Bezier_Clipping_Algorithm).

Was ist eine Bezier-Kurve?

Die Bezier-Kurve ist eine Art Darstellung einer Kurve. Es wird häufig verwendet, um Kurven auf einem Computer darzustellen, z. B. Umrissschriften und CG. Die Bezier-Kurve besteht neben den Start- und Endpunkten der Kurve aus mehreren Punkten, die als Kontrollpunkte bezeichnet werden. Im Folgenden wird auf die Kontrollpunkte einschließlich des Startpunkts und des Endpunkts Bezug genommen. Die Bezier-Kurve wird unter Verwendung der Mediatorvariablen $ t $$ (0 \ leq t \ leq 1) $ wie folgt ausgedrückt.

\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 $ ist der Kontrollpunkt und $ B_ {i} ^ {n} $ ist das Bernstein-Basispolynom. Außerdem steht $ {n \ select i} $ für eine Kombination. Der Weltstandard scheint diese Art des Schreibens zu sein, aber wenn Sie es so schreiben, wie Sie es in der japanischen High School gelernt haben, wird es wie folgt sein.

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

Da die Bezier-Kurve eine Menge von Punkten bei $ t $$ (0 \ leq t \ leq 1) $ ist, Je feiner die Schrittweite von $ t $ ist, desto glatter ist die Kurve. Das Folgende ist ein Beispiel für das Ändern der Schrittgröße. Die grauen $ \ times $ -Punkte stehen für Kontrollpunkte. ** $ (0 \ leq t \ leq 1) Wenn $ in 5 geteilt wird (wenn nur 5 Punkte berechnet werden). ** ** **

** Wenn $ (0 \ leq t \ leq 1) $ in 10 geteilt wird (wenn nur 10 Punkte berechnet werden). ** ** **

** $ (0 \ leq t \ leq 1) Wenn $ in 50 geteilt wird (wenn nur 50 Punkte berechnet werden). ** ** **

** Wenn $ (0 \ leq t \ leq 1) $ in 100 geteilt wird (wenn nur 100 Punkte berechnet werden). ** ** **

Bezier Clipping-Methode

Überblick

Die Bezier-Clipping-Methode ist eine Methode zum Ermitteln des Schnittpunkts einer Kurve und einer geraden Linie unter Verwendung der Eigenschaften der Bezier-Kurve. Vorgeschlagen von Nishida et al. Die Merkmale sind wie folgt (Teilauszug).

Alle Lösungen (Schnittpunkte) im angegebenen Bereich können gefunden werden
Eine stabile Lösung ist erforderlich
Schnelles Urteil über die Existenz einer Lösung --Lösungen können in aufsteigender Reihenfolge berechnet werden --Iterative Berechnung nur linearer Ausdrücke ... usw.

Es scheint, dass es auch auf Schnittpunkte zwischen Bezier-Kurven und Schnittpunkten im 3D-Raum angewendet werden kann. Dieses Mal beschränken wir uns auf Bezier-Kurven und gerade Linien.

Algorithmus

Der allgemeine Ablauf des Algorithmus ist wie folgt. ** 1. Konvertieren Sie die Bezier-Zielkurve in eine Bezier-Kurve, die den Abstand zur Geraden darstellt (konvertieren Sie von der $ xy $ -Ebene in die $ td $ -Ebene). ** ** ** ** 2. Finden Sie die konvexe Hülle des Kontrollpunkts der konvertierten Bezier-Kurve und finden Sie die Schnittpunkte $ t_ {min} und t_ {max} $ mit der $ t $ -Achse. ** ** **

** 3. Teilen Sie die Bezier-Kurve durch die erhaltenen $ t_ {min} und t_ {max} $, um eine neue Bezier-Kurve zu erstellen. ** ** ** ** 4. Wiederholen Sie den Vorgang von 2-3, bis das Intervall $ [t_ {min}, ~ t_ {max}] $ ausreichend klein wird. ** ** ** ** 5. Das erhaltene $ t $ (roter Punkt in der obigen Abbildung) wird zur Mediatorvariablen $ t $ der ursprünglichen Bezier-Kurve am Schnittpunkt mit der geraden Linie. ** ** **

Der Algorithmus selbst ist sehr einfach. Wahrscheinlich der Ort, an dem man stecken bleibt

** Bezier-Kurvenumwandlungsprozess **
** Verarbeitung bei mehreren Kreuzungen **

Ich denke, das ist es, deshalb werde ich es im nächsten Abschnitt ausführlich erklären.

Bezier-Kurvenumwandlungsprozess

Es wird ein zweidimensionaler ebener Koordinatenraum angenommen. Die gerade Linie $ L $ im ebenen Raum kann ausgedrückt werden als: $ a, b, c $ sind Konstanten.

ax + by + c = 0

Der Abstand $ d $ zwischen einem beliebigen Punkt $ (x_1, y_1) $ im Koordinatenraum und der geraden Linie $ L $ kann wie folgt ausgedrückt werden.

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

Hier kann der Punkt $ (x, y) $ auf der Bezier-Kurve wie folgt erhalten werden, wobei $ t $ als Mediatorvariable dient. $ (x_i, y_i) $ repräsentiert den Kontrollpunkt der Bezier-Kurve.

\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}

Mit diesen kann der Abstand $ D $ zwischen der Geraden $ L $ und der Bezier-Kurve wie folgt ausgedrückt werden.

\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 $, also

\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}

Hier ist $ D $ eine rationale Bezier-Kurve, die aus Kontrollpunkten $ \ left (\ frac {i} {n}, d_i \ right) $ besteht. Außerdem ist $ D $ die Bezier-Kurve in der $ td $ -Ebene, dh die Bezier-Kurve im Ebenenraum mit der horizontalen Achse $ t $ und der vertikalen Achse $ d $. Die Tatsache, dass die konvertierte Bezier-Kurve $ D $ bei einigen $ t ~ (0 \ leq t \ leq 1) $ $ d = 0 $ annimmt, bedeutet dies Bei diesem $ t $ -Wert bedeutet dies, dass der Abstand zwischen der Bezier-Kurve und der Geraden in der $ xy $ -Ebene vor der Konvertierung Null ist. Daher kann die Mediatorvariable $ t $ am Schnittpunkt der Geraden und der Bezier-Kurve berechnet werden. Wenn Sie danach die Mediatorvariable $ t $ in der folgenden Gleichung an den Schnittpunkt setzen, finden Sie die Koordinaten des Schnittpunkts in der $ xy $ -Ebene.

\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}

Verarbeitung bei mehreren Punkten

Der Vorgang ist einfach, wenn mehrere Kreuzungen vorhanden sind. Wenn es mehrere Schnittpunkte gibt, ist die Änderung zwischen $ t_ {min} $ und $ t_ {max} $ gering. Ein Beispiel ist in der folgenden Abbildung dargestellt. Der blaue Punkt in der Abbildung repräsentiert den vorherigen $ t_ {min}, t_ {max} $ Punkt.

Erstes Mal Zweites Mal Drittes Mal ** 4. **

Ab dem dritten Mal können Sie sehen, dass sich die Positionen von $ t_ {min} und t_ {max} $ nicht geändert haben. Teilen Sie in diesem Fall die Kurve an einem geeigneten Punkt und wenden Sie die Bezier-Beschneidungsmethode erneut auf jede Bezier-Kurve an. Es schien den Punkt der Trennung nicht zu erwähnen. In meiner Implementierung versuche ich, es in der Mitte zu teilen.

abschließend

In diesem Artikel habe ich die Bezier-Clipping-Methode erklärt. Ich hatte große Probleme, den ersten Teil der Konvertierung zu verstehen. Ich hoffe, der Inhalt dieses Artikels wird jemandem nützlich sein.