2.5. ОТСЕЧЕНИЕ ЛИНИЙ

Предположим, что мировые и экранные координаты одинаковы, то есть окно и область вывода совпадают. Поэтому в этом параграфе термин “окно” везде может быть заменен на термин “область вывода”. Однако обычно считается, что отсечение выполняется по границам окна, а не области вывода, это и учитывается в данном случае.

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

Рис. 2.7. Треугольник, подвергающийся операции отсечения

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

Совмещая это уравнение с соотношением

получим

Отсюда легко вычисляются координаты точки Р, если из вестно, что концевая точка Р находится внутри окна, а другая концевая точка удовлетворяет неравенствам

Однако необходимо рассмотреть значительно больше ситуаций. Большое разнообразие логических операций, которые нужно выполнить для решения этой задачи, делают проблему отсе чения линий очень интересной с алгоритмической точки зрения Из рис. 2.8 очевидно, что совершенно недостаточно отсечь отрезок прямой линии PQ относительно прямой линии Коэн у Сазерленд разработали алгоритм для отсечения отрезков прямых линий, который описан на языке Паскаль в книге Ньюмеш и Спрула (1979). Здесь этот алгоритм будет представлен на языке Си.

С любой точкой будем ассоциировать четырехбитовы код

где может быть либо 0, либо . Этот код содержит полезную информацию о положении точки Р относительно В языке Си условные выражения вырабатывают значения. Так значение выражения будет равно 1, то есть “истина”, если оно верно, и 0, то есть “ложь”, если условие не вы полняется. Используя это правило, можно записать

Рис. 2.8. Последовательные шаги отсечения

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

На языке Си значения кодов вырабатываются функцией

Для понимания этого выражения необходимо знать, что выражение означает, что битовое значение сдвигается на

Рис. 2.9. Значения кодов

позиций влево. Кроме битовой операции сдвига есть еще битовый оператор побитовой операции ИЛИ, записываемый знак вертикальной черты (I). Этот оператор нельзя путать с логическим оператором ИЛИ, обозначаемым двойной вертикаль ной чертой (II). Менее эффективной записью вышеприведенного выражения в операторе возврата было бы выражение

Это выражение здесь приводится исключительно с цельк облегчения восприятия предыдущего выражения.

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

Если хотя бы один из кодов для точек и содержит единичный бит, то либо либо перемещается из области окна к одной из границ окна или к ее продолжению. В последнсь случае точка по-прежнему будет находиться вне окна и понадо бится еще одно перемещение. Например, в случае, изображен ном на рис. 2.8, за перемещением из точки Р в точку должьк последовать перемещение из точки в точку Затем может по требоваться отсечение другого конца отрезка, как это видно рис. 2.8. Таким образом, процесс отсечения может быть много ступенчатым, на каждом шаге расстояние между точками и Р уменьшается. Процесс завершается, как только обе точки ока жутся в пределах окна. Оставшаяся часть отрезка будет вы черчена. Однако существует еще один важный случай, когд цикл должен быть завершен, а именно, когда обе точки находятся вне окна и в то же время по одну сторону от окна. ситуацию нельзя различить вначале, но она может возникнуть процессе отсечения. Если концевые точки отрезка прямой лини! находятся вне окна, то отрезок может пересекать окно, но може оказаться и полностью вне окна, как показано на рис. На рис. 2.10 точки и сначала не находятся одновременн ниже окна. Но в процессе отсечения точки определяют новые позиции точек соответственно. Поскольку теперь об точки находятся ниже окна, то можно сделать вывод, что ничег не надо вычерчивать. Такое решение принимается на основ анализа значений Точки

Рис. 2.10. Отрезок вне окна

находятся по одну сторону от окна тогда и только тогда, если их коды содержат 1 в одной и той же позиции. Для трех точек третий бит слева (61) в их кодах равен 1, тогда как для точки этот бит равен 0. Поэтому точка должна быть перемещена в точку Перемещение точки в точку не является необходимым, но это перемещение выполняется потому, что оно не приносит вреда, а реализация алгоритма получается проще.

Подобно оператору побитовой операции ИЛИ, обозначаемому вертикальной чертой (I) и упомянутому ранее, в языке Си имеется оператор побитовой операции Я, обозначаемый знаком Напомним, что логические версии подобных операторов обозначаются символами Побитовые операторы (обозначаемые знаками дают в результате битовые последовательности, тогда как логические операции — простые значения 1 или 0, обозначающие соответственно “истина” и “ложь”. Не только 1, но и любое другое не равное 0 значение, представляет «истину», если оно используется в логической операции. Таким образом, Циклическая конструкция

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

бите, то есть пока в аргументах или существует хотя один бит, содержащий 1. С другой стороны, оператор

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

(см. скан)

(см. скан)

На рис. 2.11 показан результат работы этой программы.

Рис. 2.11. Результат работы программы CUPDEMO