Wprowadzenie do algorytmu rysowania linii

W tym artykule zobaczymy zarys algorytmu rysowania linii. Rysowanie linii na komputerze oznacza, że ​​ekran komputera dzieli się na dwie części wierszy i kolumn. Te wiersze i kolumny są również znane jako piksele. W przypadku, gdy musimy narysować linię na komputerze, musimy przede wszystkim wiedzieć, które piksele powinny być włączone. Linia jest częścią linii prostej, która rozciąga się w przeciwnym kierunku w nieskończoność. Linia jest zdefiniowana przez dwa punkty końcowe. Jego gęstość powinna być oddzielna od długości linii.
Wzór na przecięcie linii nachylenia: Y = mx + b
W tym wzorze m jest linią nachylenia, a b przecina y w linii. W pozycjach (x1, y1) i (x2, y2) dla segmentu linii określono dwa punkty końcowe.

Wartość nachylenia mib można odpowiednio określić
• m = y2 - y1 / x2 - x1
• tj. M = yy / Δx

Przykład:

Punktami końcowymi linii są (0, 0) i (4, 12). Wykreślić wynik, aby obliczyć każdą wartość y jako x kroków od 0 do 4.

Rozwiązanie:

Mamy więc wzór na równanie linii: Y = mx + b
• m = y2 - y1 / x2 - x1
• m = 12–0 / 4–0
• m = 3
Punkt przecięcia y b znajduje się następnie przez połączenie y1 i x1 ze wzorem y = 3 x + b, 0 = 3 (0) + b. Dlatego b = 0, więc wzór y = 3x.
Celem jest jak najszybsze określenie następnej lokalizacji x, y przez poprzednią.

Rodzaje algorytmu rysowania linii

Poniżej podano typy algorytmu:

1. Cyfrowy algorytm różnicowy (DDA)

Metodą inkrementalnej konwersji jest algorytm DDA, a także nazywamy to cyfrowym algorytmem różnicowym (DDA). Podejście to charakteryzuje się wykorzystaniem wyników z poprzedniego etapu w każdym obliczeniu.

Spójrzmy na przykłady podane poniżej:

Przykład 1

Linia końcowa to (x1, y1) i (x2, y2)

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

więc teraz określimy długość linii, jeśli abs (dx)> = abs (dy), to długość = abs (dx) inaczej długość = abs (dy)

  • Δx = dx / długość
  • Δy = dy / długość
  • X = x1
  • Y = y1

Setpixel (okrągły (x), okrągły (y));

  • i = 1

while (i <= długość)

  • x = x + xx;
  • y = y + Ay;

setpixel (okrągły (x), okrągły (y));
i = i + 1
skończyć póki

Przykład nr 2

Linię punktów końcowych (5, 4) i (6, 9) można przekonwertować za pomocą DDA.

Rozwiązanie:
• dx = x2 - x1
• dx = 6 - 5 = 1
• dy = y2 - y1
• dy = 9 - 4

dy = 5
Ponieważ dx <dy zatem,
• długość = y2 - y1 = 5
• dx = (x2 - x1) / długość = 1/5 = 0, 2
• dy = (y2-y1) / długość = 5/5 = 1
x1 y1 x2 y2 L dx dy ixy

Wynik:

X1

Y1

X2

Y2

L.

Dx

Dy

ja

X

Y

Wynik

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

Ograniczenie algorytmu DDA

  • Arytmetyka dla punktów zmiennoprzecinkowych i zaokrąglających jest czasochłonna.
  • Błąd zaokrąglenia może prowadzić do odległości od rzeczywistej ścieżki segmentu długiej linii przez zmierzoną lokalizację pikseli.

2. Algorytm linii Bresenhama

Algorytm konwersji skanowania to algorytm Bresenhama. Algorytm ten oferuje główną zaletę korzystania wyłącznie z obliczeń całkowitych.

1. Punkty końcowe wiersza i zapisz lewy punkt końcowy w (x1, y1)
2. Dla parametru decyzji, aby uzyskać pierwszą wartość firstx, tj. Dx, yy, tj. Dy, 2 yy i 2 xx.
3. Zainicjuj uruchamianie
4. Zainicjuj i = 1 jako licznik,
W przeciwnym razie następnym punktem do wykreślenia jest (xk + 1, yk + 1) i powtórz krok 4 (xx - 1) razy.
Dostosowanie
Dla m> 1 możemy powiedzieć, że zwiększamy x za każdym razem, gdy zwiększamy y.
Po rozwiązaniu zmiennej decyzyjnej pk formuła jest bardzo podobna, tylko xiy w równaniu zostaną zastąpione.

Podsumowanie algorytmu linii Bresenhama

Oto następujące zalety algorytmu liniowego Bresenham:
• Szybki algorytm przyrostowy.
• Używa tylko obliczeń całkowitych.
W porównaniu z algorytmem DDA DDA ma następujące problemy:
• Pikselowana linia może być daleka od oczekiwanego nagromadzenia błędów zaokrąglania.
• Wymagany jest czas na operacje zaokrąglania i arytmetykę zmiennoprzecinkową.

Polecane artykuły

Jest to przewodnik po algorytmie rysowania linii. Tutaj omawiamy algorytm rysowania linii wraz z różnymi przykładami. Możesz także zapoznać się z następującymi artykułami, aby dowiedzieć się więcej -

  1. Algorytmy uczenia maszynowego
  2. Algorytm SVM
  3. Prosta regresja liniowa
  4. Regresja wielowymiarowa
  5. Najlepsze porównanie regresji liniowej z regresją logistyczną

Kategoria:

Big Data