Bresenhams algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 30. maj 2019; checks kræver 13 redigeringer .

Bresenhams linjealgoritme er en algoritme , der bestemmer, hvilke punkter i et todimensionalt raster, der skal skygges for at få en tæt tilnærmelse af en ret linje mellem to givne punkter . Dette er en af de ældste algoritmer inden for computergrafik - den blev udviklet af Jack Elton Bresenham hos IBM i 1962 . Algoritmen er meget brugt, især til at tegne streger på en computerskærm. Der er en generalisering af Bresenhams algoritme til at konstruere 2. ordens kurver.

Algoritme

Segmentet tegnes mellem to punkter - og , hvor disse par angiver henholdsvis en kolonne og en række, hvis tal stiger til højre og ned. Først vil vi antage, at vores linje går til højre og ned, og den vandrette afstand overstiger den lodrette , det vil sige, at linjens hældning fra vandret er mindre end 45 °. Vores mål er for hver kolonne x mellem og at bestemme hvilken række y der er tættest på linjen og tegne en prik . $(x_0, y_0)$ $(x_{1},y_{1})$ $x_{1}-x_{0}$ $å_{1}-å_{0}$ $x_{0}$ $x_{1}$ $(x, y)$

Den generelle formel for en linje mellem to punkter er:

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

Da vi kender kolonnen , fås rækken ved at afrunde følgende værdi til et heltal: $x$ $y$

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

Det er dog ikke nødvendigt at beregne den nøjagtige værdi af dette udtryk. Det er nok at bemærke, at fald fra og for hvert trin tilføjer vi til et og tilføjer hældningsværdien (i vores tilfælde vil hældningsværdien være et negativt tal): $y$ $y_0$ $x$ $y$

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

som kan beregnes på forhånd. Desuden gør vi ved hvert trin en af to ting: enten beholde den samme y eller reducere den med 1.

Hvilken af de to der skal vælges kan afgøres ved at holde styr på fejlværdien , hvilket betyder den lodrette afstand mellem den aktuelle y- værdi og den nøjagtige y- værdi for den aktuelle x . Når vi øger x , øger vi fejlværdien med mængden af hældning s givet ovenfor. Hvis fejlen er større end 1,0, kommer linjen tættere på den næste y , så vi øger y med 1,0, mens vi mindsker fejlværdien med 1,0. I implementeringen af algoritmen nedenfor plot(x,y)tegner den et punkt og absreturnerer den absolutte værdi af tallet:

funktionslinje ( int x0, int x1, int y0, int y1) int deltax := abs(x1 - x0) int deltay := abs(y1 - y0) reel fejl := 0 reel deltafejl := (deltay + 1) / (deltax + 1) int y := y0 int diry := y1 - y0 if diry > 0 beskidt := 1 hvis beskidt < 0 beskidt := -1 for x fra x0 til x1 plot(x,y) fejl := fejl + deltaerr hvis fejl >= 1.0 y := y + beskidt fejl := fejl - 1.0

Problemet med denne tilgang er, at med rigtige værdier, såsom errorog deltaerr, er computere relativt langsomme. Derudover er det i flydende kommaberegninger, på grund af begrænsningerne forbundet med repræsentationen af reelle tal, umuligt at opnå nøjagtige værdier ved opdeling. Dette fører til det faktum, at der i beregningsprocessen er en ophobning af fejl og kan føre til uønskede resultater. Af disse grunde er det bedre kun at arbejde med heltal. Dette kan gøres ved at gange alle reelle værdier brugt med ( deltax + 1). Vi får følgende kode:

funktionslinje ( int x0, int x1, int y0, int y1) int deltax := abs(x1 - x0) int deltay := abs(y1 - y0) int fejl := 0 int deltaerr := (deltay + 1) int y := y0 int diry := y1 - y0 if diry > 0 beskidt := 1 hvis beskidt < 0 beskidt := -1 for x fra x0 til x1 plot(x,y) fejl := fejl + deltaerr hvis fejl >= (deltax + 1) y := y + beskidt fejl := fejl - (deltax + 1)

Behovet for at tilføje en til deltax og deltay skyldes, at funktionen skal tegne en linje fra punktet (x0, y0) til punktet (x1, y1) inklusive! Nu kan vi hurtigt tegne ret-ned linjer med en hældning mindre end 1. Det er tilbage at udvide algoritmen til at tegne i alle retninger. Dette opnås gennem spejlrefleksioner, det vil sige ved at ændre tegnet (et trin på 1 erstattes af −1), ved at udveksle x- og y -variabler og ved at udveksle koordinaterne for begyndelsen af segmentet med koordinaterne for enden .

Tegne cirkler

Der er også Bresenhams algoritme til at tegne cirkler. Det ligner i konstruktionsmetoden at tegne en linje. I denne algoritme konstrueres en cirkelbue for den første kvadrant, og koordinaterne for cirkelpunkterne for de resterende kvadranter opnås symmetrisk. Ved hvert trin i algoritmen tages der hensyn til tre pixels, og den bedst egnede vælges blandt dem ved at sammenligne afstandene fra centrum til den valgte pixel med cirklens radius.

// R - radius, X1, Y1 - koordinater af centrum int x := 0 int y := R int delta := 1 - 2 * R int fejl := 0 mens (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) fejl := 2 * (delta + y) - 1 if ((delta < 0) && (fejl <= 0)) delta += 2 * ++x + 1 fortsæt hvis ((delta > 0) && (fejl > 0)) delta -= 2 * --y + 1 Blive ved delta += 2 * (++x - --y)

Litteratur

Rogers D. Algorithmic Foundations of Computer Graphics . - M . : Mir, 1989. - S. 54 -63. — ISBN 5-03-000476-9 .
Schildt G. "C" for professionelle programmører. - M. , 1989.

Bresenhams algoritme

Algoritme

Tegne cirkler

Litteratur

Se også