ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Загальний метод Брезенхема побудови вiдрiзка.

Загрузка...

var Xs,Ys,Xf,Yf : integer;

function Sign(X:integer):integer;

begin {Sign}

if X>0 then Sign:=1;

if X=0 then Sign:=0;

if X<0 then Sign:=-1;

end; {Sign}

procedure RastrBresLine(Xs,Ys,Xf,Yf,Color:integer);

var i,Dx,Dy,De,s1,s2,x,y,Temp,Change: integer;

begin {RastrBresLine}

// початковi установки

x:=Xs; y:=Ys;

Dx:=abs(Xf-Xs); Dy:=abs(Yf-Ys);

s1:=Sign(Xf-Xs); s2:=Sign(Yf-Ys);

// обмiн Dx и Dy у залежностi вiд коеф. нахилу вiдрiзка

if Dy > Dx

then begin

Temp:=Dx;Dx:=Dy;Dy:=Temp;Change:=1;

end

else Change:=0;

// уставлення нев'язки De з поправкою на пiвпiкселя

De:=2*Dy-Dx;

for i:=1 to Dx do

begin {for i}

Form1.Canvas.Pixels[x,y]:=Color;

while De>=0 do

begin

if Change=1 then x:=x+s1 else y:=y+s2; De:=De-2*Dx;

end;

if Change=1 then y:=y+s2 else x:=x+s1; De:=De+2*Dy;

end; {for i}

end; {RastrBresLine}

 

procedure TForm1.Button1Click(Sender: TObject);

begin {TForm1.Button1Click}

Xs:=StrToInt(Edit1.Text); Ys:=StrToInt(Edit2.Text);

Xf:=StrToInt(Edit3.Text); Yf:=StrToInt(Edit4.Text);

RastrBresLine(Xs,Ys,Xf,Yf,clGreen);

end; {TForm1.Button1Click}

 

Зауваження 1Наведенi алгоритми Брезенхема породжують лiнiю вiдрiзка границi, яка є чотирьохзв'язною (див. Пiдроздiл 2.2.5). Тому алгоритми Брезенхема зручно використовувати для виведення вiдрiзкiв границi областi, внутрішню (або зовнiшню) частину якої потрiбно заповнити якимось кольором.

Зауваження 2Для виведення вiдрiзкiв у вікно форми мовою Object Pascal використовуються процедури Form1.Canvas.MoveTo(Xa,Ya) i Form1.Canvas.LineTo(Xb,Yb) (див.[9]). Для виведення окремих пiкселiв використовується процедура Form1.Canvas.Pixels[X,Y]. Вiдповiднi засоби у мовi програмування C++ див.[10, стор.64-65].

Реалiзацiю алгоритму Брезенхема мовою програмування C див. [4, стор.128-129] i [11, стор. 121-126], на асемблерi - [11, стор. 126-129].

 

Лiтература. [12], [4, Гл.6], [8, стор.100-101], [11, Часть III], [13, Разд. 0.2.3], [13, 0.13, Прил. 2].

 

2.1.3 Алгоритм Брезенхема креслення кола

У растр потрiбно розкладати не тiльки лiнiйнi, а й iншi, складнiші функцiї. Розкладання у растр конiчних перерiзiв, тобто кола, елiпса, параболи, гiперболи, розглядалося у значної кiлькостi робiт ([14], [15], [16], [17]). Найбiльшу увагу приділяли колу ([18], [19], [20], [21]).Найбiльш ефективний i нескладний алгоритм був запропонований Брезенхемом [22]. Для початку зауважимо, що можна генерувати тiльки одну восьму частину кола (наприклад, перший октант з кутом вiд 0 до 45 градусiв). Інші частини одержуємо послiдовними симетрiями (вiдносно прямої y=x , потім вiдносно прямої x=0 i нарештi вiдносно прямої y=0).Для побудови алгоритму розглянемо першу чверть (квадрант) кола з центром в початку координат. Зауважимо, що при початку роботи алгоритму з точки (0,R) i генерацiї точок кола за годинниковою стрiлкою у першому квадрантi y-координати згенерованих точок, є монотонно спадною функцією вiд аргументу x. Будемо вважати, що центр кола знаходиться у точцi (0,0) i радiус R>0 є величина цiла.

