Двумерный алгоритм Лианга-Барски

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Двумерный алгоритм Лианга-Барски



1. История

В 1982 г. Лианг и Барски предложили алгоритмы отсечения прямоугольным окном с использованием параметрического представления для двух, трех и четырехмерного отсечения. По утверждению авторов, данный алгоритм в целом превосходит алгоритм Коэна-Сазерленда. Однако в некоторых работах показывается, что это утверждение справедливо только для случая, когда оба конца видимого отрезка вне окна и окно небольшое (до 50Ч50 при разрешении 1000Ч1000).

2. Содержание алгоритма

При 2D отсечении прямые отсекаются по 2D области, называемой окном отсечения. В частности, внутренняя часть окна отсечения может быть выражена с помощью следующих неравенств:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/



Внутренняя часть окна отсечения

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Продолжим каждую из четырех границ окна до бесконечных прямых. Каждая из таких прямых делит плоскость на 2 области. Назовем «видимой частью» ту, в которой находится окно отсечения, как это показано на рисунке (рис. 2). Видимой части соответствует внутренняя сторона линии границы. Невидимой части плоскости соответствует внешняя сторона линии границы.

Таким образом, окно отсечения может быть определено как область, которая находится на внутренней стороне всех линий границ.

Отсекаемый отрезок прямой может быть преобразован в параметрическое представление следующим образом. Пусть конечные точки отрезка есть и с координатами и , соответственно. Тогда параметрическое представление линии может быть задано следующим образом:



где

Или в общем виде для отрезка, заданного точками и :

Для точек и параметр равен и 1, соответственно. Меняя от 0 до 1, перемещаемся по отрезку от точки к точке . Изменяя в интервале , получаем бесконечную (далее удлиненную) прямую, ориентация которой - от точки к точке .

Однако вернемся к формальному рассмотрению алгоритма отсечения.

Подставляя параметрическое представление, заданное уравнениями (2) и (3), в неравенства (1), получим следующие соотношения для частей удлиненной линии, которая находится в окне отсечения:

Заметим, что соотношения (4) - неравенства, описывающие внутреннюю часть окна отсечения, в то время как равенства определяют его границы.

Рассматривая неравенства (4), видим, что они имеют одинаковую форму вида:



Здесь использованы следующие обозначения:

Вспоминая определения внутренней и внешней стороны линии границы (см. рис. 2), замечаем, что каждое из неравенств (5) соответствует одной из граничных линий (левой, правой, нижней и верхней, соответственно) и описывает ее видимую сторону. (Например, для имеем: ).

Удлиним в бесконечную прямую. Тогда каждое неравенство задает диапазон значений параметра , для которых эта удлиненная линия находится на видимой стороне соответствующей линии границы. Более того, конкретное значение параметра для точки пересечения есть .

Причем знак показывает на какой стороне соответствующей линии границы находится точка . А именно, если , тогда находится на видимой стороне линии границы, включая и ее. Если же , тогда находится на невидимой стороне.

Рассмотрим в соотношениях (6). Ясно, что любое может быть меньше 0, больше 0 и равно 0.

Если , тогда соответствующее неравенство становится:



Для пояснения на рисунке (рис. 3) показано пересечение с левой и правой границами при .

Очевидно, что диапазон значений параметра , для которых удлиненная линия находится на видимой стороне соответствующей граничной линии, имеет минимум в точке пересечения направленной удлиненной линии, заданной вектором и идущей с невидимой на видимую сторону граничной линии (так как только на границе , а в остальной части видимой стороны больше).

Аналогично, если , тогда соответствующее неравенство становится:

Для пояснения на рисунке (рис. 4) показано пересечение с левой и правой границами при .

Так как значения параметра только на границе равны , а в остальной видимой части меньше , то значение параметра имеет максимум на границе.

Наконец, если , тогда соответствующее неравенство превращается в:



Заметим, что здесь нет зависимости от , т.е. неравенство выполняется для всех , если и не имеет решения при . Для пояснения на рисунке (рис. 5) иллюстрируется случай .

