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

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

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

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

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

.

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

Ամեն քայլում կատարվում է հետևյալ երկու գործողություններից որևէ մեկը՝
 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

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

Երկրաչափական ալգորիթմներ