Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Отсечение отрезка. Алгоритм Сазерленда-Кохена

 

Задачу отсечения иногда называют задачей клиппирования (от английского clip - отрезать, отсекать). Она возникает довольно часто. Пример - размещение изображений в окнах, в том числе занимающих весь экран, при различном разрешении (640*480, 800*600 и т.д.). Требуется знать пикселы, лежащие за пределами окна, и не работать с ними. Решение "в лоб" - сравнивать с границами каждый выводимый пиксел. Но это долго, т.к. сравнение должно быть встроено в цикл в алгоритме Брезенхейма. К тому же границы должны или где-то храниться в виде набора адресов пикселов, или вычисляться путем 4-х кратного (для каждой стороны прямоугольника) решения уравнения прямой для каждой точки. Придется также учитывать специальные случаи горизонтальной и вертикальной прямой, а также вырождение прямой в точку.

Алгоритм Сазерленда-Кохена широко известен благодаря простоте и эффективности. Плоскость делится на 9 областей. В каждой из областей точки по отношению к прямоугольнику расположены одинаково. Определив, в какие области попали концы отрезка, легко определить, где нужно отсечение. Для этого каждой области сопоставляется 4-битовый код, имеющий следующий смысл:

 

 

           
 
 
 
 
 
 
 


 
 
 
N бита

Положение точки при бит=1
  Слева от прямоугольника
 
 
 
1

Выше прямоугольника
  Справа от прямоугольника
  Ниже прямоугольника

 

Соотношение конечных точек и прямоугольника вычисляется с помощью поразрядных логических операций над кодами. Они выполняются очень быстро, т.к. в процессорах 80x86 есть машинные команды AND и OR. Реализацию алгоритма см. в [ 1,3 ]. Программа из [ 1 ] - в rastr\clip\line3.cpp.

 

#include <conio.h>

#include <graphics.h>

#include <process.h>

#include <stdio.h>

#include <stdlib.h>

 

void Swap (int& a, int& b)

{

int c;

c = a;

a = b;

b = c;

}

 

int OutCode (int x, int y, int X1, int Y1, int X2, int Y2)

{

int code = 0;

// Кодирование точки в соответствии с правилами образования кодов

if (x < X1)

code |= 0x01; // код 0001

if (y < Y1)

code |= 0x02; // код 0010

if (x > X2)

code |= 0x04; // код 0100

if (y > Y2)

code |= 0x08; // код 1000

return code;

}

 

void ClipLine (int x1, int y1, int x2, int y2,

int X1, int Y1, int X2, int Y2)

{

// кодирование концов отрезка *

int code1 = OutCode (x1, y1, X1, Y1, X2, Y2);

int code2 = OutCode (x2, y2, X1, Y1, X2, Y2);

int inside = (code1 | code2) == 0; // внутри

int outside = (code1 & code2)!= 0; // вне

while (!outside &&!inside)

{

if (code1 == 0)

{

Swap (x1, x2);

Swap (y1, y2);

Swap (code1, code2);

}

if (code1 & 0x01) // clip left

{

y1 += (long)(y2-y1)*(X1-x1)/(x2-x1);

x1 = X1;

}

else

if (code1 & 0x02) // clip above

{

x1 += (long)(x2-x1)*(Y1-y1)/(y2-y1);

y1 = Y1;

}

else

if (code1 & 0x04) // clip right

{

y1 += (long)(y2-y1)*(X2-x1)/(x2-x1);

x1 = X2;

}

else

if (code1 & 0x08) // clip below

{

x1 += (long)(x2-x1)*(Y2-y1)/(y2-y1);

y1 = Y2;

}

code1 = OutCode (x1, y1, X1, Y1, X2, Y2);

code2 = OutCode (x2, y2, X1, Y1, X2, Y2);

inside = (code1 | code2) == 0;

outside = (code1 & code2)!= 0;

}

line (x1, y1, x2, y2);

}

 

main ()

{

int driver = DETECT;

int mode;

int res;

initgraph (&driver, &mode, "c:\\tcpp\\bgi");

if ((res = graphresult ())!= grOk)

{

printf("\nGraphics error: %s\n", grapherrormsg (res));

exit (1);

}

int ClipX1 = 100,

ClipY1 = 50,

ClipX2 = 540,

ClipY2 = 300;

rectangle (ClipX1, ClipY1, ClipX2, ClipY2);

setcolor(GREEN);

ClipLine (1, 100, 600, 200, ClipX1, ClipY1, ClipX2, ClipY2);

getch();

setcolor(YELLOW);

ClipLine (1, 100, 600, 500, ClipX1, ClipY1, ClipX2, ClipY2);

getch();

setcolor(12);

ClipLine (300, 600, 510, 3, ClipX1, ClipY1, ClipX2, ClipY2);

getch();

setcolor(11);

ClipLine (300, 0, 610, 200, ClipX1, ClipY1, ClipX2, ClipY2);

getch();

setcolor(9);

ClipLine (300, 0, 300, 500, ClipX1, ClipY1, ClipX2, ClipY2);

getch();

setcolor(13);

ClipLine (200, 100, 500, 200, ClipX1, ClipY1, ClipX2, ClipY2);

getch ();

closegraph ();

}

<== предыдущая лекция | следующая лекция ==>
Некоторые алгоритмы заполнения областей | Удаление невидимых линий и поверхностей
Поделиться с друзьями:


Дата добавления: 2014-01-11; Просмотров: 499; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.017 сек.