Bresenhams algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 30 maj 2019; kontroller kräver 13 redigeringar .

Bresenhams linjealgoritm är en algoritm som bestämmer vilka punkter i ett tvådimensionellt raster som behöver skuggas för att få en nära approximation av en rät linje mellan två givna punkter . Detta är en av de äldsta algoritmerna inom datorgrafik - den utvecklades av Jack Elton Bresenham på IBM 1962 . Algoritmen används i stor utsträckning, särskilt för att rita linjer på en datorskärm. Det finns en generalisering av Bresenhams algoritm för att konstruera andra ordningens kurvor.

Algoritm

Segmentet ritas mellan två punkter - och , där dessa par indikerar en kolumn respektive en rad, vars nummer ökar till höger och nedåt. Först antar vi att vår linje går åt höger och nedåt, och att det horisontella avståndet överstiger det vertikala , det vill säga att linjens lutning från horisontalen är mindre än 45 °. Vårt mål är för varje kolumn x mellan och att bestämma vilken rad y som är närmast linjen och rita en prick . $(x_0, y_0)$ $(x_{1},y_{1})$ $x_{1}-x_{0}$ $å_{1}-å_{0}$ $x_{0}$ $x_{1}$ $(x, y)$

Den allmänna formeln för en linje mellan två punkter är:

y-y_{0}={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0}).

Eftersom vi känner till kolumnen erhålls raden genom att avrunda följande värde till ett heltal: $x$ $y$

y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}.

Det finns dock inget behov av att beräkna det exakta värdet av detta uttryck. Det räcker med att notera att minskningar från och för varje steg lägger vi till ett och lägger till lutningsvärdet (i vårt fall kommer lutningsvärdet att vara ett negativt tal): $y$ $y_0$ $x$ $y$

s={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}},

som kan beräknas i förväg. Dessutom, vid varje steg gör vi en av två saker: antingen behålla samma y eller minska den med 1.

Vilken av de två som ska väljas kan avgöras genom att hålla reda på felvärdet , vilket innebär det vertikala avståndet mellan det aktuella y -värdet och det exakta y -värdet för det aktuella x . När vi ökar x ökar vi felvärdet med mängden lutning s som anges ovan. Om felet är större än 1,0 kommer linjen närmare nästa y , så vi ökar y med 1,0 samtidigt som vi minskar felvärdet med 1,0. I implementeringen av algoritmen nedan plot(x,y)ritar den en punkt och absreturnerar talets absoluta värde :

funktionsrad ( int x0, int x1, int y0, int y1) int deltax := abs(x1 - x0) int deltay := abs(y1 - y0) verkligt fel := 0 verkligt deltafel := (deltay + 1) / (deltax + 1) int y := y0 int diry := y1 - y0 om diry > 0 smutsig := 1 om smutsigt < 0 smutsig := -1 för x från x0 till x1 plot(x,y) fel := fel + deltafel om fel >= 1.0 y := y + diry fel := fel - 1.0

Problemet med detta tillvägagångssätt är att med verkliga värden, som erroroch deltaerr, är datorer relativt långsamma. Dessutom, i flyttalsberäkningar, på grund av begränsningarna förknippade med representationen av reella tal, är det omöjligt att erhålla exakta värden vid division. Detta leder till det faktum att det i beräkningsprocessen finns en ansamling av fel och kan leda till oönskade resultat. Av dessa skäl är det bättre att bara arbeta med heltal. Detta kan göras genom att multiplicera alla verkliga värden som används med ( deltax + 1). Vi får följande kod:

funktionsrad ( int x0, int x1, int y0, int y1) int deltax := abs(x1 - x0) int deltay := abs(y1 - y0) int fel := 0 int deltaerr := (deltay + 1) int y := y0 int diry := y1 - y0 om diry > 0 smutsig := 1 om smutsigt < 0 smutsig := -1 för x från x0 till x1 plot(x,y) fel := fel + deltafel om fel >= (deltax + 1) y := y + diry fel := fel - (deltax + 1)

Behovet av att lägga till en till deltax och deltay beror på att funktionen måste dra en linje från punkten (x0, y0) till punkten (x1, y1) inklusive! Nu kan vi snabbt rita rakt ner linjer med en lutning mindre än 1. Det återstår att utöka algoritmen till att rita i alla riktningar. Detta uppnås genom spegelreflektioner, det vill säga genom att ändra tecknet (ett steg på 1 ersätts med −1), genom att byta x- och y -variabler och genom att byta ut koordinaterna för början av segmentet med koordinaterna för slutet .

Rita cirklar

Det finns även Bresenhams algoritm för att rita cirklar. Det liknar i konstruktionsmetoden att rita en linje. I denna algoritm konstrueras en cirkelbåge för den första kvadranten, och koordinaterna för cirkelpunkterna för de återstående kvadranterna erhålls symmetriskt. Vid varje steg i algoritmen övervägs tre pixlar, och den mest lämpliga väljs bland dem genom att jämföra avstånden från mitten till den valda pixeln med cirkelns radie.

// R - radie, X1, Y1 - koordinater för centrum int x := 0 int y := R int delta := 1 - 2 * R int fel := 0 medan (y >= x) drawpixel(X1 + x, Y1 + y) drawpixel(X1 + x, Y1 - y) drawpixel(X1 - x, Y1 + y) drawpixel(X1 - x, Y1 - y) drawpixel(X1 + y, Y1 + x) drawpixel(X1 + y, Y1 - x) drawpixel(X1 - y, Y1 + x) drawpixel(X1 - y, Y1 - x) fel := 2 * (delta + y) - 1 if ((delta < 0) && (fel <= 0)) delta += 2 * ++x + 1 fortsätt om ((delta > 0) && (fel > 0)) delta -= 2 * --y + 1 Fortsätta delta += 2 * (++x - --y)

Litteratur

Rogers D. Algoritmiska grunder för datorgrafik . - M .: Mir, 1989. - S. 54 -63. — ISBN 5-03-000476-9 .
Schildt G. "C" för professionella programmerare. - M. , 1989.

Bresenhams algoritm

Algoritm

Rita cirklar

Litteratur

Se även