ბრეზენჰემის ალგორითმი: განსხვავება გადახედვებს შორის
| [შეუმოწმებელი ვერსია] | [შეუმოწმებელი ვერსია] |
შიგთავსი ამოიშალა შიგთავსი დაემატა
No edit summary |
No edit summary |
||
ხაზი 1:
[[image:Bresenham_line.png|right|300px|Illustration de l'algorithme de Bresenham]]
'''ბრეზენჰამის სეგმენტის აგების ალგორითმი''' არის [[ჯეკ ე. ბრეზენჰამი|ბრეზენჰამის]] მიერ ჩამოყალიბებული [[ალგორითმი]] 1962 წელს, მაშინ როცა ის მუშაობდა [[IBM]]-ის ინფორმატიკის ლაბორატორიაში და ცდილობდა მოეძებნა მეთოდი რომლითაც შეძლებდა ტექსტის კურსორის მართვას. ეს ალგორითმი წარმოდგენილი იყო [[1963]] წლის [[Association for Computing Machinery|ACM]]-ის კონვენციაზე. შემდეგ კი გამოქვეყნდა 1965 წლის ჟურნალ ''IBM Systems Journal''.
ალგორითმი განსაზღვრავს დასახული გეგმის პუნქტებს, რომლებიც უნდა დაიხაზოს რათა შეადგინოს სეგმენტის მარჯვენა ნაწილის მიახლოება მოცემულ ორ პუნქტს შორის. ეს ალგორითმი ხშირად გამოიყენება კომპიუტერის ეკრანის მარჯვენა მხარეზე სურათის ხაზის გასავლებად ან გამოსახულების ასაგებად. ის განიხილება როგორც ერთ-ერთი პირველად აღმოჩენილი ალგორითმი [[გამოსახულების სინთეზი]]-ს სფეროში.
Line 8 ⟶ 9:
==პირველი ბაიტში შემავალი მონაცებესი საბაზო ალგორითმის ახსნა==
[[Image:Bresenham.png|right|300px|thumb|Illustration du résultat de l’algorithme de tracé de segment de Bresenham.]]
მონაკვეთი იხატება ორ წერტილს შორის (''x''<sub>1</sub>, ''y''<sub>1</sub>) და (''x''<sub>2</sub>, ''y''<sub>2</sub>), სადაც ამ წყვილში მითითებულია სვეტი და სტრიქონი, შესაბამისად, რომელთა ნომრები იზრდება მარჯვნივ და ქვევით. დავუშვათ რომ ჩვენი ხაზი მიდის ქვევით და მარჯვნივ, ამასთან ჰორიზონტალური მანძილი ''x''<sub>2</sub>-''x''<sub>1</sub> აღემატება ვერტიკალურს ''y''<sub>2</sub>-''y''<sub>1</sub>, ხაზის დახრა ჰორიზონტალურად ნაკლებია 45°. ჩვენი მიზანია ყოველი x კოლონისთვის რომელიც მოთავსებულია x0 და x1 შორის განვსაზღვროთ რომელი y სვეტია ყველაზე ახლოს ხაზთან, და დავხატოთ (x,y) წერტილი.
Line 132 ⟶ 134:
''// Le pixel final (x<sub>1</sub>, y<sub>1</sub>) n’est '''pas''' tracé.''
'''fin procédure''' ;
ეს ალგორითმი ოპტიმალურია და საკმარისია იმისათის რომ დავხაზოთ ნებისმიერი დახრილი და დიაგონალური ჰორიზონტალური ვექტორი პირველ ბაიტში, ზრდად სვეტებსა და კოლონებში. ავღნიშნოთ რომ თუ პროგრამირების ენა საშუალებას გვაძლევს ორი ლოკალური გამოცხადებული ცვლადი ''x'' და ''y'' შეიძლება ჩანაცვლებული იყვნენ ''x''<sub>1</sub> და ''y''<sub>1</sub> ცვლადების პარამეტრების გამოყენებით. ეს შემთხვევა ზევითაა განხილული.
და მაინც უნდა აღინიშნოს რომ ზემოთ ნახსენებ ალგორითმში, ''e''-ს ტესტირებული ნიშანი უდრიდეს ან არ უდრიდეს ნულს. თუ ვირჩევთ დიაგონალურ გადაადგილებას მომდევნოდ ორი პუნქტი ყოველთვის მიღებული იქნება დიაგონალური გადაადგილებით; ხოლო თუ ვირჩევთ ჰორიზონტალურ გადაადგილებას, მომდევნო ორი პუნქტი ყოველთვის მიღებული იქნება ჰორიზონტალური გადაადგილებით.
== განზოგადებული ოპტიმიზირებული ალგორითმი ==
საბაზო ალგორითმის განზოგადება მიღებულია, ნებისმიერი მიმართულებით გავლებული ვექტორების მიერ შექმნილი წირის მარტივი სიმეტრიით.
აქ მოყვანილი ალგორითმი განვითარებულია და ოპტიმიზირებულია 8 ბაიტში. იმისთვის რომ დავრწმუნდეთ რომ ერთი და იგივე გამოსახულების ელემენტები ყოველთვის აგებული იქნება ორი ერთი და იგივე მაგრამ საპირისპირო მიმართულების მქონე ვექტორისთვის, შევაბრუნოთ სასაზღვრო პირობები, სადაც დიაგონალური გადაადგილება პირდაპირი გადაადგილების ტოლია, ამოვირჩიოთ დიაგონალი როცა ვექტორი უფრო მეტად ორიენტირებულია მარცხნივ(კლებადი აბსცისისკენ) ვიდრე მაჯვნივ(ზრდადი აბსცისისკენ), როგორც აქ მოყვანილ შემთხვევაში:
'''procédure''' tracerSegment('''entier''' ''x''<sub>1</sub>, '''entier''' ''y''<sub>1</sub>, '''entier''' ''x''<sub>2</sub>, '''entier''' ''y''<sub>2</sub>) '''est'''
'''déclarer''' '''entier''' ''dx'', ''dy'';
'''si''' (''dx'' ← ''x<sub>2</sub>'' - ''x<sub>1</sub>'') ≠ 0 '''alors'''
'''si''' ''dx'' > 0 '''alors'''
'''si''' (''dy'' ← ''y<sub>2</sub>'' - ''y<sub>1</sub>'') ≠ 0 '''alors'''
'''si''' ''dy'' > 0 '''alors'''
''// vecteur oblique dans le 1er quadran''
'''si''' ''dx'' ≥ ''dy'' '''alors'''
''// vecteur diagonal ou oblique proche de l’horizontale, dans le 1er octant''
'''déclarer''' '''entier''' ''e'' ;
''dx'' ← (e ← ''dx'') × 2 ; ''dy'' ← ''dy'' × 2 ; ''// e არის დადებითი''
'''boucler sans fin''' ''// ჰორიზონტალური გადაადგილება''
tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
'''interrompre boucle si''' (''x''<sub>1</sub> ← ''x''<sub>1</sub> + 1) = ''x<sub>2</sub>'' ;
'''si''' (''e'' ← ''e'' - ''dy'') < 0 '''alors'''
''y''<sub>1</sub> ← ''y''<sub>1</sub> + 1 ; ''// დიაგონალური გადაადგილება'
''e'' ← ''e'' + ''dx'' ;
'''fin si''' ;
'''fin boucle''' ;
'''sinon'''
''// vecteur oblique proche de la verticale, dans le 2nd octant''
'''déclarer''' '''entier''' ''e'' ;
''dy'' ← (e ← ''dy'') × 2 ; ''dx'' ← ''dx'' × 2 ; ''// e არის დადებითი''
'''boucler sans fin''' ''// ვერტიკალური გადაადგილება''
tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
'''interrompre boucle si''' (''y''<sub>1</sub> ← ''y''<sub>1</sub> + 1) = ''y<sub>2</sub>'' ;
'''si''' (''e'' ← ''e'' - ''dx'') < 0 '''alors'''
''x''<sub>1</sub> ← ''x''<sub>1</sub> + 1 ; ''// დიაგონალური გადაადგილება''
''e'' ← ''e'' + ''dy'' ;
'''fin si''' ;
'''fin boucle''' ;
'''fin si''' ;
'''sinon''' ''// dy < 0 (et dx > 0)''
''// vecteur oblique dans le 4e cadran''
'''si''' ''dx'' ≥ -''dy'' '''alors'''
''// vecteur diagonal ou oblique proche de l’horizontale, dans le 8e octant''
'''déclarer''' '''entier''' ''e'' ;
''dx'' ← (e ← ''dx'') × 2 ; ''dy'' ← ''dy'' × 2 ; ''// e არის დადებითი''
'''boucler sans fin''' ''// ჰორიზონტალური გადაადგილება''
tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
'''interrompre boucle si''' (''x''<sub>1</sub> ← ''x''<sub>1</sub> + 1) = ''x<sub>2</sub>'' ;
'''si''' (''e'' ← ''e'' + ''dy'') < 0 '''alors'''
''y''<sub>1</sub> ← ''y''<sub>1</sub> - 1 ; ''// დიაგონალური გადაადგილება''
''e'' ← ''e'' + ''dx'' ;
'''fin si''' ;
'''fin boucle''' ;
'''sinon''' ''// vecteur oblique proche de la verticale, dans le 7e octant''
'''déclarer''' '''entier''' ''e'' ;
''dy'' ← (e ← ''dy'') × 2 ; ''dx'' ← ''dx'' × 2 ; ''// e არის უარყოფიტი''
'''boucler sans fin''' ''// ვერტიკალური გადაადგილება''
tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
'''interrompre boucle si''' (''y''<sub>1</sub> ← ''y''<sub>1</sub> - 1) = ''y<sub>2</sub>'' ;
'''si''' (''e'' ← ''e'' + ''dx'') > 0 '''alors'''
''x''<sub>1</sub> ← ''x''<sub>1</sub> + 1 ; ''// დიაგონალური გადაადგილება''
''e'' ← ''e'' + ''dy'' ;
'''fin si''' ;
'''fin boucle''' ;
'''fin si''' ;
'''fin si''' ;
'''sinon''' ''// dy = 0 (et dx > 0)''
''// vecteur horizontal vers la droite''
'''répéter'''
tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
'''jusqu’à ce que''' (''x''<sub>1</sub> ← ''x''<sub>1</sub> + 1) = ''x<sub>2</sub>'' ;
'''fin si''' ;
'''sinon''' ''// dx < 0''
'''si''' (''dy'' ← ''y<sub>2</sub>'' - ''y<sub>1</sub>'') ≠ 0 '''alors'''
'''si''' ''dy'' > 0 '''alors'''
''// vecteur oblique dans le 2nd quadran''
'''si''' -''dx'' ≥ ''dy'' '''alors'''
''// vecteur diagonal ou oblique proche de l’horizontale, dans le 4e octant''
'''déclarer''' '''entier''' ''e'' ;
''dx'' ← (e ← ''dx'') × 2 ; ''dy'' ← ''dy'' × 2 ; ''// e არის უარყოფითი''
'''boucler sans fin''' ''// ჰორიზონტალური გადაადგილება''
tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
'''interrompre boucle si''' (''x''<sub>1</sub> ← ''x''<sub>1</sub> - 1) = ''x<sub>2</sub>'' ;
'''si''' (''e'' ← ''e'' + ''dy'') ≥ 0 '''alors'''
''y''<sub>1</sub> ← ''y''<sub>1</sub> + 1 ; ''// დიაგონალური გადაადგილება''
''e'' ← ''e'' + ''dx'' ;
'''fin si''' ;
'''fin boucle''' ;
'''sinon'''
''// vecteur oblique proche de la verticale, dans le 3e octant''
'''déclarer''' '''entier''' ''e'' ;
''dy'' ← (e ← ''dy'') × 2 ; ''dx'' ← ''dx'' × 2 ; ''// e არის დადებითი''
'''boucler sans fin''' ''// ვერტიკალური გადაადგილება''
tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
'''interrompre boucle si''' (''y''<sub>1</sub> ← ''y''<sub>1</sub> + 1) = ''y<sub>2</sub>'' ;
'''si''' (''e'' ← ''e'' + ''dx'') ≤ 0 '''alors'''
''x''<sub>1</sub> ← ''x''<sub>1</sub> - 1 ; ''// დიაგონალური გადაადგილება''
''e'' ← ''e'' + ''dy'' ;
'''fin si''' ;
'''fin boucle''' ;
'''fin si''' ;
'''sinon''' ''// dy < 0 (et dx < 0)''
''// vecteur oblique dans le 3e cadran''
'''si''' ''dx'' ≤ ''dy'' '''alors'''
''// vecteur diagonal ou oblique proche de l’horizontale, dans le 5e octant''
'''déclarer''' '''entier''' ''e'' ;
''dx'' ← (e ← ''dx'') × 2 ; ''dy'' ← ''dy'' × 2 ; ''// e არის უარყოფითი''
'''boucler sans fin''' ''// ჰორიზონტალური გადაადგილება''
tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
'''interrompre boucle si''' (''x''<sub>1</sub> ← ''x''<sub>1</sub> - 1) = ''x<sub>2</sub>'' ;
'''si''' (''e'' ← ''e'' - ''dy'') ≥ 0 '''alors'''
''y''<sub>1</sub> ← ''y''<sub>1</sub> - 1 ; ''// დიაგონალური გადაადგილება''
''e'' ← ''e'' + ''dx'' ;
'''fin si''' ;
'''fin boucle''' ;
'''sinon''' ''// vecteur oblique proche de la verticale, dans le 6e octant''
'''déclarer''' '''entier''' ''e'' ;
''dy'' ← (e ← ''dy'') × 2 ; ''dx'' ← ''dx'' × 2 ; ''// e არის უარყოფითი''
'''boucler sans fin''' ''// ვერტიკალური გადაადგილება''
tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
'''interrompre boucle si''' (''y''<sub>1</sub> ← ''y''<sub>1</sub> - 1) = ''y<sub>2</sub>'' ;
'''si''' (''e'' ← ''e'' - ''dx'') ≥ 0 '''alors'''
''x''<sub>1</sub> ← ''x''<sub>1</sub> - 1 ; ''// დიაგონალური გადაადგილება''
''e'' ← ''e'' + ''dy'' ;
'''fin si''' ;
'''fin boucle''' ;
'''fin si''' ;
'''fin si''' ;
'''sinon''' ''// dy = 0 (et dx < 0)''
''// vecteur horizontal vers la gauche''
'''répéter'''
tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
'''jusqu’à ce que''' (''x''<sub>1</sub> ← ''x''<sub>1</sub> - 1) = ''x<sub>2</sub>'' ;
'''fin si''' ;
'''fin si''' ;
'''sinon''' ''// dx = 0''
'''si''' (''dy'' ← ''y''<sub>2</sub> - ''y''<sub>1</sub>) ≠ 0 '''alors'''
'''si''' ''dy'' > 0 '''alors'''
''// vecteur vertical croissant''
'''répéter'''
tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
'''jusqu’à ce que''' (''y''<sub>1</sub> ← ''y''<sub>1</sub> + 1) = ''y<sub>2</sub>'' ;
'''sinon''' ''// dy < 0 (et dx = 0)''
''// vecteur vertical décroissant''
'''répéter'''
tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
'''jusqu’à ce que''' (''y''<sub>1</sub> ← ''y''<sub>1</sub> - 1) = ''y<sub>2</sub>'' ;
'''fin si''' ;
'''fin si''' ;
'''fin si''' ;
''// le pixel final (x<sub>2</sub>, y<sub>2</sub>) n’est pas tracé.''
'''fin procédure''' ;
| |||