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

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


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

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

  
    
      
        y
        =
        
          
            
              
                y
                
                  1
                
              
              −
              
                y
                
                  0
                
              
            
            
              
                x
                
                  1
                
              
              −
              
                x
                
                  0
                
              
            
          
        
        (
        x
        −
        
          x
          
            0
          
        
        )
        +
        
          y
          
            0
          
        
      
    
    {\displaystyle y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}}
  .Սակայն անհրաժեշտություն չկա գտնել թվի բացարձակ արժեքը, քանի որ բավական է նկատել, որ y֊ը իր արժեքը սկսում է փոխել y0֊ից սկսած։ Ամեն քայլում ընթացիկ x֊ին գումարվում է 1 և արդյունքը բազմապատկվում անկյունային գործակցով, այնուհետև գումարվում y0-ն։
Մեր դեպքում անկյունային գործակիցը բացասական թիվ է (այն հաստատուն է, հետեևաբար կարելի է նախապես հաշվել այն։)։

  
    
      
        a
        =
        
          
            
              
                y
                
                  1
                
              
              −
              
                y
                
                  0
                
              
            
            
              
                x
                
                  1
                
              
              −
              
                x
                
                  0
                
              
            
          
        
        ,
      
    
    {\displaystyle 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 վերադարձնում է թվի բացարձակ արժեքը։

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

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