Пример Простое двумерное отсечение.
Простой алгоритм двумерного отсечения
Основные алгоритмы двумерного отсечения и их идеи
Отсечение.
l алгоритмы, использующие кодирование концов отрезка или всего отрезка :
- алгоритм Коэна-Сазерленда (Cohen-Sutherland, CS-алгоритм)
- FC-алгоритм (Fast Clipping - алгоритм)
l алгоритмы, использующие параметрическое представление отсекаемых отрезков и окна отсечения.
- алгоритм Кируса-Бека (Curus-Beck, CB - алгоритм)
- более поздний алгоритм Лианга-Барски (Liang-Barsky, LB-алгоритм)
Алгоритмы с кодированием применимы для прямоугольного окна, стороны которого параллельны осям координат,
Алгоритмы с параметрическим представлением применимы для произвольного окна.
Алгоритмов двумерного отсечения огромное количество. Кратко рассмотрим некоторые из них:
В этом алгоритме отрезок отсекается поочередно каждой из сторон окна, а для полученных точек пересечения проверяется их принадлежность внутренней области окна, т. е. корректность пересечения. Эта процедура применяется сначала к исходному отрезку Р1Р2 и получается отрезок Р1'Р2, а затем к отрезку Р1'Р2 и получается результирующий отрезок Р1'Р2'.
1. Вычисление кодов концевых точек отрезка.
2. Занесение этих кодов в 2 массива, размерностью 1х4 каждый.
3. Проверка полной видимости отрезка. Если отрезок полностью видим goto 13.
4. Проверка тривиальной невидимости отрезка. Если отрезок полностью невидим goto 13.
5. Отрезок может быть частично видим. Проверяется попадание концевых точек отрезка внутрь окна. Если концевые точки внутри окна есть, goto 8.
6. Внутри окна нет концов отрезка.
7. Инициализация номера конца отрезка. Если обработано оба конца отрезка, goto 13.
8. Проверяется вертикальность отрезка. Если отрезкок вертикален, goto 11.
9. Ищутся точки пересечения отрезка с левым и правым краями окна. Если пересечение обнаружено, goto 7.
10. Проверяется горизонтальность отрезка. Если отрезок горизонтален, goto 7.
11. Проверяется пересечение отрезка с верхним и нижним краями окна. Если пересечение обнаружено, goto 7.
12. Если пересечений не обнаружено, то отрезок невидим.
13. Завершение работы и вызов процедуры черчения.
14. Перейти к обработке следующего отрезка.
В примере 3.1 показано, как этот простой метод позволяет отбросить некорректные пересечения путем простого сравнения координат точек пересечения с координатами сторон окна.
Рассмотрим отсекаюшее окно и отрезки, изображенные на рис. 3.2.
Наклон отрезка от Р1(- 3/2,1/6) до Р2(1/2,3/2) равен m = (y2 - y1) / (x2 - x1) = (3/2 - 1/6) / [1/2 - (- 3/2)] = 2/3. Его пересечения со сторонами окна таковы:
с левой: х = -1 y = (2/3)[-1 - (-3/2)] + 1/6 = ½
с правой: х = 1 y = (2/3)[1 - (-3/2)] + 1/6 = 11/6(последнее число больше, чем yв, и поэтому отвергается)
с верхней: y = 1 x = -3/2 + (3/2)[1 - 1/6] = -1/4
c нижней: y = -1 х = -3/2 + (3/2)|-1 - 1/6] = -13/4
(последнee число меньше, чем хп, и поэтому отвергается)
Аналогично, отрезок от Р3(-3/2,-1) до Р4(3/2,2) имеет
| m = | y2 - y1  x2 - x1
| = | 2 - (-1)  3/2 - (-3/2)
| = 1 |
и пересечения:
с левой: х = -1 y = (1)[-1 - (-3/2)] + (-1) = -1/2
с правой: х = 1 y = (1)[1 - (-3/2)] + (-1) = 3/2
(последнее число больше, чем yв, и поэтому отвергается)
с верхней: y = 1 x = -3/2 + (1)[1 - (-1)] = ½
c нижней: y = -1 х = -3/2 + (1)|-1 - (-1)] = -3/2
(последнee число меньше, чем хл, и поэтому отвергается)