Итак, рассмотрение четырех неравенств дает диапазон значений параметра , для которого удлиненная линия находится внутри окна отсечения. Однако, отрезок только часть удлиненной линии и он описывается значениями параметра в диапазоне: . Таким образом, решение задачи двумерного отсечения эквивалентно решению неравенств (5) при условии .

Решение этой задачи сводится к далее описанному отысканию максимумов и минимумов.

Вспомним, что для всех таких, что , условие видимости имеет вид: . Из условия принадлежности точек удлиненной линии отрезку имеем . Таким образом, нужно искать:

Аналогично, для всех таких что , условие видимости и, следовательно, .

Наконец, для всех , таких что следует проверить знак . Если , то это случай тривиального отбрасывания, задача отсечения решена и дальнейшие вычисления не нужны. Если же , то информации, даваемой неравенством, недостаточно и это неравенство игнорируется.

Правая часть неравенств (10) и (11) - значения параметра , соответствующие началу и концу видимого сегмента, соответственно. Обозначим эти значения как и :

Если сегмент отрезка видим, то ему соответствует интервал параметра:

Следовательно, необходимое условие видимости сегмента:

Но это недостаточное условие, так как оно игнорирует случай тривиального отбрасывания при , если . Тем не менее - это достаточное условие для отбрасывания, т.е. если , то отрезок должен быть отброшен. Алгоритм проверяет, если с , или и в этом случае отрезок немедленно отбрасывается без дальнейших вычислений.

Детали реализации

В алгоритме и инициализируются в 0 и 1, соответственно. Затем последовательно рассматривается каждое отношение .

1) Если , то отношение вначале сравнивается с и, если оно больше , то этот случай отбрасывания. В противном случае оно сравнивается с и, если оно больше, то должно быть заменено на новое значение.

2) Если , то отношение вначале сравнивается с и, если оно меньше , то этот случай отбрасывания. В противном случае оно сравнивается с и, если оно меньше, то должно быть заменено на новое значение.

3) Наконец, если и , то этот случай отбрасывания.

На последнем этапе алгоритма, если отрезок еще не отброшен, то и используются для вычисления соответствующих точек. Однако, если , то конечная точка равна и не требуется вычислений. Аналогично, если , то конечная точка - и вычисления также не нужны.

3. Геометрический смысл алгоритма

алгоритм барски параметрический отсечение

Геометрический смысл этого процесса состоит в том, что отрезок удлиняется для определения, где эта удлиненная линия пересекает каждую линию границы. Более детально, каждая конечная точка заданного отрезка используется как начальное значение для конечных точек отсеченного отрезка .

Затем вычисляются точки пересечения удлиненной линии с каждой линией границы (эти вычисления соответствуют вызову вспомогательной процедуры в программе). Если для данной линии границы направление, определяемое , идет с невидимой на видимую сторону линии границы, то эта точка пересечения вначале сравнивается с . Если точка находится далее вдоль линии, тогда (и таким образом, ) должна быть на невидимой стороне линии, поэтому отрезок должен быть отброшен. В противном случае точка пересечения сравнивается с , если точка далее вдоль линии, тогда перемещается вперед к этой точке.

С другой стороны, если направление с видимой на невидимую сторону, тогда точка пересечения вначале сравнивается с . Если далее вдоль линии, чем точка пересечения, тогда (и, следовательно, ) находится на невидимой стороне линии границы, т.е. отрезок должен быть отброшен. В противном случае точка пересечения сравнивается с и, если далее вдоль линии, тогда перемещается назад к точке пересечения.

Наконец, если удлиненная линия параллельна граничной линии и она на невидимой стороне, то отрезок отбрасывается. В конце алгоритма, если отрезок не отброшен, тогда и используются как конечные точки видимой части отрезка.

4. Реализация алгоритма

С++

#include <iostream> // cin, cout

using namespace std; // std:

// класс отрезков

class Segment

{

public:

double xStart, yStart, xEnd, yEnd;

};

// класс точек

class PointS

{

public:

double x, y;

};

/*

* Часть алгоритма Лианга-Барски. Определяет входимость линии в прямоугольник и

* задаёт параметры t (minT и maxT)

* Возвращает false, если линия не входит в прямоугольную область

* Pi, Qi - параметры в алгоритме

*/

