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

Отсечение

См. тут

Алгоритм Сазерланда Коэна

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

Так же как и в простом алгоритме, находятся коды концов отрезка. Сумма кодов концов = 0 - отрезок видимый, коды != 0, проанилизируем логическое произведение.

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

Основной нюанс алгоритма

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

Псевдокод

1. Ввод данных отсекателя (x_л, х_п, у_н, у_в), P1 и P2
2. Формирование признака FL = 0. Если p1.x = p2.x, то FL = -1.
   иначе, m = (p2.y - p1.y) / (p2.x - p1.x). Если m = 0, то FL = 1
3. Цикл отсечения по всем сторонам отсекателя (по i от 1 до 4)
   3.1. Обращение к функции определения видимости отрезка.
   3.2. Если отрезок видимый, то визуализируем. 
        Если отрезок невидимый, то переход к концу алгоритма
   3.3. Если T1[i] = T2[i], то переход на следующий шаг выполнения цикла.
   // так может быть только если они оба равны 0, т.к. отрезки где оба равны 1 мы обработали на 3.2.
   3.4. Если T1[i] = 0, то обмен местами вершин P1 и P2.
   3.5. Если FL != -1 (если отрезок не вертикальный), то 
          если i <= 2 то 
            P1.y = m(O[i] - P1.x) + P1.y, P1.x = O[i]
            Переход на следующий шаг
          иначе
            P1.x = 1/m * (O[i] - P1.y) + P1.x
        иначе
          P1.y = O[i]
   3.6. Конец цикла
4. Изображение отрезка P1 - P2.
5. Конец

Ответы на возможные вопросы Курова и на проверку понимания алгоритма:

Если суммы кодов концов отрезка отличны от нуля, какой вывод о расположении отрезка можно сделать?

Если одна из сумм кодов концов отрезка равна нулю, а вторая отлична от нуля, то отрезок частично видимый ((S1 == 0 и S2 <> 0) или (S1 <> 0 и S2 == 0)).
Если обе суммы ненулевые, то отрезок в действительности может оказаться частично видимым или полностью невидимым. Для распознавания части полностью невидимых отрезков можно использовать логическое произведение кодов концов отрезка: P = T1(1) * T2(1) + T1(2) * T2(2) + T1(3) * T2(3) + T1(4) * T2(4)

Если P <> 0, то отрезок невидимый.

Почему в случае if (T1[i] == T2[i]) continue; уходим на следующий шаг?

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

Логика здесь следующая: если одноименные биты коды концов отрезка равны, то мы считаем, что они могут равняться только нулю, т. е. обе вершины располагаются по видимую сторону по видимую сторону от текущей i-ой границы отсекателя, точки пересечения нет, нужно переходить на следующий шаг. Мы считаем, что они не могут одновременно равняться единице. Равенство одноименных разрядов кодов двух концов отрезка единице означает, что обе вершины лежат по невидимую сторону от текущей границы и означает тривиальную невидимость отрезка. До пункта if (T1[i] == T2[i]) continue; все подобные отрезки отбрасываются.

Почему в случае вертикального отрезка не проверяем if (flag != -1) номер шага, т.е. границу отсекателя, с которой ищем пересечение?

Вертикальный отрезок может быть полностью видимым, полностью невидимым, либо частично видимым.

Если он целиком видимый – это сразу обнаружится, уйдем сразу в визуализацию. Если полностью невидимый – уйдем в конец. Продолжится работа с вертикальным отрезком (частично видимым), но он в этом случае расположен по видимую сторону от левой и от правой границы. Значит, при выполнении пункта 3.3 (Если T1[i] =T2[i], то …) выяснится, что в первых двух разрядов обоих кодов для первой и второй вершин хранятся нули. По отношению к этим границам он является видимым и мы просто на первые два шага, где мы ищем пересечения с левой и правой границей не попадем. Мы будем переходить к следующей итерации. То есть, если мы дошли до пункта 3.5 (Если Fl <> -1, то …) и выяснили, что отрезок вертикальный, это будет означать, что мы ищем пересечения с верхней и нижней границей. Т. к. он вертикальный, x-координата изменяться не должна, измениться должна только y-координата.

Как решается вопрос о том, какую часть отрезка надо отбросить после нахождения пересечения?

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

Чем данный алгоритм отличается от простого?

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

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

Следующий вопрос: 14. Отсечение Алгоритм разбиения средней точкой при отсечении отрезка.

Предыдущий вопрос: 12. Двумерное отсечение. Простой алгоритм отсечения отрезка.