Inleiding tot lijntekeningalgoritme

In dit artikel zien we een overzicht van het lijntekeningalgoritme. Lijntekening op de computer betekent dat het computerscherm opgedeeld is in twee delen rijen en kolommen. Die rijen en kolommen worden ook wel Pixels genoemd. Als we eerst een lijn op de computer moeten tekenen, moeten we eerst weten welke pixels er moeten zijn. Een lijn is een deel van een rechte lijn die zich oneindig in de tegenovergestelde richting uitstrekt. De lijn wordt gedefinieerd door twee eindpunten. De dichtheid moet gescheiden zijn van de lengte van de lijn.
De formule voor een lijnonderschepping van de helling: Y = mx + b
In deze formule is m een ​​lijn van de helling en is b intercept van y in de lijn. In posities (x1, y1) en (x2, y2) zijn twee eindpunten opgegeven voor het lijnsegment.

De waarde van helling m en b kan dienovereenkomstig worden bepaald
• m = y2 - y1 / x2 - x1
• ie M = Δy / Δx

Voorbeeld:

Lijneindpunten zijn (0, 0) en (4, 12). Plot het resultaat om elke waarde van y te berekenen als de x-stappen van 0 tot 4.

Oplossing:

Dus we hebben een formule van lijnvergelijking: Y = mx + b
• m = y2 - y1 / x2 - x1
• m = 12 - 0/4 - 0
• m = 3
De y onderschept b wordt vervolgens gevonden door y1 en x1 te koppelen aan de formule y = 3 x + b, 0 = 3 (0) + b. Daarom is b = 0, dus de y = 3x lijnformule.
Het doel is om de volgende x, y-locatie zo snel mogelijk te bepalen door de vorige.

Soorten lijntekeningalgoritme

Hieronder worden de typen van het algoritme gegeven:

1. Digitaal differentieel algoritme (DDA)

Een incrementele conversiemethode is een DDA-algoritme en we hebben ook Digital Differential Algorithm (DDA) genoemd. Deze benadering wordt gekenmerkt door het gebruik van de resultaten van de vorige fase in elke berekening.

Laten we de onderstaande voorbeelden bekijken:

Voorbeeld 1

Eindpuntlijn zijn (x1, y1) en (x2, y2)

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

dus nu zullen we de lengte van de lijn bepalen als abs (dx)> = abs (dy) dan lengte = abs (dx) anders lengte = abs (dy)

  • Ax = dx / lengte
  • Ay = dy / lengte
  • X = x1
  • Y = y1

Setpixel (rond (x), rond (y));

  • i = 1

terwijl (i <= lengte)

  • x = x + Ax;
  • y = y + Ay;

setpixel (rond (x), rond (y));
i = i + 1
einde terwijl

Voorbeeld 2

Een lijn van eindpunten (5, 4) & (6, 9) kan worden geconverteerd met de DDA.

Oplossing:
• dx = x2 - x1
• dx = 6 - 5 = 1
• dy = y2 - y1
• dy = 9 - 4

dy = 5
Zoals, dx <dy dan,
• lengte = y2 - y1 = 5
• dx = (x2 - x1) / lengte = 1/5 = 0, 2
• dy = (y2- y1) / lengte = 5/5 = 1
x1 y1 x2 y2 L dx dy ixy

Resultaat:

X1

Y1

X2

Y2

L

dx

Dy

ik

X

Y

Resultaat

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

Beperking van het DDA-algoritme

  • Rekenen voor zwevende en afrondingspunten zijn tijdrovende procedures.
  • Een afrondingsfout kan leiden tot een afstand van het ware lange-lijnsegmentpad door de gemeten pixellocatie.

2. Het Bresenham Line-algoritme

Het scanconversie-algoritme is Bresenham-algoritme. Dit algoritme biedt het belangrijkste voordeel dat alleen hele getallen worden gebruikt.

1. Eindpunten van de rij en sla het linker eindpunt op in (x1, y1)
2. Voor de beslissingsparameter om de eerste waarde Δx te krijgen, dwz Dx, Δy dwz Dy, 2 Δy en 2 Δx.
3. Initialiseer het starten
4. Initialiseer i = 1 als een teller,
Anders is het volgende punt om te plotten (xk + 1, yk + 1) en herhaal stap 4 (Δx - 1) keer.
Aanpassing
Voor m> 1 kunnen we zeggen of we x verhogen telkens we y verhogen.
Nadat de beslissingsvariabele pk is opgelost, lijkt de formule erg op elkaar, alleen de x en y in de vergelijking worden vervangen.

Bresenham Line Algorithm Samenvatting

Dit zijn de volgende voordelen van het Bresenham-lijnalgoritme:
• Een snel incrementeel algoritme.
• Dit gebruikt alleen gehele getallen.
DDA heeft de volgende problemen in vergelijking met het DDA-algoritme:
• De korrelige lijn kan ver verwijderd zijn van de verwachte accumulatie van afrondingsfouten.
• Tijd is vereist voor afrondingen en rekenkundige zwevende punten.

Aanbevolen artikelen

Dit is een leidraad geweest voor Algoritme voor lijntekening. Hier bespreken we wat lijntekeningalgoritme is, samen met de verschillende voorbeelden. U kunt ook de volgende artikelen bekijken voor meer informatie–

  1. Machine Learning-algoritmen
  2. SVM-algoritme
  3. Eenvoudige lineaire regressie
  4. Multivariate regressie
  5. Topvergelijking van lineaire regressie versus logistieke regressie

Categorie:

Big Data