Для будь-якої точки кола при генеруваннi за напрямом стрiлки годинника iснує лише три можливостi обрати наступний пiксел, що наближатиме коло найлiпшим чином:

Рис.1. Вибiр пiкселiв у першому квадрантi

На рис.1. цi напрямки позначенi вiдповiдно mH, mD, і mV. Алгоритм вибирає той пiксел, для якого є найменшим квадрат вiдстанi мiж одним з цих пiкселiв i колом, тобто вибирає мiнiмум з наступних чисел

У околi точки (xi,yi) можливi лише п'ять типiв перетину кола з сіткою растра:

Випадок 1. Коло пройде мiж точками (xi+1,yi) i (xi+1,yi-1).

Випадок 2. Коло пройде мiж точками (xi+1,yi) i (xi+1,yi+1).

Випадок 3. Коло пройде мiж точками (xi,yi-1) i (xi+1,yi-1).

Випадок 4. Коло пройде мiж точками (xi-1,yi-1) i (xi, yi-1).

Випадок 5. Коло пройде через точку (xi+1,yi-1).

Позначимо через рiзницю мiж квадратами вiдстаней вiд центра кола до пiксела (xi+1,yi-1) i вiд центра кола до точки на колi, тобто .

Як у алгоритмi Брезенхема для вiдрiзка, бажано при обраннi нового пiксела використовувати лише знак похибки . Розглянемо алгоритм пiд цим кутом зору.

1. Випадок, коли <0.При <0 дiагональна точка (xi+1,yi-1) знаходиться всерединi кола, тобто маємо випадки 1 або 2. Звiсно, що потрiбно вибрати або пiксел (xi+1,yi), тобто mH, або пiксел (xi+1,yi-1), тобто mD.

Розглянемо спочатку випадок 1. Знайдемо рiзницю квадратiв вiдстаней від кола до пiкселiв у горизонтальному mH i дiагональному mD напрямках:

При <0 вiдстань вiд кола до дiагонального пiксела (величина mD) бiльшa нiж до горизонтального (величина mH). Тому

при 0 вибираємо mH (у точку (xi+1, yi)), інакше вибираємо mD ( у точку (xi+1, yi-1)) (3)

Зауважимо, що у випадку 1: (xi+1)2 +yi2-R2 0, (xi+1)2 +(yi-1)2-R2 0 тому що дiагональний пiксел (xi+1,yi-1) завжди лежить всерединi кола, а горизонтальний пiксел (xi+1,yi) - зовнi. Тому можна рахувати за формулою

= (x i +1)2 + y i 2 R 2 + (x i +1) 2+(y i - 1)2-R 2

=2(x i +1) 2 + 2 yi 2-12-2 R 2-2 y i -1=2 ( + yi)-1

У випадку 2 потрiбно вибрати горизонтальний пiксел (xi+1,yi) тому, що y є монотонно спадна функцiя вiд x. При цьому горизонтальний (xi+1,yi) i дiагональний (xi+1,yi-1) пiкселi лежать у серединi кола.

Тодi (xi + 1) 2+ y i 2 R 2 <0, (x i + 1) 2 + (y i - 1) 2 R 2<0 i

= - (x i + 1) 2 y i 2 + R 2 + (x i + 1) 2 + (y i - 1) 2 - R 2= - 2yi +1<0.

Тому дiє правило (3).

2. Випадок, коли >0. При >0 дiагональна точка (xi+1,yi-1) знаходиться зовнi кола, тобто одержуємо випадки 3 i 4 (потрiбно вибрати або пiксел (xi+1,yi-1), тобто mD, або пiксел (xi,yi-1), тобто mV). Знайдемо рiзницю квадратiв вiдстаней вiд кола до пiкселiв у дiагональному mD i вертикальному mV напрямках:

При '<0 вiдстань вiд кола до вертикального пiксела (xi, yi-1) бiльше нiж вiдстань до дiагонального (xi+1, yi-1) пiксела. Тому формулюємо наступне правило вибору

при 0 вибираємо mD ( у точку (x i+ 1, yi - 1)) інакше вибираємо mV (у точку (xi, yi-1)) (4)

 

Перевiрка компонент ' для випадку 3 дає (xi + 1) 2 + ( yi - 1) 2 R 2 0,

x i 2 + (y i + 1) 2 R 2 < 0 тому, що у цьому випадку дiагональний пiксел

(x i + 1 , y i - 1) лежить зовнi кола, а вертикальний пiксел (x i , yi - 1) -- у серединi кола. Звідси

’= (x i +1)2 + (y i - 1) 2 R 2 + x i 2+(y i - 1)2-R 2

=2(x i +1) 2 + 2( yi - 1)2 - 2 R 2+ (y i -1)2 – 2 xi - 1=2 ( + xi)-1

У випадку 4 потрiбно вибирати вертикальний пiксел (xi, yi-1) тому, що y є монотонно спадна функція вiд x. При цьому (xi + 1)2(yi -1)2 - R2>0,

xi2 + (yi - 1)2 - R2>0 тому, що обидва пiкселя знаходяться зовнi кола. Звiдси '>0, тобто дiє правило (4)

3. Випадок, коли =0. При =0 маємо випадок 5, тобто коли дiагональний пiксел (xi+1,yi-1) належить до кола. Перевiрка компонент виразу дає (xi+1)2+yi2-R2>0, (xi+1)2+(yi-1)2-R2=0.

Тому =(xi+1)2+yi2-R2>0 i вибираємо дiагональний пiксел (xi+1)+(yi-1)2-R2, що збiгається з правилом (3). Перевірка компонент виразу ' дає (xi+1)2+(yi-1)2-R2=0, xi2+(yi-1)2-R2=0, xi2+(yi-1)2-R2 0.

Тому '=(xi+1)2+(yi-1)2-R2>0 i вибираємо дiагональний пiксел (xi+1,yi-1), що збiгається з правилом (4).

Таким чином, випадок, коли =0 можна обробляти як за випадком, коли <0, так i за випадком, коли >0.

Знайдемо рекурентнi спiввiдношення для реалiзацiї крокiв алгоритму. Розглянемо рiзнi випадки.

Горизонтальний крок mH до пiкселя (xi+1,yi): xi+1=xi+1, yi+1=yi,

i+1=(xi+1 + 1) 2 + (yi+1 - 1) 2- R 2=xi+1 2 + 2xi+1 + 1 + (yi-1) 2 R 2=

= (xi+1) 2 + (y i-1)2 R 2 + 2xi+1 + 1= i + 2xi+1 + 1.

Дiагональний крок mD до пiкселя (xi+1,yi-1):xi+1=xi+1, yi+1=yi-1,

i+1=(xi+1 + 1) 2 + (yi+1 - 1) 2 R 2 = xi+1 2 + 2xi+1 + 1 + yi+12 - 2yi+1 + 1 – R 2 =

= (xi + 1)2 + (yi - 1)2R 2 + 2xi+1 - 2yi+1 + 2 = i + 2xi+1 - 2yi+1 + 2.

Вертикальний крок mV до пiкселя (xi, yi-1): xi+1 = xi, yi+1 = yi-1,

i+1 = (xi+1 + 1)2 + (yi+1 - 1)2R 2 = (xi + 1)2 + y2i+1 - 2yi+1 + 1 -R2=

= (xi + 1)2 + (yi - 1)2R 2 - 2yi+1 + 1 = i - 2yi+1 + 1.

Тепер ми можемо розглянути алгоритм Брезенхема побудови частини кола у першому квадрантi.

 

Загрузка...

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти