Eine Geschichte über das Zeichnen einer geraden Anti-Aliasing-Linie ** auf Ihre eigene Weise **, indem Sie einfach Matrixoperationen ausführen, ohne sich auf eine Bildverarbeitungsbibliothek verlassen zu müssen. Auch mit Pythonista möglich

** Klicken Sie hier für Grundlagen ** ** Klicken Sie hier zum Zeichnen **

Originalforschung !?

[Bresenhams Algorithmus](https://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AC%E3%82%BC%E3%83%B3%E3%83%8F%E3 Lesen Sie% 83% A0% E3% 81% AE% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0) Dann gibt es Xiaolin Wus Algorithmus und es gibt auch [Gupta-Sproulls Algorithmus](http: //d.hatena). Es gab .ne.jp / ousttrue / 20090224/1235499257). Ich dachte jedoch, ich würde mein Bestes geben, wenn ich die Matrixberechnung verwenden würde. Ich habe es meine eigene Forschung genannt, weil ich es nicht finden konnte, aber ich denke nicht, dass es einzigartig ist. (Kurz gesagt, Neuerfindung)

Konzept

Von hier Ausgeliehen

Die obige Abbildung zeigt, dass eine gerade Linie mit einer Dicke von 1 verschiedene Pixel überspannt. Ich möchte jedem Pixel eine Dichte geben, die diesem Spreizbereich entspricht.

Situationseinstellungen

Entschuldigung von Hand

Die obige Abbildung zeigt, wie eine gerade Linie im Pixel gezeichnet wird. Das heißt, die Quadrate geben Pixel an, und die drei diagonal gezeichneten geraden Linien geben eine dicke gerade Linie T an (die mittlere gerade Linie M ist die Mittellinie). Betrachten Sie ein Pixel, dessen Mittelpunkt der Punkt A $ (n_x, n_y) $ ist, und eine gerade Linie T $ ax + by + c = 0 $, deren Dicke $ w / 2 $ beträgt. $ A \ geq-b \ geq0, a> 0 $. Außerdem beträgt die Steigung der Geraden $ \ theta = - \ arctan \ frac {b} {a} $.

Dieses Pixel hat oben links vier Eckpunkte $ A_ {ul} (n_x-0.5, n_y-0.5) $, Oben rechts $ A_ {ur} (n_x-0,5, n_y + 0,5) $, Unten links $ A_ {dl} (n_x + 0,5, n_y-0,5) $, Unten rechts $ A_ {dr} (n_x + 0,5, n_y + 0,5) $.

Andererseits sind für die dicke gerade Linie T in der Figur U gezeigt, die die Obergrenze anzeigt, D die Untergrenze anzeigt und M in der Mitte verläuft. Sowohl die obere als auch die untere Linie sind durch $ w / 2 $ von der Mittellinie getrennt, und die Gesamtdicke beträgt $ w $.

Außerdem sind die geraden Linien, die mit dem linken und rechten Ende des Pixels in der Mitte von A zusammenfallen, L bzw. R, und die Indizes der Buchstaben L und R ändern sich abhängig davon, welche gerade Linie sie schneiden.

Problemstellung

In der obigen Situation finden Sie den Bereich S des gemeinsamen Teils (hellblau) von Pixel A und des parallelen Vierecks B $ L_UR_UR_DL_D $ (Punkt B ist ein Punkt auf der Geraden M in der positiven Richtung der x-Achse von A).

Definition von S_X

Wenn $ t = (x-Koordinate von B) - (x-Koordinate von A_ {ul} A_ {ur}) $, unterhalb des Liniensegments $ A_ {ul} A_ {ur} $ (positive Richtung der x-Achse) Der Bereich einer bestimmten Figur $ X $ sei $ S_X (t) $ (Bild der parallelen Bewegung der Figur von oben nach unten)

S=S_B(t)-S_B(t-1)

Wird sein. Der zweite Term ist der Bereich unterhalb des Liniensegments $ A_ {dl} A_ {dr} $. Daher sollte $ S_B (t) $ berechnet werden.

Zerlegung des parallelen Vierecks B.

Wie in der Abbildung gezeigt, kann das parallele Viereck B $ L_UR_UR_DL_D $ in drei Teile unterteilt werden: ein rotes rechtwinkliges Dreieck $ \ Dreieck Rot $, ein blaues rechtwinkliges Dreieck $ \ Dreieck Blau $ und ein weißes Rechteck $ \ Box Weiß $. .. (In der folgenden Abbildung hat das weiße Rechteck einen negativen Bereich.)

Dann

S_B(t) = S_{\triangle Red}(t) +S_{\triangle Blue}(t) +S_{\Box White}(t)

Wird sein.

Betrachten Sie daher $ S_X (t) $ für jede Figur. Darüber hinaus sollte beachtet werden

\tau_\triangle=\frac{1}{2}\left(w/\cos\theta +tan\theta\right)\\
\tau_\Box=\frac{1}{2}\left(w/\cos\theta -tan\theta\right)

Und. ($ \ Tau_ \ triangle $ entspricht der $ x $ -Koordinatendifferenz zwischen B und $ R_D $ und $ L_U $, und $ \ tau_ \ Box $ entspricht der $ x $ -Koordinatendifferenz zwischen B und $ R_U $ und $ L_D $. Ist)

Erstens ist die Gesamtfläche dieser drei Teile

\triangle Red=\triangle Blue = 0.5\tan\theta = \frac{\tau_\triangle-\tau_\Box}{2}\\
\Box White = 2\tau_\Box
\\

Betrachten Sie als nächstes jedes $ S_X (t) $. $ \ Triangle Red $ überschreitet $ A_ {ul} A_ {ur} $, wenn $ t = - \ tau_ \ triangle $, und die gesamte Zahl passt, wenn $ t = - \ tau_ \ Box $. Auch die Zunahme dazwischen ist eine nach unten konvexe quadratische Funktion.

S_{\triangle Red}(t) = 
\begin{cases}
0 & 
    (t<-\tau_\triangle)\\
\frac{1}{2}\frac{1}{\tau_\triangle-\tau_\Box}\left(t+\tau_\triangle\right)^2 & 
    (-\tau_\triangle\leq t\leq-\tau_\Box)\\
\frac{\tau_\triangle-\tau_\Box}{2} & 
    (-\tau_\Box<t)
\end{cases}

$ \ Box White $ überschreitet $ A_ {ul} A_ {ur} $, wenn $ t = \ min (- \ tau_ \ Box, \ tau_ \ Box) $ und $ t = \ max (- \ tau_ \ Box) , \ tau_ \ Box) Wenn $, passt die ganze Zahl. Da der Anstieg in der Zwischenzeit linear funktionell ist,

S_{\Box White}(t) = 
\begin{cases}
0 &
    (t<-\tau_\Box)\\
t+ \tau_\Box & 
    (-\tau_\Box\leq t)\\
\end{cases}
+
\begin{cases}
0 &
    (t<\tau_\Box)\\
-t+ \tau_\Box & 
    (\tau_\Box\leq t))\\
\end{cases}

$ \ Triangle Blue $ überschreitet $ A_ {ul} A_ {ur} $, wenn $ t = \ tau_ \ Box $, und die gesamte Zahl passt, wenn $ t = \ tau_ \ triangle) $. Auch der Anstieg in der Zwischenzeit ist eine quadratische Funktion, die nach oben konvex ist. Dies entspricht daher der Funktion, $ S_ {\ triangle Red} (t) $ punktsymmetrisch zum Ursprungsziel zu bewegen und dann $ \ frac {\ tau_ \ triangle- \ tau_ \ Box} {2} $ hinzuzufügen. ..

S_{\triangle Blue}(t) =　\frac{\tau_\triangle-\tau_\Box}{2}-S_{\triangle Red}(-t)

Code

Die Anfangsbedingungen sind wie folgt.

import numpy as np
import matplotlib.pyplot as plt

x, y  = np.mgrid[:10,:10]
a, b, c = 2, -1, -1
w = 1

Berechnung von t

Das ist einfach. Addieren Sie einfach 0,5 zum Abstand zwischen dem Pixel und der geraden Linie.

import numpy as np
import matplotlib.pyplot as plt

x, y  = np.mgrid[:10,:10]
a, b, c = 2, -1, -1
w = 1

t = - b/a * y - c/a - x + 0.5

Berechnung von τ

Berechnen Sie, ohne $ \ theta $ zu durchlaufen.

tau_triangle = (w*(a**2 + b**2)**0.5/a - b/a)/2
tau_square = (w*(a**2 + b**2)**0.5/a + b/a)/2

Berechnung von S_X

#S_Weil es auch in blau verwendet wird, S._Deklarieren Sie Rot als Funktion
S_red_func = lambda t :\
        np.where(t<-tau_triangle,0,
        np.where(t<= -tau_square,(t+tau_triangle)**2/(2*(tau_triangle - tau_square)),
                                 (tau_triangle - tau_square)/2))
S_red = S_red_func(t)
S_blue = (tau_triangle - tau_square)/2 - S_red_func(-t)
S_white = np.where(t<-tau_square,0, t+tau_square) + \
          np.where(t<tau_square,0, -t+tau_square)

#S_Erstellen Sie B.
S_B = S_red + S_blue + S_white

Berechnen Sie die Differenz in S_X

Verwenden Sie np.diff. Um $ S_B (t) -S_B (t-1) $ zu berechnen, muss -np.diff (S_B) vor und nach der Subtraktion angeordnet werden verwenden. Es wird auch eine Konvertierung durchgeführt, um eine schwarze gerade Linie auf einem weißen Hintergrund zu erstellen.

img_how_long_did_it_take_to_get_this = -np.diff(S_B,axis = 0)

#Der Maximalwert beträgt 1 Pixelfläche=1
img_black = 1-img_how_long_did_it_take_to_get_this
plt.imshow(img_black, cmap = 'gray')

Beachten Sie, dass die vertikalen Pixel aufgrund des Unterschieds um 1 dekrementiert werden.

Als Funktion zusammenfassen

Erstellen Sie eine Funktion, nachdem Sie die Bedingung $ a \ geq-b \ geq0, a> 0 $ entfernt haben. (Außerdem wird keine Ausnahmeverarbeitung durchgeführt, wenn a und b 0 sind.)

def my_antialias(height, width, a, b, c, w=1):
    '''Gerade Axt mit der Dicke w in einer Ebene mit Höhe, Höhe und Breite, Breite+ by + c =Zeichne 0 mit Antialiasing.'''
    
    #Fügen Sie den Betrag hinzu, der abnimmt, wenn Sie zuerst das Diff nehmen
    x, y  = np.mgrid[:height + 1,:width]
    
    #Berechne t(ein Mal)
    t = 0.5*a - (a*x + b*y + c)
    
    #Berechnen Sie τ(a mal)
    tau_triangle = (w*(a**2 + b**2)**0.5 +abs(b))/2
    tau_square = (w*(a**2 + b**2)**0.5 - abs(b))/2
    
    #Berechnung von S.
    S_red_func = lambda t :\
            np.where(t<-tau_triangle,0,
            np.where(t<= -tau_square,(t+tau_triangle)**2/(2*(tau_triangle - tau_square)),
                                     (tau_triangle - tau_square)/2))
    S_red = S_red_func(t)
    S_blue = (tau_triangle - tau_square)/2 - S_red_func(-t)
    S_white = np.where(t<-tau_square,0, t+tau_square) + \
              np.where(t<tau_square,0, -t+tau_square)
    
    #t,Da τ mit a multipliziert wird, dividiere durch a
    S_B = (S_red + S_blue + S_white)*a
    return -np.diff(S_B,axis = 0)

plt.imshow(my_antialias(20,20,-3,-7,60,1),cmap = 'gray',vmin = 0,vmax=1)
plt.show()

Das Folgende ist übrigens [Nachahmung des Bresenham-Algorithmus](http://qiita.com/secang0/items/b45272a6f1212510ef99#%E3%83%96%E3%83%AC%E3%82%BC%E3%83%B3% E3% 83% 8F% E3% 83% A0% E3% 81% AE% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0% E6% 93% AC% E3% 81% 8D% E3% 81% AB% E3% 82% 88% E3% 82% 8B% E7% 9B% B4% E7% B7% 9A% E6% 8F% Es ist eine gerade Linie, die von 8F% E7% 94% BB) erzeugt wird.

In meiner Ausführungsumgebung war die Verwendung des Bresenham-Algorithmus 3-4 Mal schneller.

Lineares Zeichnen mit einer Matrix-Originalforschung von einem Neuerfinder der Python-Bildverarbeitung-