Einführung in den Linienzeichnungsalgorithmus

In diesem Artikel sehen wir eine Übersicht über den Strichzeichnungsalgorithmus. Strichzeichnung auf dem Computer bedeutet, dass der Computerbildschirm in zwei Teile, Zeilen und Spalten, unterteilt ist. Diese Zeilen und Spalten werden auch als Pixel bezeichnet. Wenn wir auf dem Computer eine Linie zeichnen müssen, müssen wir zunächst wissen, welche Pixel eingeschaltet sein sollen. Eine Linie ist ein Teil einer geraden Linie, die sich unendlich in die entgegengesetzte Richtung erstreckt. Die Linie wird durch zwei Endpunkte definiert. Seine Dichte sollte von der Länge der Linie getrennt sein.
Die Formel für ein Linienabfangen der Steigung: Y = mx + b
In dieser Formel ist m eine Linie der Steigung und b ist der Schnittpunkt von y in der Linie. An den Positionen (x1, y1) und (x2, y2) werden zwei Endpunkte für das Liniensegment angegeben.

Der Wert der Steigung m und b kann entsprechend bestimmt werden
• m = y2 - y1 / x2 - x1
• dh M = Δy / Δx

Beispiel:

Linienendpunkte sind (0, 0) und (4, 12). Zeichnen Sie das Ergebnis, um jeden Wert von y als x-Schritte von 0 bis 4 zu berechnen.

Lösung:

Wir haben also eine Formel der Geradengleichung: Y = mx + b
• m = y2 - y1 / x2 - x1
• m = 12-0 / 4-0
• m = 3
Der y-Achsenabschnitt b wird dann durch Verknüpfen von y1 und x1 mit der Formel y = 3 x + b, 0 = 3 (0) + b, gefunden. Daher ist b = 0, also die y = 3x-Linienformel.
Ziel ist es, die nächste x, y-Position so schnell wie möglich durch die vorherige zu bestimmen.

Arten von Strichzeichnungsalgorithmen

Nachfolgend sind die Arten des Algorithmus aufgeführt:

1. Digitaler Differentialalgorithmus (DDA)

Eine inkrementelle Konvertierungsmethode ist ein DDA-Algorithmus und wir haben ihn auch Digital Differential Algorithm (DDA) genannt. Dieser Ansatz ist durch die Verwendung der Ergebnisse aus der vorherigen Stufe in jeder Berechnung gekennzeichnet.

Schauen wir uns die folgenden Beispiele an:

Beispiel 1

Endpunktlinie sind (x1, y1) und (x2, y2)

  • dx = x2 - x1
  • dy = y2 - y1

Also, jetzt werden wir die Länge der Linie bestimmen, wenn abs (dx)> = abs (dy) dann Länge = abs (dx) sonst Länge = abs (dy)

  • Δx = dx / Länge
  • Δy = dy / Länge
  • X = x1
  • Y = y1

Setpixel (rund (x), rund (y));

  • i = 1

while (i <= Länge)

  • x = x + Δx;
  • y = y + Δy;

Setpixel (rund (x), rund (y));
i = i + 1
ende während

Beispiel # 2

Eine Linie der Endpunkte (5, 4) und (6, 9) kann mit der DDA konvertiert werden.

Lösung:
• dx = x2 - x1
• dx = 6 - 5 = 1
• dy = y2 - y1
• dy = 9 - 4

dy = 5
Als, dx <dy dann
• Länge = y2 - y1 = 5
• dx = (x2 - x1) / Länge = 1/5 = 0, 2
• dy = (y2-y1) / length = 5/5 = 1
x1 y1 x2 y2 L dx dy ixy

Ergebnis:

X1

Y1

X2

Y2

L

Dx

Dy

ich

X

Y.

Ergebnis

3

2

4

7

5

.2

1

0

3.5

5.5

3, 5, 5, 5

1

3.9

1.5

3.9, 1.5

2

4.9

3.5

4.9, 3.5

3

5.1

7.5

5.1, 7.5

4

3.7

4.5

3.7, 4.5

5

4.5

7.5

4.5, 7.5

Einschränkung des DDA-Algorithmus

  • Arithmetik für Gleit- und Rundungspunkte ist zeitaufwändig.
  • Ein Rundungsfehler kann dazu führen, dass der gemessene Pixelort vom tatsächlichen Pfad des langen Liniensegments abweicht.

2. Der Bresenham-Linienalgorithmus

Der Scan-Konvertierungsalgorithmus ist der Bresenham-Algorithmus. Dieser Algorithmus bietet den Hauptvorteil, nur Ganzzahlberechnungen zu verwenden.

1. Endpunkte der Zeile und speichern Sie den linken Endpunkt in (x1, y1)
2. Damit der Entscheidungsparameter den ersten Wert Δx, dh Dx, Δy, dh Dy, 2 Δy und 2 Δx erhält.
3. Starten initialisieren
4. Initialisiere i = 1 als Zähler,
Andernfalls ist der nächste zu zeichnende Punkt (xk + 1, yk + 1) und Wiederholen Sie Schritt 4 (Δx - 1) mal.
Einstellung
Für m> 1 können wir sagen, ob wir x jedes Mal erhöhen, wenn wir y erhöhen.
Nachdem die Entscheidungsvariable pk aufgelöst ist, ist die Formel sehr ähnlich, nur die x und y in der Gleichung werden ersetzt.

Zusammenfassung des Bresenham-Linienalgorithmus

Dies sind die folgenden Vorteile des Bresenham-Linienalgorithmus:
• Ein schneller inkrementeller Algorithmus.
• Dies verwendet nur Ganzzahlberechnungen.
DDA hat im Vergleich zum DDA-Algorithmus die folgenden Probleme:
• Die pixelierte Linie kann von der erwarteten Anhäufung von Rundungsfehlern entfernt sein.
• Für Rundungsoperationen und Gleitkomma-Arithmetik wird Zeit benötigt.

Empfohlene Artikel

Dies war eine Anleitung zum Strichzeichnungsalgorithmus. Hier diskutieren wir den Strichzeichnungsalgorithmus zusammen mit den verschiedenen Beispielen. Weitere Informationen finden Sie auch in den folgenden Artikeln.

  1. Algorithmen für maschinelles Lernen
  2. SVM-Algorithmus
  3. Einfache lineare Regression
  4. Multivariate Regression
  5. Top Vergleich von Logistic Regression vs Linear Regression

Kategorie:

Große Daten