Рис. 6.26. Четыре возможных выхода процедуры отсечения левой границей в зависимости от положения пары конечных точек относительно левой границы отсекающего окна Общая схема этого алгоритма состоит в следующем: последовательно проводить пары концов соседних сторон многоугольника по ряду процедур отсечения (отсечение слева, справа, снизу, сверху). Когда процедура отсечения завершает обработку пары вершин, выходные координаты оставшихся вершин (если они есть) передаются следующей процедуре отсечения. Затем первая процедура отсечения обрабатывает следующую пару конечных точек. При подобной схеме отдельные процедуры отсечения по границе могут работать параллельно.
При обработке стороны многоугольника процедурой отсечения по границе нужно рассмотреть четыре возможные ситуации. Первая возможность - первый конец отрезка находится снаружи отсекающий границы, а второй - внутри. Вторая - оба конца находятся внутри. Третья ситуация - первая конечная точка находится внутри, а вторая снаружи границы. Наконец, обе точки могут находиться снаружи границы.
Чтобы облегчить передачу вершин с одного этапа отсечения на другой, выход каждой процедуры отсечения можно сформулировать так, как показано на рис. 6.26. При передаче последовательных пар конечных точек одной из четырех процедур отсечения выход генерируется согласно результатам следующих проверок.
1. Если первая входная вершина находится вне данной границы отсекающего окна, а вторая расположена внутри, две точки - пересечения стороны многоугольника с границей окна и вторая вершина - передаются следующей процедуре отсечения.
2. Если обе входные вершины находятся внутри данной границы отсекающего окна, следующей процедуре передается только вторая вершина.
3. Если первая вершина находится внутри данной границы отсекающего окна, а вторая - снаружи, следующей процедуре передается только точка пересечения стороны многоугольников с границей отсекающего окна.
4. Если обе входные вершины находятся вне данной границы отсекающего окна, ни одна из них не передается следующей процедуре.
Рис. 6.27. Обработка набора вершин многоугольника {1, 2, 3} процедурами отсечения по границам с использованием алгоритма Сазерленда-Ходгмана. Набор вершин после отсечения - {1',2, 2', 2"}
Последняя в цикле процедура отсечения генерирует список вершин, который описывает окончательную обрезанную закрашенную область.
На рис. 6.27 изображен пример алгоритма Сазерленда-Ходгмана для закрашенной области, определенный списком вершин {1,2,3}. Пока процедура отсечения получает пару конечных точек, она определяет соответствующий выход, используя проверки, иллюстрируемые на рис. 6.26. Данные выходы последовательно передаются от процедуры отсечения по левой границе процедурам отсечения по правой, нижней и верхней границам. Выход процедуры отсечения по верхней границе представляет собой набор вершин, определяющих окончательную закрашенную область. В приведенном примере выходной список вершин выглядит как {1',2,2/,2"}.