загрузка...
загрузка...
На головну

Sutherland - Cohen

Відсікання прямокутником.

II. Відсікання відрізка (clipping).

Лекція 2, частина 2

СПИСОК ЛІТЕРАТУРИ

[Bresenham, 1965]Bresenham J.E. Algorithm for Computer Control of a Digital Plotter // IBM System Journal.- 1965.- Vol.4.- pp. 25-30.

[Castle-Pitteway, 1987] Castle C.M., Pitteway L.V. An Efficient Structural Technique for Encoding "Best-fit" Straight Lines // The Computer Journal.- 1987.- Vol. 30, No. 2.

Завдання відсікання прямокутником виникає, як правило, через фізично кінцевих розмірів растра, на який відбувається висновок (приклад: дисплей комп'ютера)

Можливі підходи:

1) У функції зміни атрибутів пікселя перевіряти x і y на потрапляння в допустимі діапазони значень.

Неефективно, так як відбудеться занадто розрахунків для які не відображаються точок.

Класифікуємо всі крапки в залежності від їх положення по відношенню до відтинає прямим 1, 2, 3, 4: поставимо у відповідність кожній області 4-бітний код.


Мал. 1. Алгоритм Сазерленда-Кохена.

Встановимо ці біти наступним чином:

0 біт - якщо точка лежить лівіше прямої 1

1 біт - якщо точка лежить вище прямої 2

2 біт - якщо точка лежить правіше прямий 3

3 біт - якщо точка лежить нижче прямої 4

Тоді для відрізка ABна Рис. 1 будемо мати:

код A = 1001

код B = 0100


нехай A - Код точки - початку відрізка,

B - Код точки - кінця відрізка.

Можливі варіанти:

· A = B= 0000

Цей випадок означає, що обидві точки лежать всередині прямокутника (т. Е. Відсікання не потрібне)

· C = A & B ? 0

В цьому випадку точки лежать по одну сторону від будь-якої відтинає лінії (з зовнішньої її сторони), отже, малювати взагалі нічого не потрібно.

· В іншому випадку необхідно знаходити точки перетину з деякими з відтинають прямих (для прямих, які перетинає AB, Відповідний біт в A ^ Bвстановлений в 1), розбити наш відрізок знайденими точками перетину і потім застосувати той же аналіз кодів кінців вже для цих подотрезков. Один з можливих варіантів реалізації остаточного алгоритму наведено нижче:

алгоритм:

нехай A = (x1, y1), B = (x2, y2);

(X_лево, y_верх, x_право, y_ніз) -відтинає прямокутник

функція код (<точка>) повертає код, значення якого описано вище

Відсікти (x1, y1, x2, y2, x_лево, y_верх, x_право, y_ніз)

{

поки ((код (A) | код (B)) && (! (код (A) & код (B))))

{

якщо (код (A) == 0) // т. е. A всередині

поміняти (A, B); // Міняємо координати місцями, щоб A завжди лежала зовні

якщо (код (A) & 0x01) // т. е. A лежить зліва від відсікаючого прямокутника

{

y1 + = (y2-y1) * (x_лево-x1) / (x2-x1);

x1 = x_лево;

}

інакше якщо (код (A) & 0x02) // т. е. A лежить зверху від відсікаючого прямокутника

{

x1 + = (x2-x1) * (y_верх-y1) / (y2-y1);

y1 = y_верх;

}

інакше якщо (код (A) & 0x04) // т. е. A лежить праворуч від відсікаючого прямокутника

{

y1 + = (y2-y1) * (x_право-x1) / (x2-x1);

x1 = x_право;

}

інакше якщо (код (A) & 0x08) // т. е. A лежить знизу від відсікаючого прямокутника

{

x1 + = (x2-x1) * (y_ніз-y1) / (y2-y1);

y1 = y_ніз;

}

}

}

На виході AB - Відсічений відрізок.

Малювання відрізка з нецілочисельне координатами кінців «-- попередня | наступна --» Відсікання опуклим багатокутником.
загрузка...
© om.net.ua