Introduktion till linjeritningsalgoritm

I den här artikeln kommer vi att se en översikt över linjeteckningsalgoritmen. Ritning på datorn innebär att datorskärmen delar upp i två delar rader och kolumner. Dessa rader och kolumner är också kända som Pixels. Om vi ​​måste dra en linje på datorn måste vi först veta vilka pixlar som ska vara på. En linje är en del av en rak linje som sträcker sig i motsatt riktning på obestämd tid. Linjen definieras av två slutpunkter. Dess täthet bör vara separat från linjens längd.
Formeln för en radavlyssning av lutningen: Y = mx + b
I denna formel är m en linje i sluttningen och b är avlyssning av y i linjen. I positioner (x1, y1) och (x2, y2) anges två ändpunkter för linjesegmentet.

Värdet på sluttningen m och b kan bestämmas i enlighet därmed
• m = y2 - y1 / x2 - x1
• dvs. M = Δy / Δx

Exempel:

Linjeändpunkter är (0, 0) och (4, 12). Plotta resultatet för att beräkna varje värde på y som x-steg från 0 till 4.

Lösning:

Så vi har en formel för ekvationen av linjen: Y = mx + b
• m = y2 - y1 / x2 - x1
• m = 12 - 0/4 - 0
• m = 3
Y-skärningen b hittas sedan genom att länka y1 och x1 till formeln y = 3 x + b, 0 = 3 (0) + b. Därför b = 0, så y = 3x radformel.
Målet är att bestämma nästa plats x, y så snabbt som möjligt av den föregående.

Typer av linjeritningsalgoritm

Nedan anges typerna av algoritmen:

1. Digital Differential Algoritm (DDA)

En inkrementell omvandlingsmetod är en DDA-algoritm och även kallad vi Digital Differential Algoritm (DDA). Denna strategi kännetecknas av användningen av resultaten från föregående steg i varje beräkning.

Låt oss titta på exemplen nedan:

Exempel 1

Slutpunktlinjen är (x1, y1) och (x2, y2)

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

så nu kommer vi att bestämma längden på linjen om abs (dx)> = abs (dy) då längd = abs (dx) annars längd = abs (dy)

  • Δx = dx / längd
  • Δy = dy / längd
  • X = x1
  • Y = y1

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

  • i = 1

medan (i <= längd)

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

setpixel (rund (x), rund (y));
i = i + 1
slut medan

Exempel 2

En rad slutpunkter (5, 4) & (6, 9) kan konverteras med DDA.

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

dy = 5
Som dx <dy då,
• längd = y2 - y1 = 5
• dx = (x2 - x1) / längd = 1/5 = 0, 2
• dy = (y2- y1) / längd = 5/5 = 1
x1 y1 x2 y2 L dx dy ixy

Resultat:

X1

Y1

X2

Y2

L

Dx

Dy

jag

X

Y

Resultat

3

2

4

7

5

0, 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

Begränsning av DDA-algoritmen

  • Aritmetik för flytande och rundade punkter är tidskrävande förfaranden.
  • Ett avrundningsfel kan leda till ett avstånd från den verkliga långlinjesegmentvägen med den uppmätta pixelplatsen.

2. Bresenham Line Algoritm

Scan-konverteringsalgoritmen är Bresenham-algoritmen. Denna algoritm erbjuder den största fördelen med att endast använda heltalberäkningar.

1. Slutpunkter för raden och lagra vänster slutpunkt i (x1, y1)
2. För beslutsparametern att få det första värdet Δx dvs. Dx, Δy dvs. Dy, 2 Δy och 2 Δx.
3. Initiera start
4. Initiera i = 1 som en räknare,
Annars är nästa punkt att plotta (xk + 1, yk + 1) och upprepa steg 4 (Δx - 1) gånger.
Justering
För m> 1 kan vi säga om vi ökar x varje gång vi ökar y.
Efter att beslutsvariabeln pk kommer att lösas är formeln mycket lik, endast x och y i ekvationen kommer att ersättas.

Bresenham Line Algoritm sammanfattning

Dessa är följande fördelar med Bresenham-linjealgoritmen:
• En snabb inkrementell algoritm.
• Detta använder endast heltalberäkningar.
DDA har följande problem jämfört med DDA-algoritmen:
• Den pixelerade linjen kan vara avlägsen från den förväntade ansamlingen av avrundningsfel.
• Det krävs tid för rundning och aritmetik för flytande punkter.

Rekommenderade artiklar

Detta har varit en guide till linjeteckningsalgoritm. Här diskuterar vi vad som är linjeritningsalgoritm tillsammans med de olika exemplen. Du kan också titta på följande artiklar för att lära dig mer–

  1. Maskininlärningsalgoritmer
  2. SVM-algoritm
  3. Enkel linjär regression
  4. Multivariat regression
  5. Toppjämförelse av linjär regression vs logistisk regression

Kategori:

Big Data