Простой метод решения проблемы охвата отсекаемым многоугольником вершины окна предлагается в алгоритме Сазерленда-Хогдмана [40], когда весь многоугольник последовательно отсекается каждой границей окна, как это показано на рис. 0.3.23.
 Рис. 0.3.21: Последовательное отсечение многоугольника сторонами окна
При отсечении ребра, соединяющего очередную пару вершин K и L, возможны 4 случая взаимного расположения (рис. 0.3.24):
ребро на внутренней стороне границы,
ребро выходит из окна наружу,
ребро на внешней стороне границы,
ребро входит снаружи в окно.
 Рис. 0.3.22: Относительные расположения ребра и границы окна
В случае а) в результат добавляется вершина L. В случае б) в результат заносится S - точка пересечения ребра с границей. В случае в) нет вывода. В случае г) выдаются точка пересечения S и конечная точка ребра L.
Для определения взаимного расположения и направленности используется векторное произведение вектора P1P2, проведенного из начальной в конечную точку текущего ребра окна, на вектор b>P1S из начальной точки текущего ребра окна в очередную вершину S многоугольника (рис. 0.3.25).
 Если P1P2 ×P1S < 0, то поворот от P1P2 к P1S по часовой стрелке, т.е. точка S внутри окна.
Если P1P2 ×P1S > 0, то поворот от P1P2 к P1S против часовой стрелки, т.е. точка S вне окна.
Рис. 0.3.23: Определение взаимного расположения окна и вершины
Предложена аппаратная реализация этого алгоритма, состоящая из четырех идентичных ступеней отсечения без промежуточной памяти [28].
В алгоритме Сазерленда-Ходгмана в результат могут заноситься границы окна, даже если они и не ограничивают видимую часть отсеченного многоугольника. Это можно устранить дополнительным анализом, либо используя более сложный алгоритм отсечения.
8 8 8
| |
*
Обратная связь