Մասնակից:Skhachatryan/sandbox

Բրեզենհեմի ալգորիթմ

Ալգորիթմի կիրառումը

Բրեզենհեմի ալգորիթմ

Բրեզենհեմի ալգորիթմ (անգլ.՝ Bresenham's algorithm) ― հնագույն ալգորիթմներից է համակարգչային գրաֆիկայում։ Որոշում է պատկերացանցում երկու կետերը միացնող ամենակարճ ճանապարհը։ Այն մշակվել է 1962 թվականին, IBM ընկերությունում, Ջեկ Է․ Բրեզենհեմի կողմից։ Մասնավորապես այն կիրառվում է համակարգչի էկրանին գծեր նկարելու համար։

Ալգորիթմ

Գիծը գծվում է երկու կետերի միջև - $(x_{0},y_{0})$ и $(x_{1},y_{1})$, որտեղ տրված են սյունը ($y$) և տողը($x$), վերջիններս աճում են դեպի ներքև և աջ( (0,0) սկզբնակետը կլինի ամենավերև և ամենաաջ կետը )։ Սկզբում ենթադրենք, որ գիծը ուղղված է դեպի ներքև և աջ, ինչպես նաև $(x_{1}-x_{0})>(y_{1}-y_{0})$ (այսինքն՝ գիծը հորիզոնական ուղղի հետ կազմում է 45°֊ից փոքր անկյուն): Մեր խնդիրն է՝ գտնել այն կետի x և y ֊ը, որն ամենամոտը կլինի ուղղին։

Երկու կետերի միջև ընկած գծի հավասարումը

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

Քանի որ $(x_{1}-x_{0})>(y_{1}-y_{0})$, ապա անհրաժեշտ է դիտարկել x-երը՝ գտնելու համար y֊երը։ y֊ը գտնելու համար անհրաժեշտ է կլորացնել հետևյալ բանաձևից ստացված թիվը (դեպի ավելի փոքր՝ ամբողջ թիվը)։

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

Սակայն անհրաժեշտություն չկա գտնել թվի բացարձակ արժեքը, քանի որ բավական է նկատել, որ y֊ը իր արժեքը սկսում է փոխել y0֊ից սկսած։ Ամեն քայլում ընթացիկ x֊ին գումարվում է 1 և արդյունքը բազմապատկվում անկյունային գործակցով, այնուհետեվ գումարվում y0-ն: Մեր դեպքում անկյունային գործակիցը բացասական թիվ է (այն հաստատուն է, հետեևաբար կարելի է նախապես հաշվել այն։)։

$a={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}},$

Ամեն քայլում կատարվում է հետևյալ երկու գործողություններից որևե մեկը՝

• y֊ը մնում է նույնը
• y-ը փոքրանում 1֊ով

Գործողությունը պարզելու համար հարկավոր է հետևել շեղմանը, որը ընթացիկ x-ի նկատմամբ y-ի և ընթացիկ y֊ի հեռավորությունն է։ Ամեն քայլում x-ը մեծացնելով 1֊ով, շեղումը մեծացնում ենք անկյունային գործակցով։ Եթե շեղումը մեծ է 0.5֊ից, ապա գիծը ավելի մոտ է հաջորդ y-ին, հետևաբար y֊ը փոխում ենք մեկով, հակառակ դեպքում թողնում ենք նույնը՝

Հետևյալ օրինակում plot(x,y) ներկում է պիկսելը, sign(T) վերադարձնում է T֊ի նշանը, abs վերադարձնում է թվի բացարձակ արժեքը:

Նկարում է գիծը՝ (0,1)֊ից (6,4) կետը

  function line(x0, x1, y0, y1)
     real deltax := x1 - x0
     real deltay := y1 - y0
     real error := 0
     real deltaerr := abs (deltay / deltax)    // Ենթադրենք deltax != 0 (գիծը ուղղահայաց չէ),
           // կարևոր պայման է, որ deltaerr փոփոխականը կարողանա ընդունել կոտորակային թվեր
     int y := y0
     for x from x0 to x1
         plot(x,y)
         error := error + deltaerr
         while error ≥ 0.5 then
             plot(x, y)
             y := y + sign(y1 - y0)
             error := error - 1.0

Այս լուծման բացասական կողմերից մեկն այն է, որ այնպիսի փոփոխականների հետ, ինչպիսին են՝ deltaerr֊ը և error֊ը, համակարգիչները համեմատաբար ավելի դանդաղ են աշխատում։ Այս հարցը հեշտությամբ լուծվում է բոլոր իրական թվերը բազմապատկելով deltax֊ով։ Իրական թվերից վերջնականապես ազատվելու համար՝ error >= 0.5 * deltaerr -ը փոխարինում ենք 2 * error >= deltaerr ֊ով: Արդյունքում ստանում ենք հետևյալ լուծումը՝

  function line(x0, x1, y0, y1)
     int deltax := abs(x1 - x0)
     int deltay := abs(y1 - y0)
     int error := 0
     int deltaerr := deltay
     int y := y0
     for x from x0 to x1
         plot(x,y)
         error := error + deltaerr
         if 2 * error >= deltax
             y := y - 1
             error := error - deltax

Ամբողջ թիվը երկուսով բազմապատկելու համար բավական է կատարել ձախ բիթային տեղաշարժ։ Սակայն, եթե թիվը բացասական է, ապա վերջին բիթը կկորցնենք՝ արդյունքում կորցնելով նշանի բիթը։ Դրա համար օգտագործվում են լրացում և շրջում բիթային գործողությունները։