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

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

## Ալգորիթմ
Գիծը գծվում է երկու կետերի միջև - (x_0, y_0) և (x_1, y_1), որտեղ տրված են սյունը (x) և տողը(y), վերջիններս աճում են դեպի ներքև և աջ( (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` վերադարձնում է թվի բացարձակ արժեքը։
300px|thumb|Նկարում է գիծը՝ (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

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

Կատեգորիա:Երկրաչափական ալգորիթմներ
Կատեգորիա:Համակարգչային գրաֆիկա
Կատեգորիա:Ալգորիթմներ
Կատեգորիա:Տվյալների վիզուալացում