В компьютерной графике , то алгоритм Liang-Барский (названный в честь You-Dong Liang и Брайан А. Барский ) является линией отсечения алгоритма. Алгоритм Лянга – Барского использует параметрическое уравнение линии и неравенства, описывающие диапазон окна отсечения, для определения пересечений между линией и окном отсечения . С помощью этих пересечений он знает, какую часть линии следует провести. Этот алгоритм значительно более эффективен, чем Коэн – Сазерленд . Идея алгоритма отсечения Лянга – Барски состоит в том, чтобы провести как можно больше тестов перед вычислением пересечений линий.
Рассмотрим сначала обычную параметрическую форму прямой:
Точка находится в окне клипа, если
а также
которое можно выразить в виде 4 неравенств
где
Чтобы вычислить последний отрезок линии:
- Линия, параллельная краю окна отсечения, имеет для этой границы.
- Если для этого , , то линия полностью выходит за пределы и может быть устранена.
- Когда , линия переходит наружу внутрь окна клипа, а когда , линия идет изнутри наружу.
- Для ненулевого , дает точку пересечения.
- Для каждой строки рассчитайте а также . Для, посмотрите границы, для которых (т.е. снаружи внутрь). Брать быть самым большим среди . Для, посмотрите границы, для которых (т.е. изнутри наружу). Брать быть минимумом . Если, линия находится снаружи и поэтому отклонена.
// Алгоритм обрезки линии Лян-Барского #include #include #include используя пространство имен std ;// эта функция дает максимальное значение с плавающей запятой maxi ( float arr [], int n ) { float m = 0 ; for ( int i = 0 ; i < n ; ++ i ) if ( m < arr [ i ]) m = arr [ i ]; return m ; }// эта функция дает минимальное значение с плавающей запятой mini ( float arr [], int n ) { float m = 1 ; for ( int i = 0 ; i < n ; ++ i ) if ( m > arr [ i ]) m = arr [ i ]; return m ; }void liang_barsky_clipper ( float xmin , float ymin , float xmax , float ymax , float x1 , float y1 , float x2 , float y2 ) { // определение переменных float p1 = - ( x2 - x1 ); поплавок p2 = - p1 ; float p3 = - ( y2 - y1 ); поплавок p4 = - p3 ; float q1 = x1 - xmin ; float q2 = xmax - x1 ; float q3 = y1 - ymin ; Поплавок Q4 = уты - у1 ; float posarr [ 5 ], negarr [ 5 ]; int posind = 1 , negind = 1 ; posarr [ 0 ] = 1 ; negarr [ 0 ] = 0 ; прямоугольник ( xmin , ymin , xmax , ymax ); // отрисовываем окно отсечения if (( p1 == 0 && q1 < 0 ) || ( p2 == 0 && q2 < 0 ) || ( p3 == 0 && q3 < 0 ) || ( p4 == 0 && q4 < 0 )) { outtextxy ( 80 , 80 , «Линия параллельна окну отсечения!» ); возврат ; } если ( p1 ! = 0 ) { float r1 = q1 / p1 ; поплавок r2 = q2 / p2 ; если ( p1 < 0 ) { negarr [ negind ++ ] = r1 ; // для отрицательного p1 добавляем его к отрицательному массиву posarr [ posind ++ ] = r2 ; // и добавляем p2 в положительный массив } else { negarr [ negind ++ ] = r2 ; posarr [ posind ++ ] = r1 ; } } если ( p3 ! = 0 ) { float r3 = q3 / p3 ; поплавок r4 = q4 / p4 ; если ( p3 < 0 ) { negarr [ negind ++ ] = r3 ; posarr [ posind ++ ] = r4 ; } else { negarr [ negind ++ ] = r4 ; posarr [ posind ++ ] = r3 ; } } float xn1 , yn1 , xn2 , yn2 ; float rn1 , rn2 ; rn1 = макси ( негарр , негарр ); // максимум отрицательного массива rn2 = mini ( posarr , posind ); // минимум положительного массива if ( rn1 > rn2 ) { // отклонить outtextxy ( 80 , 80 , «Строка за пределами окна отсечения!» ); возврат ; } xn1 = x1 + p2 * rn1 ; yn1 = y1 + p4 * rn1 ; // вычисление новых точек xn2 = x1 + p2 * rn2 ; yn2 = y1 + p4 * rn2 ; setcolor ( CYAN ); строка ( xn1 , yn1 , xn2 , yn2 ); // рисование новой линии setlinestyle ( 1 , 1 , 0 ); строка ( x1 , y1 , xn1 , yn1 ); строка ( x2 , y2 , xn2 , yn2 ); }int main () { cout << " \ n Обрезка линии по Лян-Барскому" ; cout << " \ n Структура окна системы: (0,0) внизу слева и (631, 467) вверху справа" ; cout << " \ n Введите координаты окна (wxmin, wxmax, wymin, wymax):" ; float xmin , xmax , ymin , ymax ; cin >> xmin >> ymin >> xmax >> ymax ; cout << " \ n Введите конечные точки линии (x1, y1) и (x2, y2):" ; float x1 , y1 , x2 , y2 ; cin >> x1 >> y1 >> x2 >> y2 ; int gd = DETECT , gm ; // использование библиотеки winbgim для C ++, инициализация графического режима initgraph ( & gd , & gm , "" ); liang_barsky_clipper ( xmin , ymin , xmax , ymax , x1 , y1 , x2 , y2 ); getch (); closegraph (); }
Смотрите также
Алгоритмы, используемые с той же целью:
Рекомендации
- Лян, Ю. Д., и Барски, Б., « Новая концепция и метод обрезки строк », ACM Transactions on Graphics , 3 (1): 1-22, январь 1984.
- Лян, Ю.Д., Б.А., Барски и М. Слейтер, Некоторые улучшения в алгоритме параметрического отсечения строк, CSD-92-688, Отдел компьютерных наук, Калифорнийский университет, Беркли, 1992.
- Джеймс Д. Фоули. Компьютерная графика: принципы и практика . Addison-Wesley Professional, 1996. стр. 117.