bool VisibleLine (double &MinT, double &MaxT, double Pi, double Qi)

{

// инициализируем

bool InputResult = true;

double t;

// идем по уже отработанному алгоритму

if (Pi == 0)

{

if (Qi < 0)

{

InputResult = false;

}

}

else

{

t = Qi / Pi;

if (Pi < 0)

{

if (t > MaxT)

{

InputResult = false;

}

else

{

if (t > MinT)

{

MinT = t;

}

}

}

else

{

if (t < MinT)

{

InputResult = false;

}

else

{

if (t < MaxT)

{

MaxT = t;

}

}

}

}

return InputResult;

}

/*

* Алгоритм Лианга-Барски

* Возвращает координаты отсечённого отрезка

* LineStart - координаты начало отрезка

* LineEnd - координаты конца отрезка

* BoxLU - координаты левого верхнего угла прямоугольной области

* BoxRD - координаты правого нижнего угла прямоугольной области

*/

Segment LiangBarskyAlg (PointS LineStart, PointS LineEnd, PointS BoxLU, PointS BoxRD)

{

// инициализация

// начальные значения для t

double MinT = 0, MaxT = 1;

// dx, dy

double dx = LineEnd.x - LineStart.x;

double dy = LineEnd.y - LineStart.y;

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

bool FlagVisible = false;

// результирующий отрезок

Segment ResultLine;

ResultLine.xEnd = LineEnd.x;

ResultLine.yEnd = LineEnd.y;

ResultLine.xStart = LineStart.x;

ResultLine.yStart = LineStart.y;

//

// проверяем на видимость продленной линии в каждой из частей

if (VisibleLine (MinT, MaxT, - dx, LineStart.x - BoxLU.x))

{

if (VisibleLine (MinT, MaxT, dx, BoxRD.x - LineStart.x))

{

if (VisibleLine (MinT, MaxT, - dy, LineStart.y - BoxRD.y))

{

if (VisibleLine (MinT, MaxT, dy, BoxLU.y - LineStart.y))

{

// находится в области сечения

FlagVisible = true;

if (MaxT < 1)

{

ResultLine.xEnd = LineStart.x + MaxT * dx;

ResultLine.yEnd = LineStart.y + MaxT * dy;

}

if (MinT > 0)

{

ResultLine.xStart = LineStart.x + MinT * dx;

ResultLine.yStart = LineStart.y + MinT * dy;

}

}

}

}

}

// если не виден

if (! FlagVisible)

{

ResultLine.xEnd = 0;

ResultLine.yEnd = 0;

ResultLine.xStart = 0;

ResultLine.yStart = 0;

}

return ResultLine;

}

void ShowResult (Segment &ResultSegment)

{

// выводим ответ

cout << «Итоговый отрезок будет иметь координаты:» << endl << endl;

cout << «Начало (» << ResultSegment.xStart <<»,» << ResultSegment.yStart <<»)» << endl;

cout << «Конец (» <<ResultSegment.xEnd <<»,» << ResultSegment.yEnd <<»)» << endl << endl;

}

// процедура ожидания клавиши

void WaitUserEnter()

{

system («pause»); // Для продолжения нажмите любую клавишу…

}

// основное тело программы

int main()

{

// инициируем отрезок

PointS LineStart;

LineStart.x = 0.0;

LineStart.y = 480.0;

PointS LineEnd;

LineEnd.x = 640.0;

LineEnd.y = 0.0;

// инициируем окно сечения

PointS BoxLU;

BoxLU.x = 0.0;

BoxLU.y = 450.0;

PointS BoxRD;

BoxRD.x = 600.0;

BoxRD.y = 0.0;

// вызываем алгоритм

Segment ResultSegment = LiangBarskyAlg (LineStart, LineEnd, BoxLU, BoxRD);

// выводим ответ

ShowResult(ResultSegment);

// ждать клавиши

WaitUserEnter();алгоритм барски параметрический отсечение

return 0;

Размещено на Allbest.ru